全辺巡回・郵便配達問題
バグ・不具合を報告
すべての辺を少なくとも1回通って始点に戻る最小費用の経路を求める。
対象は無向・連結のネットワークの閉巡回です。各辺のコストは0以上、小数第6位までです。
厳密計算は最大120辺・80頂点・奇数次数16頂点です。上限を超える場合は最適値を示しません。
項目を入力・選択してから「計算する」を押してください。
必要な入力・選択は2項目です。
計算結果
—
- 元の辺の合計コスト
- —
- 再走行の追加コスト
- —
- 総通過回数
- —回
- うち追加通過
- —回
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
元費用C=Σ辺コスト。次数が奇数の頂点を抽出し、頂点間の重み付き最短距離を計算。奇数次数頂点の最小費用完全マッチングで得た各ペアの最短路を複製し、追加費用Mを得ます。すべて偶数次数となった多重グラフでEuler巡回を構築し、全ての元の辺IDが1回以上現れること、始点に戻ること、費用C+Mであることを検査します。0費用・多重辺・自己ループを含みます。
辺ID付きの閉巡回、再走行する辺、元・追加・総コスト。
計算例(架空の数値)
3頂点A・B・Cの三角形で辺AB、BC、CAが各1なら最小費用3で各辺を1回ずつ通ります。辺ABだけで費用5ならA→B→Aで総費用10です。
適用対象と限界
全ての対象辺と非負費用が分かり、各辺を両方向に通れる小規模な無向ネットワーク。有向辺・一方通行・時間/車両/容量制約・非連結成分の移動補完・実際の道路通行可否・16個超の奇数次数頂点に対する最適性判定。
採用した方式
- 重み付き最小費用完全マッチング(厳密DP)(v1.0):対象範囲 連結無向、辺120本・頂点80個・奇数次数頂点16個以下、閉巡回/適用地域 global
方法と出典
方法:E1221 undirected-weighted-cpp exact bitmask-dp v1.0。データ記録日:2026-11-14。