1.経路探索について
経路探索問題とは、どのように移動すれば出発地から目的地まで、時間、通行料金、環境負荷など様々な観点で最適なルートとなるのかをコンピュータ上で計算するという問題です。
身の回りで用いられている例は幅広く、例えば倉庫で複数の棚から荷物を取って運ぶ時、どんなルートをたどれば効率が良いのか、あるいは徒歩で駅から目的地へ移動するとき、どのようなルートをたどれば歩く距離が少ないのか等を計算する際に用いられています。カーナビやスマホアプリのルート案内サービスなどでも使われていますので、皆さんが目にする機会も多いと思います。
一般的に出発地から目的地まで到達する経路は無数に存在しますが、経路探索では探索したいルートの中から何らかの基準（時間、通行料金、環境負荷など）で最も望ましい経路を選ぶことで、最終的に経路を１つに絞り込みます。ここでの経路選択基準は、どのような経路を探したいかによって様々です。
例えば、車を運転するときには距離の短い経路、あるいは所要時間の短い経路が望ましいですが、電車の乗り換えの際には料金を重要視することもあります。
表1ではいくつの応用事例を挙げますが、様々な目的で経路探索が利用されていることがご覧いただけると思います。
| 経路探索が用いられる例 | 概要 | |
|---|---|---|
| 1 | 電車の乗り換え案内アプリにおける経路の探索 | 目的地までの膨大な経路の組み合わせの中から、所要時間が最小の経路や、料金や乗り換え回数が最小の経路を探索 |
| 2 | インターネットでのルーティング | Webサイトを閲覧する際、ネットワーク全体で負荷が分散されるように、ネットワーク上の通信経路を探索 |
| 3 | コンピュータゲームにおけるキャラクターの移動経路計算 | コンピュータが操作するキャラクターの移動について、プレイヤーの所在場所やキャラクター同士の相互関係を考慮したうえで、より自然に見える移動ルートを計算 |
| 4 | コンビニの商品配送ルートの決定 | 複数のエリアのコンビニを巡回するトラックに対し、配送時間帯等の制限を考慮しながら効率の良い配送順序を決定 |
| 5 | 災害時の避難ルートの生成 | 危険な場所を避けて通るための制約を加味し、経路の安全性および目的地への到達性の高いルートを速やかに選択 |
