巡回セールスマン問題 - Wikipedia

巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。 巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。 詳細[編集] 問題例の大きさは、都市の数で表される。この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題である。なお、この問題の特殊ケースとして考

[k_wizard]

セールスマンが仕事しなければ問題は解決される。/笑ってるかもしれない

[foussin]

eテレ：地球ドラマチック『ハキリアリ…』でもやってた。バックトラッキング…。再放送やるはず。36分以降を要チェック。。。

[boyasan]

でやってたやつ / 地球ドラマチック「驚き！ハキリアリの世界」 - NHK http://www4.nhk.or.jp/dramatic/x/2013-06-22/31/5341/

[yudukikun5120]

“NP困難”

[kabacsharp]

色々と大変ねー　“問題例によっては解が得られないことがあってもよいのであれば、線形計画法と論理木を組み合わせた分枝限定法や”

[Haaaa_N]

>線形計画法と論理木を組み合わせた分枝限定法や、線形計画法と巡回群を組み合わせた切除平面法により、パーソナルコンピュータでおよそ1日以内で厳密解を得られることが多い

[otauwohikki]

“この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。”　　　　　/

[nekotuna]

@petitbass 巡回セールスマン問題の実例を見るとは！NP困難ですね…。健闘を祈る。

[gabuchan]

これはむずかしい