巡回セールスマン問題において、始点と終点が決まっていて、残りn個の頂点のうちr個だけ通ればいい場合に

巡回セールスマン問題において、始点と終点が決まっていて、残りn個の頂点のうちr個だけ通ればいい場合に最短になるように通る頂点の選択と順番を決めるアルゴリズムはありますでしょうか
すべての頂点を通るアルゴリズムは見つかるのですが、スタンプラリーにはエリア当たり○個スタンプを押せといったものが多いものですから

No.1 回答者： otaks 回答日時： 2016/09/10 09:45

直接の回答にならないと思いますが、

r個を選択する組み合わせすべてに対して、各最短経路を求めて、
それらのうち最短が、求めるものになるのではないでしょうか？

この回答へのお礼

まあ 総当たりということになりますけど
nCr通りの巡回セールスマン問題を計算しないといけないので。。。

直感的にはn個全部選んだ場合の最短経路から、順番を飛ばしたときに最も総距離が短くなるノードを削除して、r個になるまで繰り返すと最適解になるかもと思っていますが数学的な確証はないものでして。。

お礼日時：2016/09/14 18:04