ボトルネック巡回セールスマン問題
巡回セールスマン問題の変種

ボトルネック巡回セールスマン問題（ボトルネックTSP ）は、離散最適化または組合せ最適化における問題です。この問題は、重み付きグラフにおいて、各ノードを1回だけ訪れるハミルトン閉路を見つけ、その閉路の最も重みの高い辺の重みを最小化するものです。 [1]ギルモアとゴモリー（1964）によっていくつかの制約条件が付加されて初めて定式化され、その完全な一般性はガーフィンケルとギルバート（1978）によって確立されました。[1] [2] [3]

複雑

この問題はNP困難であることが知られています。「与えられた長さxに対して、グラフGにおいてxより長い辺を持たないハミルトン閉路が存在するか？」という判定問題はNP完全です。NP完全性は、ハミルトン閉路を見つける問題からの帰着によって直ちに得られます。 [4]

アルゴリズム

ボトルネックTSPから通常のTSP（目標は辺の長さの合計を最小化すること）への別の縮約により、通常のTSPの任意のアルゴリズムをボトルネックTSPの解決にも使用できるようになります。ボトルネックTSPの辺の重みを、同じ相対順序を持つ他の数値に置き換えても、ボトルネックの解は変わりません。さらに、シーケンス内の各数値がそれより小さい数値の合計を超える場合、ボトルネックの解は通常のTSPの解と等しくなります。たとえば、各重みをn i にリセットすることでこのような結果が得られます。ここで、nはグラフの頂点の数、iは重みのソートされたシーケンスにおける辺の元の重みの順位です。たとえば、この変換に続いて、Held-Karpアルゴリズムを使用して、ボトルネックTSPを時間O ( n 2 2 n )で解決できます。[1]

あるいは、重みが最大でxである辺の部分グラフがハミルトン閉路を持つような最小のxを求める二分探索または逐次探索を実行することでも、この問題を解くことができます。この方法で得られる解の実行時間は、ハミルトン閉路を見つけるのにかかる時間の対数倍に過ぎません。[1]

バリエーション

非対称ボトルネック TSPでは、ノードAからBへの重みが、ノードB から A への重みと異なる場合があります (例: 一方向に交通渋滞がある 2 つの都市間の移動時間)。

ユークリッドボトルネックTSP、または平面ボトルネックTSP は、距離が通常のユークリッド距離であるボトルネックTSPです。この問題は依然としてNP困難ですが、他の距離関数よりも多くのヒューリスティックがこの問題に対して有効です。

最大散布巡回セールスマン問題は、巡回セールスマン問題の別のバリエーションであり、最大辺長を最小化するのではなく、最小辺長を最大化するハミルトン閉路を見つけることを目標としています。その応用としては、医用画像の解析や、航空機製造における金属加工工程のスケジューリング（時間的にも空間的にも近接する工程からの熱蓄積を避けるため）などが挙げられます。この問題は、すべての辺長を負にすることで（あるいは、結果を正にするために、十分に大きな定数からすべての辺長を減算することで）、ボトルネックTSP問題の例に変換できます。しかし、この変換は最適解を保存しますが、その解への近似値の品質は保存しません。[1]

メトリック近似アルゴリズム

グラフが距離空間である場合、最大辺重みが最適値の 2 倍以下であるハミルトン閉路を見つける効率的な近似アルゴリズムが存在する。この結果は、 2 頂点連結グラフの平方には常にハミルトン閉路が含まれるというフライシュナーの定理に従う。重みθの辺が 2 連結グラフを形成する最小の値である閾値θを見つけるのは簡単である。するとθ はボトルネック TSP の重みの有効な下限値となる。ボトルネック TSP 自体が 2 連結グラフであり、必然的に少なくともθの重みの辺が含まれるからである。しかし、最大でθ の重みの辺の部分グラフの平方はハミルトンである。距離空間の三角不等式により、そのハミルトン閉路には最大で2 θの重みの辺が含まれる。[5] [6]

この近似比は可能な限り最良のものである。なぜなら、任意の重みなしグラフは、辺の重みを1に設定し、隣接していないすべての頂点間の距離を2に設定することで、距離空間に変換できるからである。この距離空間において比が2よりも良い近似は、元のグラフがNP完全問題であるハミルトン閉路を含むかどうかを判定するために使用できる。[6]

入力が距離空間であるという仮定がなければ、有限近似比は不可能である。[1]

参照

参考文献

  1. ^ abcdef Kabadi, Santosh N.; Punnen, Abraham P. (2007)、「ボトルネックTSP」、Gutin, Gregory; Punnen, Abraham P. (編)、『巡回セールスマン問題とそのバリエーション』、組み合わせ最適化、第12巻、Springer、pp.  697– 735、doi :10.1007/0-306-48213-4_15、ISBN 978-0-387-44459-8。
  2. ^ Gilmore, PC; Gomory, RE (1964)、「1状態変数マシンのシーケンス：巡回セールスマン問題の解決可能なケース」、Oper. Res.、12 (5): 655– 679、doi :10.1287/opre.12.5.655、JSTOR  167772。
  3. ^ Garfinkel, RS; Gilbert, KC (1978)、「ボトルネック巡回セールスマン問題：アルゴリズムと確率解析」、Journal of the ACM、25 (3): 435– 448、doi : 10.1145/322077.322086、S2CID  12062434。
  4. ^ ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論へのガイド」、WHフリーマン、A2.3：ND24、p.212、ISBN 0-7167-1045-5。
  5. ^ Parker, R. Garey; Rardin, Ronald L. (1984)、「ボトルネック巡回セールスマン問題に対する保証されたパフォーマンスヒューリスティック」、Operations Research Letters、2 (6): 269– 272、doi :10.1016/0167-6377(84)90077-4。
  6. ^ ab Hochbaum, Dorit S. ; Shmoys, David B. (1986年5月)、「ボトルネック問題に対する近似アルゴリズムへの統一アプローチ」、Journal of the ACM、33 (3)、ニューヨーク、NY、USA: ACM: 533– 550、doi :10.1145/5925.5933、S2CID  17975253。
「https://en.wikipedia.org/w/index.php?title=ボトルネック_巡回セールスマン問題&oldid=1326528595」より取得