巡回セールスマン問題の類似問題

質問

卒業研究の題材で巡回セールスマン問題をあつかっていて、解法に困ってます。巡回セールスマン問題の定義は「完全グラフにおいて全ての都市を回り、始点にもどってくる最短経路を探す問題」だと思うのですが、私の研究室の教授が、完全グラフ（すべての都市に道が繋がっているグラフ）ではなく、道の決まってるグラフで、しかも始点に戻ってくる必要のないグラフで考えるようにいわれました。確かに現実問題として全ての家に道が繋がっているケースは考えられません。たとえば、世界の全ての空港を最短距離で巡ろうとしたとき、今いる国からいけるところといけないところがあるのと同じです。
ただ、この場合の解法として、巡回しなくてもよいといっても完全グラフではないのでひたすら最短の道を選んでいては解がえられず、ハミルトン経路のように同じ道を２度使ってはいけないという定義でもないので、これもつかえません。この問題はいったいどう定義したらいいものでしょうか？また、このような問題には、すでに解法があるのでしょうか？難しい問題だと思いますが、少しでも解る方、おねがいいたします。

回答No.2

nana773

わかる方ではないですが１つの案を書きます。
巡回セールスマン問題を解く方法は全てのケースを当たる方法と遺伝的アルゴリズムに代表されるような準最適解を求める方法の２つに分けられます。

全ての可能性を探索するのであれば、最短路を探せば良いのではないでしょうか？道が決まっていると言っても、道がないのであれば最短路ではありません。

GAで解くのであれば、道がないのですから評価値を下げて自然淘汰されるようにすれば良いと思います。

全探索は、数が大きくなるとスーパーコンピュータを使っても解けません。
GAはその戦略によってプログラムの性能が大きく変わる可能性があります。

それと、以上のような問題は同じことをやってる人は多分いると思います。レベルは巡回セールスマン問題とたいして変わらないと思いますよ。

なんか、見当違いをしているような気もするので間違ってたらごめんなさい。

お礼

やはり形が変わっても、巡回セールスマン問題に近道なし！ってことですね！巡回セールスマン問題にいくつかの制限をあたえることによって、なんとか遂次法でとけないかと考えていたのですが、甘かったです。イロイロと試してみます！ありがとうございました！

回答No.1

stomachman

過去の質問に、同じ問題を（すごくいい加減ですけど）扱ったものがあります。（下記URL）

特に、同じ道を同じ向きに２度使う経路は最短経路ではない、という自明の定理を使いますと、総当たりが必要なNP問題(NP=nondeterministic polynomial)に帰着しそうですね。

しかし準最適解を求めるということでしたら、様々な工夫の余地が幾らでもある奥の深い問題でしょう。

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?q=147691

お礼

参考ＵＲＬを拝見させていただきました。なるほど、やはり一概には解けない問題なんですね。最適解をみつけるのは無理そうなので、いかに処理時間の短い、準最適解をみつけるかを考えてみます！ありがとうございました！