経路探索（けいろたんさく）
最終更新：2026/4/27
経路探索は、ある地点から別の地点へ到達するための最適な経路を見つけ出す処理である。
別名・同義語 ルート探索パスファインディング
ポイント
経路探索は、地図ナビゲーションシステムやロボットの自律移動など、様々な分野で応用されている技術である。計算複雑性や最適性の基準が課題となる。
経路探索とは
経路探索（Pathfinding）とは、グラフ理論における基本的な問題の一つであり、ある開始ノードから目標ノードまでの経路を探索するアルゴリズムのことです。この「経路」は、物理的な移動経路だけでなく、抽象的な関係性を示すこともあります。
経路探索の応用例
経路探索は、以下のような様々な分野で応用されています。
- 地図ナビゲーションシステム: 車載ナビゲーションやスマートフォンアプリなどで、出発地から目的地までの最適なルートを検索します。
- ロボット工学: ロボットが障害物を回避しながら目的地まで移動するための経路を計画します。
- ゲームAI: ゲームキャラクターがプレイヤーを追いかけたり、アイテムを探したりするための経路を決定します。
- ネットワークルーティング: インターネット上で、データパケットを効率的に転送するための経路を決定します。
- VLSI設計: 集積回路の配線経路を最適化します。
代表的な経路探索アルゴリズム
- ダイクストラ法 (Dijkstra’s algorithm): 開始ノードから他のすべてのノードへの最短経路を求めるアルゴリズムです。非負の重みを持つグラフに対して有効です。
- A探索 (A search): ダイクストラ法を改良したアルゴリズムで、ヒューリスティック関数を用いて探索範囲を絞り込み、より効率的に最短経路を探索します。
- 幅優先探索 (Breadth-First Search): 開始ノードから近い順にノードを探索するアルゴリズムです。最短経路を求めることができますが、探索範囲が広くなる可能性があります。
- 深さ優先探索 (Depth-First Search): 開始ノードから深く探索していくアルゴリズムです。メモリ使用量が少ないですが、最短経路を保証できません。