読書記録
17. 町の散策も勉強 P.149
ここから一筆書きの話に移る。
1735年の「ケーニスベルクの橋の問題」をきっかけに、レオンハルト・オイラーはグラフ理論全体の基礎を作り上げた。
ある無向グラフにおいて、ノードから出るエッジの数を次数(degree)と呼ぶ。
degreeが奇数であるノードの数は必ず偶数個である。
18. 電流のない電磁誘導 P.157
「degreeが奇数であるノードの数は必ず偶数個である」ことを以下のように数学的帰納法で証明した。
m 個のエッジからなるグラフを考え、全ての非負整数 m について命題が真であることを言えば良い。
(i) m = 0 の時、degreeが奇数であるノードの数は0であるため、命題は真である。
(ii) m = k の時、命題が真であると仮定する。
このグラフの (node1, node2) 間にエッジを加えるとする。(node1のdegree, node2のdegree) の遷移は以下の4パターンが存在する。
- (奇数, 奇数) -> (偶数, 偶数)の場合、 #odd_degrees -= 2 より、degreeが奇数であるノードの数は偶数個のまま
- (奇数, 偶数) -> (偶数, 奇数)の場合、 #odd_degrees += 0 より、degreeが奇数であるノードの数は偶数個のまま
- (偶数, 奇数) -> (奇数, 偶数)の場合、 #odd_degrees += 0 より、degreeが奇数であるノードの数は偶数個のまま
- (偶数, 偶数) -> (奇数, 奇数)の場合、 #odd_degrees += 2 より、degreeが奇数であるノードの数は偶数個のまま
よって、m = k + 1 の時、命題は真である。
i, ii より、数学的帰納法により、命題は真であることが証明された。
19. オイラー的か否かという歌 P.164
◉ 無向グラフにおけるオイラーの一筆書きの定理
オイラー路(Eulerian Trail) とは、グラフに含まれるすべての辺(エッジ)をちょうど1回ずつ通るような路のことである。無向グラフにおいては、(i)連結 かつ (ii) degreeが奇数のノードが0か2個であることと同値である。
特に、オイラー回路(Euler Circuit)とは、グラフに含まれるすべての辺(エッジ)をちょうど1回ずつ通り、最初のノードに戻ってくる回路のことである。無向グラフにおいては、(i)連結 かつ (ii) degreeが奇数のノードが0個であることと同値である。
◉ オイラー路の見つけ方
P.169-P.170 で、奇数ノードが2個の場合のオイラー路の見つけ方を図付きでわかりやすく教えてくれている。
まとめると、まず2つある奇数ノードの片方から出発し、もう一方の奇数ノードに辿り着くまでの「メインの道」を一本見つける。次に、その道中で通り損ねたエッジがあれば、そのノードから「寄り道(小さな輪っか)」をして元のノードに戻り、メインの道に組み込む。これを繰り返しすことで、一本の大きなオイラー路が完成する。
なお、奇数ノードが0個の場合は、任意のノードから始めてよく、そのノードに戻ってくるまでの経路が「メインの道」になる。
◉ オイラー路の実装
ノードを複数通ることは許されているため、オイラー閉路ではなく、オイラー回路を考えているという認識。
20. オイラーとサンタクロース P.172
オイラー(1707-1783)の幅広い業績について紹介されている。
21. 今日はごみ収集車が散策する P.180
中国の郵便配達問題(CPP = Chinese Postman Problem, 1962) について。
「重みつき無向グラフにおいて、全てのエッジを通って開始地点に戻ってくる回路(circuit)のうち、重みの合計が最小となるものを見つけよ」
これは、CPPはP問題であり、多項式時間で解ける。
c.f. 循環セールスマン問題 (TSP = Traveling Salesman Problem, 1930s)
「重みつき無向グラフにおいて、全てのノードをちょうど1回ずつ通って開始地点に戻ってくる閉路(Cycle)のうち、重みの合計が最小となるものを見つけよ」これは、NP-hard問題であり、多項式時間で解く方法は見つかっていない。
◉ このグラフがオイラー回路の場合、
全てのエッジを1回ずつ通る経路(一筆書き経路)が、求める経路である。
◉ このグラフがオイラー路ではない場合、
第17章で出たように、奇数のdegreeのnode(= critical nodes)の数は必ず偶数なので、2,4,6,8,... のいずれか。
critical node を二つ一組にペアリングして結ぶ"創業橋渡し運行"を、critical nodeの数が 0 になるまで減らせば良い。(circuitを作る必要があるので、2ではなく0まで減らす。)
TODO: 本当にこれで最適な解が見つかるのか分かっていない。
a*
|
2
|
*c--1--b*--3--d*
* がcritical node。
を例えば (b, c) と (a, d)間に操業橋渡し運行をすると以下になる。
※ (a, d) 間は直接引くことはできないので、経路が最短となる a-b-d を引くことになる。
a
||
22
_1_–||__3_
*c--1--b*--3--d
これを a -- d を重み2+3=5で繋ぐと考えることもできる。
a
| \
1 2 5
/ \| \
*c--1-–b*--3--d
critaical nodeが0つになったため、一筆書きで一周することが可能となった。
よって、この場合のコストは、2 + 1 + 1 + 3 + 5 = 12。
このようにして、操業橋渡し運行のペアあらゆるペアの中で、合計の経路コストが最小になるものを見つける。
つまり、この問題は「critical node が 2n 個与えられ、各node間の重み付き最短経路がわかっている。この中で、コストの和が最小となるような操業橋渡し運行(start, end) のペアn組の作り方を見つけよ」というペアリング問題を解けばよい。
22. ペアリングの時間 P.190
中国の郵便配達問題を解くために、ペアリング問題を解く必要がある。
様々なペアリング問題が紹介されている。アルゴリズム自体の説明はなかった。
◉ マッチング問題とは
集合内の要素同士を結びつける問題。エッジの重みの合計を最大化または最小化する、最適なペアの組み合わせを数学的に導き出す。
◉ 二部的マッチング (Bipartite Matching)**
ノードが2つの異なるグループ(AとB)に分かれており、ペアを組めるのは「グループAのメンバー」と「グループBのメンバー」の間だけ、という制約があるケース。
- ルール: グループ内(A同士、B同士)でのペア結成は禁止
- 例: 求職者と求人企業、学生と研究室、男性と女性
→ 有向グラフの中国の郵便配達問題ではこれを使う。
◉ 一般的マッチング (General Matching)
グループ分けがなく、「誰と誰でもペアになれる」ケース。
- ルール: どのノード同士でも、エッジ(縁)さえあればペアになれる
- 例: 寮のルームメイト決め: 全学生の中から2人組を作る
- アルゴリズム: Blossom Algorithm(エドモンズの花アルゴリズム)* により O(N^3) で解くことができる
-> 無向グラフの中国の郵便配達問題ではこちらを使う
(* Blossom Algorithm は、P アルゴリズムの中で最も難しいものの一つだと言われている)
23. 中国からの手紙 P.199
第21章で紹介された、無向グラフにおける中国の郵便配達問題のアルゴリズムを改めて説明している。
◉ 無向グラフにおける中国の郵便配達問題の応用例
プロッタ(Plotter)は、ペンやカッターを使って、図面やデザインを物理的に描き出す装置である。
プロッタのペンやカッターが「いかに無駄な動きを減らして、連結した図を最短時間で描き終えるか」という最適化においてCPPアルゴリズムを使用している。
◉ 有向グラフにおける中国の郵便配達問題
まずは、有向グラフにおけるオイラー定理。
オイラー路(Eulerian Trail)とは、グラフに含まれるすべてのエッジをちょうど1回ずつ通るような路のことである。有向グラフにおいては、(i) 連結 かつ (ii) 次数のバランスが以下であることと同値である。
- すべてのノードで、indegree = outdegree。
- OR, あるノードで indegree = outdegree + 1, 別のノードで outdegree = indegree + 1, 他の全てのノードは、indegree = outdegree。
オイラー回路(Eulerian Circuit)とは、グラフに含まれるすべてのエッジをちょうど1回ずつ通るような回路のことである。有向グラフにおいては、(i) 連結 かつ (ii) 全てのノードでindegree = outdegree であることと同値である。
これを元に、無向グラフの場合と同じように考えると、
- indegree < outdegree を満たすノードが directed edge の source (根本) となる。
- indegree > outdegree を満たすノードが directed edge の sink (先端) となる。
これを元にどのように操業橋渡し運行を行うべきかを表すペアリング問題を解けば良い。
◉ 混合グラフにおける中国の郵便配達問題
混合グラフ(mixed graph)とは、無向エッジと有向エッジの混じったグラフのこと。
「無向エッジと有向エッジ2本に置き換える」テクニックはここでは使えない。
この問題は、NP-hard に属する。
24. チェックメイト P.212
Knight's Tourというゲームのアルゴリズムと一筆書き経路の説明がされた。
◉ Knight's Tour の解法アルゴリズム
- ナイーブな backtracking
- ウォーンスドルフの規則 = 次に進むべきマス目の候補の中から、その先に進むことのできるマスの数が最も少ないマス目を選び、そこに進む貪欲法
ウォーンスドルフの規則は、実際はうまくいかない場合がある。マスを多くして試すと失敗確率が上がる。
これは、ある程度正解に近い答えを見つけ出すための発見的手法であるヒューリスティックな方法にすぎない。
TODO: ヒューリスティックとは最適解ではなく近似解を見つける時にいうのではないのか?成功率90%のアルゴリズムを近似解と呼んでいいのか?
◉ Knight's Tour における一筆書き経路 (一筆書き)
全ての経路をとおるオイラー路(Euler Trail)は存在しない。
degreeが3(奇数)のノードが4つ存在するから。
全ての頂点をとおるハミルトン閉路(Hamilton Cycle)は存在する。
25. プラトニックな愛? P.227
ハミルトン路 (Hamilton Path) を持つかを判定するアルゴリズムは、NP-complete (= NP && NP-hard) である。
また、ハミルトン閉路 (Hamilton Cycle) を持つかを判定するアルゴリズムも同じく NP-complete である。
◉ 正多面体とハミルトン閉路
まず、正多面体は五種類しか存在しない。
正四面体、正六面体、正八面体、正十二面体、正二十面体である。
これら5種類の正多面体は、すべて「ハミルトン閉路(およびハミルトン路)」を持っている。
26. 表記上の問題 P.237
P vs NP について説明されている。
ハミルトン問題は「決定問題」である。
NP問題 (Non-determistic Polynomial, 非決定多項式)とは、決定問題のうち、「答えがYesであるときに限り、それを証明する証拠(リスト)があれば、NP時間で正しいと確認できる」もの。
NP-hard問題のうちのどれか一つを NP時間で解く解放が見つかったら、全てのNP問題について、NP時間で解けるアルゴリズムが見つかることになり、N = NP が言える。
「ある問題Aの解法アルゴリズムを応用すればNP-hard問題Bが NP時間で解ける」ならば、Aは少なくともBより難しいため、問題AはNP-hardであると言える(意訳)
- 例として A = 「各エッジを最大1回まで使用する、正負の重み付きグラフの最短経路問題」→ B = 「ハミルトン閉路が存在するかを判定する問題」の変換例が挙げられていた
- TODO: 本来のNP-hard問題の定義は、「あらゆる NP問題を多項式時間で帰着(reduction)させることができる」であった。本当にこれを満たすのか考える
最初に考えられたNP問題は、「充足可能性問題」であった。
◉ ref. 自分で昔P vs NPを調べた時のまとめ記事
27. 巡回セールスマンのためだけではなくて P.250
◉ 巡回セールスマン問題(Traveling Salesman Problem, TSP)とは
巡回セールスマン問題 = 重み付き無向グラフにおいて、全てのノードを一度ずつ通り、出発点に戻る最短経路を求める問題
これは、順回路問題の一種である。
◉ 巡回セールスマン問題の解き方
まず、全てのnode間の組み合わせについて最短経路(all pair shortest path)を求め、これら全てのエッジを貼ったグラフXを考える。(前処理*)
このグラフX上で、出発ノードから始まるハミルトン閉路(Hamilton Cycle)のうち、重みの合計が最小であるものを見つければ良い。だが、残念ながら、このようなグラフで最短のハミルトン閉路を見つける問題は、NP-hard である。
NOTE: 一般的に、巡回セールスマン問題は、あらゆるノード間にエッジが存在する問題、つまり(前処理*)終了後のグラフを考える場合が多いようだ。以降その前提で記入する。
1️⃣ 本書では、再隣接ヒューリスティック解法が紹介されていた。これは、「グラフXの探索時、まだ訪れていないノードに繋がるエッジの中で、最も重みが小さい経路を選んで進む」貪欲法を用いることで近似解を求める方法である。
しかしこれは、Final Stretch Problem、つまり「最後の数手で取り残した遠くのノードを訪れることでコストが一気に増える問題」が発生しうる。そこで、「一度出来上がったルート上で、あるノードを別の二つのノードの間に挟み込まれる場所にへ移動してみて、コストが小さくなるならそれを採用する」という修正作業を繰り返す 2-opt法によって、さらに最適化することができる。ただし、これで到達可能なのは、局所最適解である。
2️⃣ 近似解ではなく、最適解を求めたい場合には、bit-DP を使ったO(n^2 * 2^n)時間かかる実装をすることになる。(TODO: 実装してみる)
◉ 巡回セールスマン問題の現実世界での応用例
半導体基盤の製造過程で、ロボットが穴を開けていく経路を最適化できる。
なお、第23章で登場したプロッタの例は、「経路(=edge)を描く」場合であり、半導体基盤のロボットは、「点(=node)を描く」場合である。
28. 少ないは多い P.264
(この章から難しくなってきた
)
緩和法(relaxation)を用いて、最適解の"範囲" (下限 <= 最適解 <= 上限) を求められる。
◉ TSP、つまり「重みつき無向グラフにおいて最短経路となるハミルトン閉路」の下限の求め方
ハミルトン閉路の緩和法として、1-木(1-tree)を考える。
1-木とは、与えられたグラフにおいて、ある頂点 𝑣 (rootと呼ぶ) を除いた残りの頂点で最小全域木を作り,𝑣 と他の頂点との間にある辺のうち,
重みが最小の2本を選んで接続して得られるグラフである。[追記] 1-木の定義には「重みが最小の」という部分は入っていない。しかし、最小1-木であれば、必ず「重みが最小の」2本になっているので、探索時に「重みが最小の」2本を選んで接続すれば良い。
ここで、以下が言える。
- ① 全てのハミルトン閉路は、最小1-木である (TODO: 証明)
- かつ、どのノードを特別ノードとして1-木を作ったとしても、それがハミルトン回路であれば、それはそのグラフ上の最短ハミルトン閉路(の一つ)である (TODO: 証明)
- あるグラフにおいて、
存在するハミルトン閉路の数 << 存在する1-木の数である- 1-木では、MST と vに接続する最小の2辺、にtieが存在するから
- ② 存在する1-木の中で最短経路のもの(= 最小1-木)を見つけるのは、定数時間で可能
- 各rootに対して、最小全域木を見つけるだけなので、貪欲法が使えるから
- つまり、NP-hard である「最短経路のハミルトン閉路の発見」より圧倒的に早くできる
①,②より、最小1-木の経路距離 <= ハミルトン閉路の最短経路距離が言える。
1-木の最短経路距離は P時間で求められるため、妥当な時間で、ハミルトン閉路の最短経路距離の下限を求められることがわかる。
29. 150パーセントの P.271
前章では、1-木を使うことで、ハミルトン閉路の最短距離の最適解下限をP時間で求められることがわかった。
本章では、三角不等式が成立するという制約下で ハミルトン閉路の最短距離の最適解の1.5倍以下の経路を確実に求められる、クリストフィードのアルゴリズムが紹介されている。
三角不等式(Triangle Inequality)とは、**「2点間を直接結ぶ距離は、他の点を経由する距離よりも短い(または等しい)」**というルールです。$$Cost(A, D) \le Cost(A, B) + Cost(B, C) + Cost(C, D)$$
◉ クリストフィードのアルゴリズム (1976)
1️⃣ 適当なノードを特別ノードとする最小の1-木を見つける
これは、あるノードを決めうちで特別ノードとしてしまい、残りは貪欲法で最小全域木を求めれば良いので P時間で可能。
これをまず求めるルートの土台として使う。
2️⃣ 3️⃣ 最小1-木の辺 と そこに加えたマッチングの辺 の全てを通る、最小のオイラー回路を見つける。
中国の郵便配達問題と同じ処理を行う。見つかった最小のオイラー回路は、全てのノードを通るが、同じノードを複数回通る可能性がある。
第21-23章で説明された通り、degreeが奇数のノード(常に複数個ある) のマッチング問題を解き、ペア間に(操業橋渡し運行の)エッジを引く。
この時点で、見つかったオイラー回路の経路距離 <= 最短ハミルトン閉路の経路距離 * 1.5 が成立する。
"1.5"の証明
① 第28章でも述べられたように、最小1-木の経路距離 <= 最短ハミルトン閉路の経路距離。
② 経路距離が最短となるハミルトン閉路を考える。
このハミルトン閉路の中で、次数が奇数のノードだけを通る回路を考えると、これは全てのノードを通るハミルトン閉路を"ショートカット"した回路であるから、三角不等式より、(ODN = odd degree node)
cost(ODN1->ODN2) + cost(ODN2->ODN3) + cost(ODN3->ODN4) + cost(ODN4->ODN5) + ...cost(ODN-last, ODN1) <= 最短ハミルトン閉路の経路距離
ここで、
M1 = cost(ODN1->ODN2) + cost(ODN3->ODN4) + cost(ODN5->ODN6) + ... + cost(ODN-last-1>ODN-last)M2 = cost(ODN2->ODN3) + cost(ODN4->ODN5) + cost(ODN6->ODN7) + ... + cost(ODN-last->ODN1)
と見ると、M1, M2 のそれぞれに、マッチングペアが一式揃っていることが分かる。
よって マッチング合計コスト M1 + マッチング合計コスト M2 <= ハミルトン閉路の経路距離
わかっていることをまとめると、
マッチング合計コスト M1 + マッチング合計コスト M2 <= ハミルトン閉路の経路距離min(マッチングコスト) <= マッチング合計コスト M1min(マッチングコスト) <= マッチング合計コスト M2
これより、 min(マッチングコスト) <= 最短ハミルトン閉路の経路距離 * 0.5 が言える。
①②より、見つかったオイラー回路の経路距離 <= 最短ハミルトン閉路の経路距離 * 1.5 である。
4️⃣ 同じノードを複数回通らないように、ショートカットを行う
求めたいのはハミルトン閉路であるため、同じノードを複数回訪れてはいけないため。
このショートカットにより、ハミルトン閉路が完成する。
ルートを辿ってみて、あるノードにおいて、次に進むノードがすでに訪問済みである場合、そのノードを飛ばしたその次の訪問していない次の頂点へと直接向かう。
例えば、A -> B -> C -> B(2回目) -> D -> Aの場合、A -> B -> C -> D -> A にする。
ただし、1回目のBをスキップして、A -> C -> D -> Aとする場合の方が、コストが小さくなることはありうる。しかし、これは気にしなくて良い。なぜなら、クリストフィードのアルゴリズムは、「可能な限り最短経路(つまり局所最適)を見つける」ためのものではなく、「どんなに悪くても最適解の1.5倍以内に収まることを保証する」ためのものだからである
前提条件より、三角不等式が成立しているから、完成したハミルトン閉路 <= 見つかったオイラー回路の経路距離
よって、完成したハミルトン閉路 <= 見つかったオイラー回路の経路距離 <= 最短ハミルトン閉路の経路距離 * 1.5であるから、完成したハミルトン閉路 <= 最短ハミルトン閉路の経路距離 * 1.5 が言える。
◉ クリストフィードのアルゴリズムで、最適解のほぼ1.5倍の経路が見つかるケース
例えば以下のようなグラフが与えられた場合、横幅を大きくすると、見つかったルートの経路 = ハミルトン閉路の経路 * 1.5に近づく。
30. ボンサイ P.279
本章では、分枝限定法(Branch and Bound)による枝刈り(pruning)を考える。
簡単にいうと、「ある選択をした時点で、現在見つかっている最適値の暫定解 <= その選択以降に見つかる最適値の下限であれば、その選択以降の候補をひとまとめに切り捨てる」というものである。
その選択以降に見つかる最適値の下限の見つけ方はさまざまな方法があり、本章では、TSP問題の厳密な最適解を効率よく見つける二つの方法を以下のグラフ例を用いて紹介されている。
1️⃣ 全てのノードを総当たりで試すDFSにおいて分枝限定法を用いる方法
TSP を DFSで総当たりで厳密な最適解を見つける際の効率化について考える。
あるノードまで進んだ時点で、以下を満たす最小の1-木を考える。
- TSPの出発地点のノードを特別ノードとする
- 今までに通ったエッジを含む (つまり、特別のノードと最小全域木を結ぶエッジ2つのうちの1つは定まっていることになる)
こうして求まる最小1-木の経路距離は、ここまでの選択以降に見つかる最短経路距離の下限である(TODO:証明)。 もし、これが現在の暫定最適値よりも大きい場合には、探索をここで打ち切りにする。
2️⃣ あるノードを特別ノードした1-木を見ていく中で分枝限定法を用いる方法
前提となるアルゴリズムは、 「あるノードを特別ノードとする全ての1-木を考える。この中には最短ハミルトン回路が必ず含まれるので(第28章で述べた)、これらを総当たりすれば最短ハミルトン回路が見つかる」というもの。
ノード1を特別ノードとして考えた以下の最小1-木から始めてみる。
なお、探索中はこのノード1を特別ノードとして固定する。すると、以下のような最小1-木が見つかる。
この1-木では、ノード 3 が最も高いdegreeを持つ。したがって、このノード3から生えるエッジに関して**排他的な分枝(Branching)**を行うのが最も効率が良い。ちなみに他のノードで行うことも非効率だが可能ではある。
ノード3から出るエッジに注目して、存在する1-木を3つの重複しない集合に分割すると (TODO: ベン図を書いてみる)
- 3-1禁止
- 3−1固定、3-5禁止
- 3−1固定、3−5固定、他の3-*禁止
このそれぞれについて、特別ノードをノード1とする最小1-木を作る。
- 3-1禁止
これを満たす 特別ノードが1の最小1-木は、ハミルトン閉路(距離21)となる。これを暫定ベストとし、ここで STOP
- 3−1固定、3-5禁止
これを満たす 特別ノードが1の最小1-木は、ハミルトン閉路(距離20)となる。これで暫定ベストを更新し、ここで STOP
3−1固定、3−5固定、他の3-*禁止
これを満たす 特別ノードが1の最小1-木は、非ハミルトン閉路(距離19)であるので、探索を続ける。これはノード5が最大のDegreeを持つので、次はこのノードからエッジに関して排他的な分枝を行う。5−3がすでに固定されていることに留意して、
- 5−3固定、5-4禁止
- 5−3固定、5−4固定、他の5-*禁止
このそれぞれについて、前述の3−1固定、3−5固定、他の3-*禁止と合わせ、特別ノードをノード1とする最小1-木を作る。
- 3−1固定、3−5固定、他の3-*禁止 + 5−3固定、5-4禁止
これを満たす 特別ノードが1の最小1-木は、非ハミルトン閉路(距離20)となる。暫定の最適値 20 = 下限 20となるので、ここでSTOP
- 3−1固定、3−5固定、他の3-*禁止 + 5−3固定、5−4固定、他の5-*禁止
これを満たす 特別ノードが1の最小1-木は、非ハミルトン閉路(距離22)となる。暫定の最適値 20 < 下限 22となるので、ここでSTOP
これにて、ノード1を特別ノードとする全ての1-木を探索し終わり、その中で最短のハミルトン経路(20)を発見した。これは、元のグラフの全ての最短のハミルトン経路(の一つ)である。
31. 全然,プラトニックでない P.291
グラフを凸多面体に写像する。
凸多面体上では、分枝カット法(Branch and Cut) における「下限を求める」に相当する操作を、線形計画法(LP)を使いP時間で求めることができる。(LP緩和という)
これにより、非常に大きな巡回路問題の厳密な最適値をNPではあるが高速に求めることができる。
このように、多面体論的組合せ論 (Polyhedral combinatorics) には、かなりの成果があり。巡回路問題やその他多くの問題を解くために現在存在する最良のアルゴリズムは、多面性組み合わせ論に基づいている。
(例) 巡回セールス問題
例えば、巡回セールスマン問題(TSP)の場合、すべての「ハミルトン閉路」は多次元空間上の点(ベクトル)として表現され、それらを包み込む最小の凸多面体、すなわち TSP多面体 (Traveling Salesman Polytope) を考えることになる。この多面体は、都市数が増えるにつれて頂点や面の数が爆発的に増加し、正多面体とは比較にならないほど複雑でトゲトゲとした「怪物的」な形をしている。
通常、私たちが「多面体」と聞いて思い浮かべるのは、正四面体や立方体といった、対称的で美しい**正多面体(プラトニック・ソリッド)**だろう。これらは頂点や面の数が限られており、構造も極めて単純だ。しかし、組合せ最適化の世界で扱う多面体は、その名に反して全くプラトニックではありません。
◉ Pseudo code
Geminiに書いてもらった。雰囲気をつかみたい。
def _branch_and_cut(self, current_constraints):
"""
分枝カット法の再帰関数
【インスタンス変数】self.constraints
現在の凸多面体を定義する制約式。
再帰の過程でカット(妥当不等式)が追加され、形が更新されていく。
【インスタンス変数】self.current_best
これまでに見つかった最短ルートの距離(上界)。
全ての再帰枝で共有され、これより悪い枝をバッサリ刈るために使う。
"""
# 1. 限定操作 (Bounding): LP緩和を解いて「下界値 (lower_bound)」を得る
# 凸多面体上の計算。これがその枝における「理論上の最小見積もり」となる
lp_solution = solve_lp_relaxation(current_constraints)
lower_bound = get_objective_value(lp_solution)
# 2. 枝刈り (Pruning):
# 現在の見積もり(lower_bound)が、すでに手元にある「現在のベスト(current_best)」
# よりも悪いなら、この先をどれだけ精密に彫刻しても無駄なので探索を中止する
if lower_bound >= self.current_best:
return
# 3. 切除平面フェーズ (Cutting Plane): 多面体を削って下界値を高める
node_cuts = [] # この階層(ノード)で追加したカットを記録するリスト
while True:
# 緩和解(小数の解)を凸多面体から切り離す「壁(妥当不等式)」を探す
cut = find_violated_valid_inequality(lp_solution, self.cities)
if cut:
# この探索ノードの制約に「壁」を追加して、多面体をタイトにする
current_constraints.add(cut)
node_cuts.append(cut) # ロールバック用に保存
# 削られた新しい多面体上でLPを再計算
lp_solution = solve_lp_relaxation(current_constraints)
lower_bound = get_objective_value(lp_solution)
# 多面体を削ったことで見積もり(lower_bound)が厳しくなり、
# current_best を超えた場合はその時点で枝刈り
if lower_bound >= self.current_best:
for c in node_cuts: current_constraints.remove(c) # 追加した壁を戻す
return
else:
# これ以上、現在の多面体を効率的に削る壁が見つからない
break
# 4. 整数性の確認
if is_integer_solution(lp_solution):
# 完全に 0 または 1 の頂点(正しい巡回路)に到達
if lower_bound < self.current_best:
# 【インスタンス変数の更新】
# より良いルートを発見したので、全体で共有する「現在のベスト」を更新
self.current_best = lower_bound
self.best_solution = lp_solution
# 親に戻る前に、このノードで追加した壁をすべて削除(ロールバック)
for c in node_cuts: current_constraints.remove(c)
return
# 5. 分枝 (Branching): 整数でないエッジで多面体を2つに分割
# 答えが「プラトニックでない(小数の点)」場合、空間を割って追い詰める
edge = select_fractional_edge(lp_solution)
# 左右の枝(エッジを使う場合・使わない場合)を再帰的に探索
for value in [0, 1]:
# 制約を追加(Do)
fixed_constraint = current_constraints.add_fixed_edge(edge, value)
# 子ノードへの再帰。
self._branch_and_cut(current_constraints)
# 制約を削除(Undo / ロールバック)
current_constraints.remove_fixed_edge(fixed_constraint)
# 最後に、このノードの切除平面フェーズで追加した壁をすべて削除して親に戻る
for c in node_cuts:
current_constraints.remove(c)
分枝カット法 (Branch-and-Cut法)
大規模な整数計画問題を解くための高性能な厳密解法であり、分枝限定法(Branch-and-Bound)に切除平面法(Cutting Plane Method)を組み合わせた手法。探索木の各ノードで緩和問題を解く際、カット(妥当不等式)を生成・追加して連続緩和の解を切り落とすことで、下界値を改善し、探索効率を劇的に向上させる。
妥当不等式(Valid Inequality)
数理最適化、特に整数計画問題(Integer Programming)において、「目的の整数解(実行可能解)を一つも切り落とすことなく、整数解ではない不要な候補(線形緩和の解)を切り捨てるために追加する制約式」のことです。
切除平面法(Cutting Plane Method)などにおいて、元の問題の連続緩和解(LP緩和)が整数制約を満たさない場合に、より真の最適解に近い解を得るために加えられます。
線形緩和(LP緩和)
解くのが難しい整数計画問題において、「変数は整数でなければならない」という制約を「変数は実数でもよい(範囲内)」に緩和し、線形計画問題として解く手法です。NP困難な最適化問題に対して高速に最適値の上下界を推定し、近似解を得るために分枝限定法などで広く利用されます。
32. 巡回セールスマンの成功物語 P.301
巡回セールス問題に関わる歴史が駆け足で紹介されている。






