厳密解関連

Held-Karpアルゴリズム (1962)

いわゆるbitDP
頂点数 $n$ に対して $\mathcal{O}(n ^ 2 2 ^ n)$ で厳密解を求められる

Held-Karp下界 (1970)

The Traveling Salesman Problem and Minimum Spanning Trees (Held and Karp, 1970)

一般に、枝刈り探索は良い下界（最適解はこの値より小さくならないよという値）があると高速になる

まず、グラフの最小1-木の大きさはTSPの解の下界になっている

1-木とは、頂点1, 2, 3, ..., nで構成されるグラフについて、頂点1を除いた2, 3, ..., nのグラフの全域木と、頂点1からそれ以外の頂点への2本の辺で構成されるグラフのことである（1-木という名前だが木ではない）

ここで、グラフのすべてのハミルトン閉路は1-木であるから、最小1-木は最小のハミルトン閉路よりも小さい（巡回セールスマン問題の下界となる）

最小1-木が運良くハミルトン閉路であった場合、その1-木はTSPの解に等しい

グラフの最小1-木を求めるには、まず頂点1を除いたグラフの最小全域木をクラスカル法などで求め、そこに頂点1に繋がる辺のうち最も短い2つを足せば良く、辺の数 $m$ に対して $\mathcal{O}(m \log m)$ で求められる

Held-Karp下界では、グラフの辺の重みをうまく変えて最小1-木を求めることによってより良い下界を求める

具体的には、グラフの各頂点についてペナルティ $\pi _ 1 , \pi _ 2 , ..., \pi _ n$ を定め、
頂点 $i, j$ を結ぶ辺の重み $c _ {ij}$ を、すべて $c _ {ij} + \pi _ i + \pi _ j$ に変えたグラフで最小1-木を求める

この最小1-木の大きさから $2 \sum _ {i=1} ^ n \pi _ i$ を引いた値は、TSPの下界となっている

なぜなら、上記の方法で辺の重みを変えると任意のハミルトン閉路の大きさは $2 \sum _ {i=1} ^ n \pi _ i$ だけ等しく変わり、
最短路自体は変化しないためである

式で書くと以下の通り

$\ (重み修正グラフのTSPの解) \geq (重み修正グラフの最小1 \unicode{x2d} 木の大きさ) \\ \displaystyle \Leftrightarrow (元のグラフのTSPの解) + 2 \sum _ {i=1} ^ n \pi _ i \geq (重み修正グラフの最小1 \unicode{x2d} 木の大きさ) \\ \displaystyle \Leftrightarrow (元のグラフのTSPの解) \geq (重み修正グラフの最小1 \unicode{x2d} 木の大きさ) - 2 \sum _ {i=1} ^ n \pi _ i \\$