最短ハミルトン路問題
全ての頂点を一度ずつ通る最短のパスを求める問題
「パス」なので、始点に戻らない
始点に戻る場合を最短ハミルトン閉路問題という
巡回セールスマン問題の別名が有名。
始点に戻らなくても「戻らないセールスマンなんだ」みたいな捉えられ方をしてるっぽい
Related Pages
- →指数時間アルゴリズム×岩田_陽一×巡回セールスマン問題×最大クリーク問題×幅×グリッドグラフ×pathwidth×半分全列挙×最大独立集合問題×fptアルゴリズム×最小頂点被覆問題×有界探索木×カーネライズ×シュタイナー木問題×包除原理×ハミルトンパス×グラフ彩色問題×彩色数×高速ゼータ変換×畳込み×完全マッチングの個数×完全マッチング×color_coding×k-cycle×bandwidth×cut_&_count×iterative_compression→
- →past3×past3n×past3o×past1m×past1k×最小共通祖先×past1l×クラスカル法×past2h×past2i×past2j×past2k×最小費用流×past2n×平面走査法×PAST3M×巡回セールスマン問題×past2m×past4m×past2l×past4n×past2o×past4o×past1o→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]