next up previous
: 最大クリーク問題(MAX-CLIQUE) : 近似アルゴリズムでよく取り扱われる問題(代表的なものの一部) : スケジューリング問題

巡回セールスマン問題(TSP)

セールスマンが訪問しなければならない町がn個あるとする. どの町からでも好きな町に移動できるものとする. 町から町に移動するのに交通費がかかるが, それは出発地と目的地により まちまちである. セールスマンは必ず全ての町を訪問し, 最後に(出発した時の)最初の町に 戻らなければならない. どのような順番で町を訪問したら, 交通費が最少にできるか? 例えば, 以下の図のように訪問すべき場所が5箇所あり, それぞれの 間の料金がそれらを結ぶ辺上の数字だとする. このとき, 点線のルートを たどると安くすむが, 実線のルートをたどると高くつく.



Koichi Yamazaki 平成12年3月15日