巡回セールスマン問題の計算
小規模な有向コスト行列から、各頂点を1回ずつ訪れて頂点ゼロに戻る最小費用の巡回路を厳密に求めます。
計算結果
結果
—
計算手順
手順を1つずつ、またはまとめて表示できます。現在の入力値を使った計算手順です。
計算方法
Held-Karp 部分集合動的計画法を用い、開始ノードをゼロに固定しながら非対称入力コストを可能にする。
DP[visited,last]=min(DP[visited without last,previous]+cost(previous,last)); close tour to node 0
計算例
4ノードのデフォルト対称行列は、最小ツアーコスト80、たとえば0 → 1 → 3 → 2 → 0 である。
前提条件と入力上の注意
非負のコストの完全なマトリックス、2–14ノード。エッジの欠落、道路データ、交通量、時差窓、車両の制約はない。コストは一貫した数値単位である。 1つの最適なツアーは、いくつかのネクタイのときに表示される。正確な指数関数サイズの検索は、ブラウザの使用に制限されている。
このツールの使い方
自分の値を入力できますか？
はい。入力例をご自身の値に変更してください。結果・計算手順・表・対応する図が入力に応じて更新されます。空欄や無効な値がある場合は結果を消去し、不足した入力を自動的に例の値で補うことはありません。
結果は厳密ですか？
浮動小数点演算を使用し、表示時に丸めています。計算式・前提条件・記載されたデータ精度を確認して結果を解釈してください。
入力内容は送信されますか？
計算はブラウザー内で行います。アカウント・ファイルのアップロード・外部AIサービスは不要です。ページを再読み込みすると入力値は保持されません。
非負コストの小さな有向・無向グラフから、最小費用の経路を求めます。
区間距離、平均速度、休憩を順に組み合わせ、日付付きの到着予定を作ります。
依存関係ネットワークの最早・最遅時刻、総余裕、クリティカル作業を求めます。
広告掲載用スペースです。