あいまいな中間目標を有する巡回経路探索

概要

論文の詳細を見る
ノードとパスから構成されるネットワークにおいて、2点間の最短経路を求める問題は経路探索問題として知られ、始点及び終点は各々1個のみ与えられるのが通常である.これに対して目標地点にあいまい性があり、目標が複数存在する場合が考えられる。例えば東京を出発し、群馬、新潟、長野を回って東京に戻る計画を考える.ここで各々の県で行きたい観光地は3〜4ヵ所程度あるが、全部回る時間は無いため、各県1ヵ所を回る最短経路を知りたいとする。この種の問題において、県に相当する中間目標の巡回順序が与えられている場合は、"あいまいな中間目標を有する経路探索アルゴリズム"により求解可能である。しかし中間目標の巡回順序が与えられていない場合、中間目標の巡回の順列全てに対して最短経路を求めた上で最短経路を決定しなければならないため、中間目標数の増加とともに探索処理量も大きく増加する。そこで本稿では、上記の様な中間目標の巡回順序が与えられていない場合でも適用可能な巡回経路探索アルゴリズムを提案し、順列回の探索を行う順列法との探索処理量を比較する。
一般社団法人情報処理学会の論文
1990-03-14