宅配便などの最短経路問題について

Question

宅配便のように、すべてのポイントを通る最短経路を求めるアルゴリズムに有名なものはありますか？
ダイキストラかなと思ったんですが、それは必要なルートしか通らないし、ゴールも決まっているため違うかなと思ってます。

Answer 1

「すべてのポイントを通る最短経路問題」は、「巡回セールスマン問題」と呼ばれています。

問題自体がNP困難（現状、多項式時間で解けない）なので、まずは「（時間はかかるかもしれないけど）厳密に解く」か「（より小さな解がある可能性を残した上で）近似的に速く解く」かを選ぶ必要があります。

Comments

[Chikin]

回答ありがとうごさいます。
巡回セールスマン問題はどこかで聞いたことがありました。
時間かけてでも正確な解を得られるもので簡単に実装してみようと思ってます。
もし何かおすすめのサイトなどあれば教えてください！

[coco_bauer]

どのぐらいのポイント数を想定してらっしゃいますか？　ポイントがN個の場合、経路は(N-1)!/2 種類になり、それらの経路帳を全て計算しようとすると、計算回数は(N-1)!/2回になります。N=10なら18万回ですが、N=20だと６垓回(6万ｘ１京回)で毎秒10億経路を計算しても３年近くかかりますよ。許容できる計算時間を考慮して、厳密解にするか、近似解にするかを考えたほうが良いと思います。

[Chikin]

N＝１００で経路(N-1)!/2を計算してみるとありえない数字が出てきました（笑）
最適解を得たかったのですが、あきらめます。
最近近傍法という近似解を求めるアルゴリズムで実装してみました。
1番簡単そうだったので実装したんですが、感覚的に遺伝的アルゴリズムなんかよりは精度が低そうですね。

Answer 2

こんにちは。

有名なアルゴリズムは知らないですが、その問題はたぶん有名な「巡回セールスマン問題」だと思います。
リンク先に幾つかの条件付きアルゴリズムへのリンクがあります。

---

ありゃあゃ、完全にかぶっちゃいました。リロードするべきでした。ごめんなさい。