 | >質問２
>複数の都市が道でつながっている様子をグラフで表し移動時間を辺のコストとします。
>同じ都市を何度も通ってよいという条件のもとで最小移動時間で全ての都市を回るには
>どのような手法があるでしょうか？
「同じ都市を何度も通ってよい」という条件がありますが、
次のように考えれば、「どの都市もちょうど一回だけ通る」
という「巡回セールスマン問題」に帰着できます。
はじめに与えられたグラフをGとします。
Gは連結な単純無向グラフとしておきます。
Gをもとにして、完全グラフHを次のように構成します。
Hの頂点集合はGの頂点集合に一致。
Gの任意の２点a,bに対して、aとbを結ぶGの最短パスの長さを、
Hの２点a,bを結ぶ辺の長さに設定します。
グラフGにおいて同じ都市を何度でも通ってよいという条件で、
全ての都市を回って元の位置に戻ってくる最小移動時間は、
グラフHにおいてどの都市もちょうど一回だけ通って元の位置
に戻ってくる最小移動時間に一致します。
(堀江伸一さんの質問は、必ずしも元の位置に戻ってくる必要はなく、
単に全ての都市を訪問すればよいという主旨なのかもしれませんが、
その場合にはグラフHの最小の長さのハミルトンパスを求めればよい
です。そしてその場合もやはり、或るグラフの巡回セールスマン問題
を解くことに帰着します。)
|