「あなたはセールスマンです。 現在、下の図の印の位置にいます。 これから、印の得意先を1軒づつすべて訪問して、 もとの位置に戻ってこなければなりません。 どのような順序で訪問すれば、歩く距離を最短にできるでしょうか。」 これが、コンピュータプログラムの 難問 として有名な 巡回セールスマン問題 です。 ゲームのつもりで、気軽に 最短巡回コース を考えてみて下さい。 まず、最初に訪問する得意先の印にマウスのカーソルを合わせます。 の色がブルーに変わります。 マウスのボタンをクリックすると巡回経路が描かれます。 順次をクリックし、すべての得意先を訪問し終わったら、 最後にをクリックすれば完了です。 誤ってクリックしてしまった場合は、をダブルクリックすると 巡回経路を消去できます。 次の得意先との距離 (len)、およびこれまでの巡回コースの合計距離 (
巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。 巡回セールスマン問題(じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP)は、都市の集合と各2都市間の移動コスト(たとえば距離)が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める(セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める)組合せ最適化問題である。 問題例の大きさは、都市の数で表される。この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題である。なお、この問題の特殊ケースとして考えられるハミル
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く