Comments
Description
Transcript
数理計画（後） - Info Shako
数理計画（後）
M. Shigeno
1
∗
グラフ・ネットワーク
1. グラフ (graph) G = (V, A)：2 つの集合からなる離散構造
• V : 頂点（あるいは接点，点，vertex, node）の集合
• A : 枝（あるいは辺，弧，線，arc, branch, edge）の集合
• 頂点と枝の接続関係（枝に対する端点，始点／終点 ：枝 a = (v, v ′ ) のとき，a の始点は v, 終点は v ′ ．
このとき，枝 a は v に接続しているという．また，頂点 v と v ′ は隣接しているという．
）
2. グラフは図に表すとわかりやすい．
v
¶³ a
µ´
始点
-
3́
´
HH ¶³
´
j
v
* µ´
©
Q
©©
Q
Q
s
v′
¶³
H
µ´
終点
3. 有向グラフ／無向グラフ 各枝 a = (v, v ′ ) で，v と v ′ の順序を無視したグラフを無向 (undirected) である
という．無向グラフに対して，v と v ′ の順序を考慮したグラフを有向 (directed) であるという．有向グラフ
の枝を有向枝，無向グラフの枝を無向枝ともよぶ．グラフを図示する際，無向枝は矢線の代わりに線分を用
いる．
4. 特別な枝として，始点と終点が同じであるような枝 a をループ (loop)（あるいは自己閉路）といい，相異
なる 2 本の枝 a1 = (v, v ′ ), a2 = (w, w′ ) が，v = w, v ′ = w′ のとき，この 2 本の枝を多重枝 (multiple arc)
（あるいは平行枝，並列枝，parallel arc）という．ループや多重枝のないグラフのことを単純グラフ (simple
graph) という．以下，断りのない限り，単純グラフを仮定する．
例 1.1 以下の集合と接続関係で与えられるグラフを図示せよ．ループや多重枝は存在するか確認せよ．さ
らに，始点と終点を区別しない無向グラフとして図示せよ．
V = {v1 , v2 , v3 , v4 , v5 }, A = {a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 }
a1
a2
a3
a4
a5
a6
a7
a8
始点
v1
v1
v1
v2
v4
v4
v5
v5
終点
v3
v5
v5
v2
v3
v5
v4
v2
∗ この資料の誤字脱字を見つけたり，わかりにくい文章であることの指摘，改善点など教えて頂けるとうれしいです．授業中に指摘して頂
くのがベストですが，復習の時に見つかったものは，[email protected] までお願いします m( )m
1
5. 基本的用語
路 (path，walk) 隣接関係にある頂点と枝の交互列
• 路の始点と終点
• 有向路
• 到達可能
• 単純な路 (simple path) — 同じ枝を 2 回以上通らない
• 初等的な路／道 (elementary path) — 同じ頂点を 2 回以上通らない
閉路 (cycle) 少なくとも 1 本の枝を通り，始点と終点が一致する路で，始点と終点以外は同じ頂点を繰り返
さない路
• 有向閉路
連結グラフ (connected graph) どの２頂点間にも路が存在
木 (tree) 連結で閉路をもたないグラフ
• 全域木／全張木 (spanning tree)
頂点の次数 (degree) 完全グラフ (complete graph)
例 1.2 図 1 のグラフにおいて，
(a) v1 を始点，v6 を終点とする路を考える．
i. 路 P1 = (v1 , a1 , v2 , a3 , v4 , a6 , v3 , a5 , v2 , a3 , v4 , a7 , v6 ) は，
であるが，
ii. 路 P2 = (v1 , a1 , v2 , a4 , v5 , a8 , v3 , a5 , v2 , a3 , v4 , a7 , v6 ) は，
ではない．
であるが，
ない．
iii. 路 P3 = (v1 , a1 , v2 , a4 , v5 , a9 , v6 ) は，
である．
iv. 路 P4 = (v1 , a1 , v2 , a5 , v3 , a8 , v5 , a9 , v6 ) は，
(b) 路 P5 = (v2 , a4 , v5 , a8 , v3 , a5 , v2 ) は
であるが，
である．
a3- vm
vm
2
4
a¶
@ a7
6
a¡
Sa4
µ 6
1¡
@
¶
S
R
@
¡
a5 S ¶
vm
vm
1
6
¶S
@
µ
¡
a@
a¡
¶ S
2
9
/
S
w ¡
@
R ¶
m
¾
m
v3
a8 v5
図 1: グラフの例
2
ではない．
では
6. グラフの頂点や枝に数量，例えば，頂点に需要／供給や，枝に距離／費用／時間などが与えられているとき，
グラフと数量をあわせてネットワーク (network) とよぶ．
7. ネットワーク上の最適化問題の例
最短路問題 (shortest path problem)*
入力: 有向グラフと各枝の長さ．出発点となる頂点（始点）．
出力: 始点から到達可能な各頂点への長さ最小の有向道をそれぞれ出力．
最小木問題 (minimum spanning tree problem)*
入力: 連結な無向グラフと各枝の費用．
出力: 枝の費用の和が最小となる全域木．
巡回セールスマン問題 (traveling salesman problem:TSP)*
入力: 完全グラフと各枝の費用.
出力: 枝の費用の和が最小となる巡回路（すべての頂点をちょうど１度ずつ通る閉路）
最大流問題 (maximum flow problem)
入力: 有向グラフと各枝の容量．入口となる頂点と出口となる頂点．
出力: 容量制約と流量保存則を満たし，入口から出口に流れる量を最大にするフロー．
容量制約： 各枝のフロー量は容量を超えない．
流量保存則： 入口と出口以外ではフローが消失したり，湧いたりしない．
最小費用流問題 (minimum cost flow problem)
入力: 有向グラフと各枝の容量と単位フロー量あたりの費用．各頂点の需要／供給量．
出力: 容量制約を満たし，各頂点で需要／供給を満たすフローのなかで各枝のフローに対する費用の和を最小
とするようなフロー．
演習問題
問題 1:
1. 連結なグラフの枝数は (頂点数 −1) 以上であることを示せ．
2. 閉路を含まないグラフの枝数は (頂点数 −1) 以下であることを示せ．
以上より，頂点が k 個の木の枝数は k − 1 本であることを示せ．
問題 2: 任意のグラフにおいて，次数が奇数の頂点の個数は偶数であることを示せ．
3
問題 3: 頂点が n 個のグラフで，どの頂点の次数も
n−1
2
以上のとき，グラフは連結であることを示せ．
問題 4: 無向グラフ G に対して，任意の２頂点間の枝で G にない枝を集めてできたグラフを G の補グラフという．
G と G の補グラフの少なくともどちらか一方は連結であることを示せ．
問題 5: 以下が同値であることを示せ．
1. G は木である．
2. G は閉路を含まないが，G にない枝を１本加えると閉路ができる．
3. G 上の任意の２点間に唯一の道がある．
4. G は連結であるが，G から任意の枝を 1 本なくすと，連結でなくなる．
問題 6: 有向グラフが与えられたとき，行を頂点に，列を枝に対応させ，(v, a) 要素を，
(枝 a の始点が頂点 v のとき)
1
(v, a) =
−1 (枝 a の終点が頂点 v のとき)
0
(それ以外)
と決めた行列でこのグラフを表すことができる．この行列を接続行列 (incidence matrix) という．接続行列
の任意の部分正方行列の行列式は 0 か ±1 であることを帰納法を用いて示せ．
• 部分行列に零列ベクトルが存在するとき．
• 部分行列に非零要素をちょうど 1 つもつ列ベクトルが存在するとき．
• 部分行列のすべての列ベクトルが非零要素を 2 つずつもつとき．
に場合分け．
問題 7: あるマネキン会社に，４つの店から依頼があった．その日勤務可能なアルバイターはちょうど４人．各
アルバイターを各店に派遣するには，以下のような交通費がかかる．交通費はマネキン会社の負担である．
つくば店
土浦店
牛久店
取手店
大仏さん
800
280
200
350
学園さん
650
550
800
1100
霞ヶ浦さん
700
300
320
400
東京さん
1200
850
850
750
さて，交通費を最小にしてアルバイターを派遣したい．
（各店に一人ずつ派遣する）この問題を整数条件付き
の最小費用流問題で表せ．
4
問題 8: あるマネキン会社に，６つの店（A, B, C, D, E, F) から依頼があった．その日勤務可能なアルバイター
はちょうど７人 (a, b, c, d, e, f, g)．各アルバイターを各店に派遣する時，仕事によって，派遣可能かどう
かが決まる．それぞれの店に派遣できるアルバイターは，以下の通りである．
A店
a
b
B店
c
d
C店
c
d
D店
c
d
E店
c
d
F店
c
d
c
e
f
g
f
このとき，どのアルバイターをどの店に派遣すればよいか．
（各店に一人ずつ派遣する）この問題を整数条件
付きの最大流問題で表せ．
問題 9: n 個の供給地と m 個の需要地があり，供給地 i (i = 1, 2, . . . , n) の供給量 si ，需要地 j (j = 1, 2, . . . , m) の
需要量 dj がわかっている．さらに，供給地 i と需要地 j 間の 1 単位あたりの輸送コスト cij がわかっている．
このとき，輸送コストの総和を最小化するように，供給地から需要地への輸送方法を決定する問題を輸送問
∑n
∑m
題という．ただし， i=1 si = j=1 dj とする．この問題は供給地 i から需要地 j への輸送量を変数 xij と
定義すると，以下のように定式化できる．
最小化
条件
∑n
∑m
i=1
j=1 cij xij
∑m
j=1 xij = si
∑n
i=1 xij = dj
(i = 1, 2, . . . , n)
xij ≥ 0
(i = 1, 2, . . . , n; j = 1, 2, . . . , m)
(j = 1, 2, . . . , m)
1. 輸送問題は最小費用流問題の特殊ケースであることを示せ．
2. 最小費用流問題はグラフの変形をおこなうことで，輸送問題に変形できることを示せ．
（与えられたグ
ラフの各枝 (u, v) に対し，新しい頂点 vuv をグラフに加え，枝 (u, v) を 2 本の枝 (u, vuv ), (v, vuv ) に置
き換える．枝 (v, vuv ) の流量はもとの枝 (u, v) の容量制約に対するスラック変数に対応させる．
）
5
最短路問題
2
2.1
問題の定義
カーナビゲーションシステムや，電車経路案内のソフトにみられるように，複雑な交通ネットワークにおいて，
出発点から目的地まで多くの経路の中から最も早い経路や費用のかからない経路を探すことは馴染みになっている．
与えられたネットワーク上で距離（時間・費用）が最小となる 2 点間の経路を求める問題を最短路問題 (shortest
path problem) という．最短路問題は多くの応用例をもつのみならず，他の組合せ最適化問題の部分問題としても
扱われることから，1950 年代後半より多くの研究者により，理論面，実用面ともに議論され様々なアルゴリズム
が提案されてきた．
グラフ上に始点（出発点）が与えられたときに，始点から各頂点への距離が最小となる経路を求める問題を 1
始点最短路問題 (single source shortest path problem) という．ここで，有向路の長さとはその有向路が含むすべ
ての枝の長さの和で定義される．また，有向閉路に含まれる枝の長さの和が負であるとき，負閉路という．
1 始点最短路問題
入力: 有向グラフ G = (V, A) と各枝 a の長さ l(a)．出発点となる頂点（始点）s．
出力: s から到達可能な各頂点への長さ最小の有向路とその長さ（距離）をそれぞれ出力．ただし，始点 s か
ら到達可能な負閉路が存在する場合は，その負閉路を 1 つ出力．
頂点 v から頂点 v ′ への有向路のうち，長さ最小のものを v から v ′ への最短路 (shortest path) という．v から v ′
への有向路が存在しないとき，v から v ′ への有向路の長さを +∞ とする．
始点を定めず，すべての頂点間の最短経路を求める問題もある．
全頂点対間最短路問題
入力: 有向グラフ G = (V, A) と各枝 a の長さ l(a)．
出力: 各頂点の順序対 [v, v ′ ] に対して v から v ′ に到達可能なとき，長さ最小の有向路とその長さ（距離）をそ
れぞれ出力．ただし，グラフ G に負閉路が存在する場合は，負閉路を 1 つ出力．
• 到達可能な負閉路が存在したとき，なぜ，最短路を求めないのか．
以下のグラフの s から v5 への最短路は？
0
vi
vi
4¾
3
@
µ0
¡
−1
@
R ¡
10
- vi
si10 - vi
2
HH
©
* 5
©
©
H
jvi
©©1
1 H
1
一般には頂点 v から頂点 v ′ への長さ最小の有向 道 を求めよという問題は，N P-困難1 である．
• 最短路となる有向路は常に初等的（有向道）であるか．
• 到達点となる頂点（終点）が与えられているとき，各頂点から終点への最短路を求めよという問題は 1 始点
最短路問題と本質的に同じか．
1 計算機を使って効率よく解く方法がわからない問題，難しい問題．問題のサイズが大きくなると，計算機で解こうとしてもすごく時間が
かかってしまい，卒業までに終わらないかもしれない問題のグループ．詳しくは，
「計算機科学」でちょろっと．もっと詳しくは，大学院の「離
散最適化理論」で．(^o^)
6
2.2
基本的性質
以下に，アルゴリズムの設計に必要ないくつかの基本的性質をあげる．
定理 2.1 有向グラフ G において，各頂点 v ∈ V に対し，d(v) を s から v へのある有向路の長さとする．ただし，
d(s) = 0 とする．このとき，d が最短路の長さであることの必要十分条件は，
d(v ′ ) ≤ d(v) + l(a), ∀a = (v, v ′ ) ∈ A
(1)
が成り立つことである．
[必要性] 対偶を示す．ある枝 â = (v̂, vˆ′ ) で，d(vˆ′ ) > d(v̂) + l(â) とする．このとき，d(v̂) を与える s か
ら v̂ への有向路を Pv̂ とすると，Pv̂ に枝 â を加えた s から vˆ′ への有向路は，d(vˆ′ ) を与える有向路よりも長さは
証明:
短い．よって，d(vˆ′ ) は最短路の長さではない．
v̂
i
3 Sâ
S
w iˆ′
v
µ
Pv̂
si
図 2: 必要性の対偶の証明．s から vˆ′ への有向路として，â を経由する路をとれる．
[十分性] s から任意の頂点 v̂ への任意の有向路 P = (v0 v1 v2 . . . vk−1 vk ) （ただし，v0 = s, vk = v̂ ）を考える．
不等式 (1) より，この有向路上の各枝 (vi , vi+1 ) では，
l(vi , vi+1 ) ≥ d(vi+1 ) − d(vi )
が成立している．よって，有向路 P の長さに関しては，
k−1
∑
i=0
l(vi , vi+1 ) ≥
k−1
∑
(d(vi+1 ) − d(vi )) = d(vk ) − d(v0 ) = d(v̂)
(2)
i=0
が得られる．すなわち，d(v̂) よりも短い長さの s から v̂ への有向路は存在しないので，d(v̂) を決める s から v̂ へ
の有向路が最短路となる．
不等式 (1) は三角不等式と呼ばれる．以下，1 始点最短路問題において，始点 s から頂点 v への最短路の長さを
d∗ (v) とする．以下の性質は式 (2) から導かれる．
系 2.2 始点 s から頂点 v への有向路が最短路であるための必要十分条件は，その有向路に含まれるすべての枝
で，d∗ に関する三角不等式 (1) が等号で満たされていることである．
三角不等式 (1) と系 2.2 は，1 始点最短路問題を線形計画問題として定式化したときの双対実行可能条件と相補
スラック条件に相当する．有向路の長さを表す d(v) (v ∈ V ) は双対変数に対応しており，ラベル (label)，あるい
は，ポテンシャル (potential) とよばれる．
7
系 2.3 始点 s から頂点 v への最短路を P とする．P 上で v の一つ手前の頂点を w とすると，P 上の s から w へ
の有向道は s から w への最短路である．
i
©
*
©
P
©
J
i
J
J
^ i ¡
µ
¡
si
*
©©
- wi
vi
図 3: 最短路の部分路は，また最短路となることの概念図
2.3
アルゴリズム
各枝の三角不等式 (1) を満たすように順次，ラベル値を更新する方法をラベリング法という．
ラベリング法（1 始点）
ステップ 0 [初期化] d(s) := 0; d(v) := +∞ ∀v ∈ V \ {s} とする．
ステップ 1 [頂点の選択] 適当に頂点 v を選択．
ステップ 2 [v を始点とする枝の捜査] 頂点 v を始点とする枝 (v, v ′ ) で三角不等式：
d(v ′ ) ≤ d(v) + l(v, v ′ )
が成立していなければ，d(v ′ ) := d(v) + l(v, v ′ ) と更新する．
ステップ 3 [判定] すべての枝 a ∈ A で三角不等式が成立しているか，負閉路がみつかったならば終了．そうで
なければ，ステップ 1 へ．
補題 2.4 ラベリング法において，各頂点 v のラベル d(v) は非増加である．また，d(v) < ∞ ならば，d(v) は s か
ら v までのある有向路の長さを表している．よって，ラベル値が最短路長と等しくなった頂点のラベルはラベリ
ング法の終了まで変化しない．さらに，ラベリング法が終了したとき，d(v) = ∞ ならば，頂点 v は s から到達不
可能である．
頂点の選択の仕方によって，いろいろなアルゴリズムがある．
条件
アルゴリズム
枝の長さは任意
Bellman-Ford 法
枝の長さは非負
Dijkstra 法
枝の長さがすべて 1
2.3.1
幅優先探索法
Bellman-Ford 法
1. 頂点に適当に番号づけをする．ラベリング法のステップ 1 で，番号順に頂点を選択する．すべての頂点を
選択し終えるまでを 1 サイクルと呼ぶ．Bellman-Ford 法は，このサイクルを何度も繰り返す．
8
2. すなわち，サイクルごとに各頂点が選択され，ラベルの修正が繰り返される．このように，同じ頂点が何度
も選択され，そのラベルが修正されるラベリング法をを，ラベル修正法ともよぶ．
3. 定理 2.5 始点 s から頂点 v への最短路の枝数が k 本のとき，k 回目のサイクルが終了すると，d(v) は最短
路長になる．
証明:
Guide: 最短路の枝数の帰納法による．
4. 初等的な最短路の枝数は高々(頂点数 − 1) である．そこで，頂点数回分のサイクルが終了しても，ラベル値
が更新される頂点が存在するときは，その頂点を含む負閉路が存在する．
5. アルゴリズムを以下に示す．π(v) は，s から v への最短路上で v の直前の頂点を格納するための変数である．
頂点数を n とする．
Bellman-Ford 法
ステップ 1 [初期化] d(s) := 0; d(v) := +∞ ∀v ∈ V \ {s}; π(v) := v ∀v ∈ V とする．頂点は
V = {v1 , v2 , . . . , vn } と番号付けされているとする．頂点の番号に対する変数 i, サイクルに対する変
数 k = 1 を用意．
ステップ 1 [サイクル開始] i = 1 とする．
ステップ 2 [vi を始点とする枝の捜査] 頂点 vi を始点とするすべて枝 (vi , v ′ ) に対して，d(v ′ ) > d(vi ) + l(vi , v ′ )
ならば，d(v ′ ) = d(vi ) + l(vi , v ′ )，π(v ′ ) = vi と更新する．
ステップ 3 i < n ならば，i = i + 1 として，ステップ 2 へ．
ステップ 4 k < n ならば，k = k + 1 として，ステップ 1 へ．k = n ならば終了．
6. アルゴリズムが終了したとき，s から v への最短路は，π を逆にたどれば得られる．あるいは，n 回目のサ
イクルでラベル値が更新された頂点 v から π を逆にたどると，負閉路が得られる．
7. Bellman-Ford 法の例
(∞, v4 )
(∞, v2 )
−3
- vi
vi
2
4
5µ 6
¶6
(0, v1 ) ¡¡
1 2¶ 2
s = vi
1
¶
@
3@
¶
/ - i
R i
v3
v5
2
(∞, v3 )
(∞, v5 )
図 4: 問題例．枝上の数字は枝の長さを表す．v1 が始点である．頂点上の組は (d(v), π(v)) を表す．
9
v1
(5, v1 )
vi
2
v2
(∞, v4 )
- vi
4
(5, v1 )
v3
(4, v3 )
(2, v2 )
−3- vi
vy
2
4
vi
2
v4
(2, v2 )
- vi
4
(4, v3 )
vi
2
v5
(2, v2 )
- vy
4
(4, v3 )
vi
2
(2, v2 )
- vi
4
5¡
¶ 6 (0, v1¡
µ 6
µ 6
(0, v¡
1)
¡)
¶
vy
vi
1
1
k=1
¶
@
3@
¶
/ - i
R i
v3
v5
(3, v1 )
(4, v3 )
vi
2
¶ 6 (0, v1¡
¶ 6 (0, v1¡
¶ 6 (0, v1¡
¶6
µ 6
µ 6
µ 6
¡) 1 ¶
¡)
¡)
¶
¶ 2
2¶
vi
vi
vi
1
1
1
¶
¶
¶
¶
@
@
@
@
/ - i
¶
/ - i
¶
¶
/ - i
/ - y
¶
R i
@
@
R y
R i
@
R i
@
v3
v5
v3
v5
v3
v5
v3
v5
2
(∞, v5 )
(3, v1 )
(∞, v5 )
(3, v1 )
(2, v2 )
- vi
4
(4, v3 )
(1, v2 )
−3- vi
vy
2
4
(4, v3 )
vi
2
(5, v3 )
(3, v1 )
(1, v2 )
- vi
4
(4, v3 )
vi
2
(5, v3 )
(3, v1 )
(1, v2 )
- vy
4
(4, v3 )
(5, v3 )
vi
2
(1, v2 )
- vi
4
5¡
¶ 6 (0, v1¡
µ 6
µ 6
(0, v¡
1)
¡)
¶
i
vy
v
1
1
k=2
¶
@
3@
¶
/ - i
R i
v3
v5
(3, v1 )
(5, v3 )
¶ 6 (0, v1¡
¶ 6 (0, v1¡
¶ 6 (0, v1¡
¶6
µ 6
µ 6
µ 6
¡) 1 ¶
¡)
¡)
¶
¶
¶
i
2
i
2
vi
v
v
1
1
1
¶
¶
¶
¶
@
@
@
@
/ - i
¶
/ - i
¶
¶
/ - i
/ - y
¶
R i
@
@
R y
R i
@
R i
@
v3
v3
v3
v3
v5
v5
v5
v5
2
(3, v1 )
(5, v3 )
(3, v1 )
(5, v3 )
(3, v1 )
(5, v3 )
(3, v1 )
(5, v3 )
以下，サイクルを繰り返しても，ラベル値は変わらない．よって，負閉路は存在せず，s から各頂点への最
短路と最短路長は以下の通りである．
頂点
最短路
長さ
v1
v1
0
v2
v1 − v3 − v2
4
v3
v1 − v3
3
v4
v1 − v3 − v2 − v4
1
v5
v1 − v3 − v5
5
8. 毎サイクルですべての頂点を調べる必要はない．また，１サイクルの間にどの頂点のラベルも更新されなけ
れば，アルゴリズムは終了してよい．など，高速化の工夫はいろいろ．
2.3.2
Dijkstra 法
1. 始点 s から頂点 v への最短路 P 上で v の一つ手前の頂点を w とする．d(w) が最短路長に等しいとき，ラベ
リング法で w を選択すると，この繰り返しで，d(v) も最短路長に等しくなる．
2. ラベル値が最短路長と等しくなった頂点の集合を F と表す．頂点 v が F に属するとき，v はラベリング法
のステップ 1 で一度選択されれば十分である．
（頂点 v ∈ F を選択したとき，d(v) は最短路長に等しいので，これより小さくなることはない．よって，一
度 v を選択して，v から出る枝を捜査した後，v から出る枝 (v, v ′ ) に関して，三角不等式を満たさないこと
はない．
）
3. 補題 2.6 ラベリング法のステップ 1 で一度でも選択された頂点の集合を W と表す．ただし，頂点は必ず F
から選択されるものとする．枝の長さが非負のとき，W に属さない頂点のなかで，d の値が最も小さい頂点
は F に属する．
証明:
背理法で示す．
現在のラベル値を d, 最短路長を d∗ とする．d の値が最も小さい頂点を v̂ とし，v̂ ̸∈ F ，すなわち， d(v̂) > d∗ (v̂) と仮定する．
s から v̂ への最短路を P とする．P を v̂ から逆にたどっていったときに，初めて W に入る直前の頂点を
ŵ，初めて W に入った頂点を w′ とする．系 2.3 を繰り返し用いることにより，P 上の s から ŵ への有向道
10
は s から ŵ への最短路である．ここで，w′ ∈ W かつ，w′ ∈ F より，d(ŵ) は最短路長 d∗ (ŵ) に等しい．さ
∑
て，P 上の ŵ から v̂ への有向道に含まれる枝を A(P ′ ) で表すと，d∗ (v̂) = d∗ (ŵ) + a∈A(P ′ ) l(a) であるが，
枝の長さは非負なので，
d(ŵ) = d∗ (ŵ) ≤ d∗ (v̂) < d(v̂)
となり，v̂ の選び方に矛盾する．
W
?
′
wi
Q
Q
si
ŵ
si
N i
v̂
図 5: s から v̂ への最短路 P と W の概念図
4. アルゴリズムを以下に示す．W は探索の候補となる頂点（まだ，選択されていない頂点）の集合を格納す
る．
Dijkstra 法
ステップ 0 [初期化] d(s) := 0; d(v) := +∞ ∀v ∈ V \ {s}; W := V ; W = ∅; π(v) := v ∀v ∈ V とする．
ステップ 1 [頂点の選択] W にある頂点の中で，d の値が最も小さい頂点 v を選択．
ステップ 2 [v を始点とする枝の捜査] 頂点 v を始点とするすべて枝 (v, v ′ ) に対して，d(v ′ ) > d(v) + l(v, v ′ ) な
らば，d(v ′ ) = d(v) + l(v, v ′ )，π(v ′ ) = v と更新する．
ステップ 3 [判定] 頂点 v を W からのぞき，W に加える．W = ∅ ならば終了．そうでなければステップ 1 へ．
5. Dijkstra 法の例
図 6 の例で，s から各頂点への最短路と最短路長は以下の通りである．
頂点
最短路
長さ
s
s
0
v1
s − v2 − v1
3
v2
s − v2
2
v3
到達不可能
∞
v4
s − v2 − v1 − v4
5
6. Dijkstra 法もラベリング法の一つであるが，特に，一度選択されたラベル値がその後変わらないことより，
ラベル確定法ともよばれる．
7. Dijkstra 法のステップ 1 で d の値が最も小さい頂点を選択するときに，データ構造を工夫することで，アル
ゴリズムの高速化が図られている．具体的には，heap, bucket などを用いる．
11
(∞, v1 ) (∞, v3 )
4 vi
vi
3
1¾
5¡
µ
S
6
(0, s) ¡
1 S2
1
si
S
@
2@
S
w?
R i v2
vi
4
(∞, v2 )
4
(∞, v4 )
問題例と初期ラベル
(3, v2 )
(∞, v3 )
4 vi
y
y
vi
1¾
3
µ 6
S
(0, s) ¡¡
i
1 S
sy
S
@
?
S
wi
@
R y
vi
vy
2
4
(2, s)
(5, v1 )
(5, s)
vi
1¾
(∞, v3 )
vi
3
5µ 6
S
(0, s) ¡¡
S
y
i
s
S
@
2@
S
w?
R i v2
vi
4
(2, s)
(∞, v4 )
(3, v2 )
(∞, v3 )
vi
vi
1¾
3
µ 6
S
(0, s) ¡¡
i
y
1 S
s
S
@
@
R y
vi
2
(2, s)
S
w?
- vi
4
4
(6, v2 )
?
(3, v2 )
(∞, v3 )
y
vi
vi
1¾
3
(3, v2 )
(∞, v3 )
y
vi
vi
1¾
3
µ 6
S
¾ (0, s) ¡
¡
S
y
si
S
@
S
w?
@
R i
i
vy
vy
2
4
µ 6
S
¾ (0, s) ¡
¡
S2
y
si
S
@
S
w?
@
R i
vy
vi
2
4
(2, s)
(5, v1 )
(2, s)
(5, v1 )
図 6: Dijkstra 法の例．枝上の数字は枝の長さを表す．頂点上の組は (d(v), π(v)) を表す．網掛けの頂点は W に属
する．
2.3.3
幅優先探索法
1. 枝の長さがすべて 1 のとき，Dijkstra 法のステップ 1 で頂点の選択が簡単にできる．d の値が有限値をとり，
W に含まれない頂点をキュー（先入れ先出し：FIFO）2 に格納すればよい．キューにしまわれている頂点
の d の値は，現在選択されている頂点の d の値と等しいか，+1 である．さらに，キューには d の小さい順
に格納される．よって，キューから順に取り出せばよい．
2. このキューを用いた Dijkstra 法は，グラフの探索法の一つである幅優先探索法 (breadth-first search method)
と同じである．この探索の手順を以下に示す．Q は探索の候補となる頂点を格納するキューを表す．
幅優先探索法
ステップ 0 すべての頂点に「未探索」マークをつける．始点のマークを「探索済」にし，Q に格納する．
ステップ 1 Q に格納されている頂点がなければ終了．そうでなければ，Q から頂点を取り出す．取り出した頂
点を v とする．
ステップ 2 頂点 v を始点とするすべての枝 (v, v ′ ) に対して，頂点 v ′ が「未探索」ならば，その頂点のマーク
を「探索済」にして Q に格納する．ステップ 1 へ．
演習問題
問題 10: 図 7 の例題において，始点 s から各頂点への最短路を求めよ．
問題 11: 図 7 の例題において，各頂点から頂点 3 への枝数での最短路（すべての枝の長さを 1 とみなす）を幅優
2 キューは基本的なデータ構造の一つである．キューと対になって，スタック（先入れ後出し :FILO) もよく登場する．基本的なデータ構
造については，計算機科学の授業であつかうので，お楽しみに！(^ ^)/
12
- vi
5
9
¶
/ 7
¶
vi
4
S
@
¶ o
1 ?
10
¶
/7 S
R ?
@
Si
Si
i
v2
v3 ¾
v6
vi
1¾
1
7
5¡
µ o
S
¡ 4 S4
i
s
8
4
図 7: 最短路問題の例．枝上の数字は枝の長さを表す．
先探索を用いて求めよ．
問題 12: 図 8 の問題で始点 s から各頂点への最短路を求めよ．
3- vi
vi
1
3
2¡
S
µ o
¡ 1 S−6 3
si
15
- vi
vi
1
3
2¡
o −5
7
¶
µ S
¡ 7 S¶ 9
si
¶ −10
S
@
10
¶
S?
@
R ?
- vi
vi
2
4
2
(a)
(b)
S
@
10
S?
@
R ?
vi
vi
2¾
−7 4
図 8: 最短路問題の例．枝上の数字は枝の長さを表す．
問題 13: Bellman-Ford 法では，毎サイクルですべての頂点を調べる必要はない．また，n 回目のサイクルまでお
こなわなくても終了できる．サイクルごとに調べる頂点や終了条件を工夫して，Bellman-Ford 法を改良せよ．
問題 14: 各頂点 v に対して，dk (v) は s から v への枝数 k 以下での最短路の長さを表すとする．dk に関して，以
下の再帰式が成り立つ．
d0 (s) = 0;
dk+1 (v) = min{dk (v),
d0 (v) = +∞, ∀v ∈ V \ {s}
{dk (w) + l(w, v)}}, ∀v ∈ V, ∀k ≥ 0
min
w:(w,v)∈A
これを Bellman 方程式とよぶ．
1. Bellman 方程式が正しいことを説明せよ．
2. n を頂点数とする．dn (v) を求めれば，最短路長が求められる．Bellman 方程式を用いて，図 8(a) の問
題に対して，以下の表に dk (v) の値を行ごとに埋めていき，s から各頂点への最短路長を求めよ．
k
s
v1
v2
v3
v4
0
1
2
3
4
5
0
0
0
∞
2
2
∞
10
∞
∞
∞
∞
13
3. Bellman 方程式と Bellman-Ford 法のサイクルごとのラベル d との関係を述べよ．
問題 15: 有向閉路を含まないグラフ（非巡回グラフ）G = (V, A) と各枝 a の長さ l(a)，始点 s ∈ V が与えられた
とき，s から各頂点への長さ最大の有向道を求めるラベル確定法を示せ．
問題 16: 始点 s，終点 t の最短路問題を定式化すると，
∑
′
Minimize
(v,v ′ )∈A l(v, v )xvv ′
subject to
∑
xvw −
w:(v,w)∈A
∑
1
xzv =
z:(z,v)∈A
xvw ≥ 0 : 整数
−1
0
(v = s)
(v = t)
(v ∈ V \ {s, t})
((v, w) ∈ A)
となる．ただし，xvv′ は枝 (v, v ′ ) が最短路に含まれる回数を表す．以下，l(v, v ′ ) ≥ 0 ((v, v) ∈ A) を仮定
する．
1. x の整数条件をなくした線形計画問題に対して，x の値が，0 か 1 をとる最適解が存在することを示せ．
( もし，整数解でなかったとき，整数でない変数に対応する枝を集めてくると，どうなるか？）
2. 1 の線形計画問題の双対問題と相補性の条件を述べよ．
3. 双対変数とラベル d，三角不等式の関係を述べよ．
4. 始点 s からすべての頂点への最短路問題を同様に定式化せよ．
問題 17: Dijkstra 法では始点と同時に終点も与えられている場合，終点が W に含まれた時点で終了すればよい．
始点から終点までの最短路上にない頂点の選択をなるべくさけるために，Dijkstra 法のステップ 1 で W か
ら頂点を選ぶ際に，
min{d(v) + (v から終点への最短距離の下限値 h(v)) | v ∈ W }
を達成する頂点を選択するとよい．ただし，最短距離の下限値 h(v) は，
h(v) ≤ h(v ′ ) + l(v, v ′ ) ∀(v, v ′ )
(3)
を満たすものとする．通常の Dijkstra 法では，すべての頂点 v で h(v) = 0 とみなすことができる．
1. 図 7 の例題に対して，問題 11 で求めた頂点 3 への枝数での最短距離を４倍した値が，(3) の条件を満
たすことを確かめよ．
2. 図 7 の例題に対して，1 で得られた値を下限値 h として，下限を利用した Dijkstra 法を動かせ．
問題 18: 問題 17 で述べた下限を利用した Dijkstra 法で，始点から終点への最短路が求まることを証明せよ．
より)
14
最小費用流問題*
3
3.1
問題の定義
与えられたネットワーク上に “モノ” を流すことを考える．交通網，情報網，水路，あるいは製品の流れなどなん
でもよい．モノは有向枝に沿って流れ，頂点で分岐や合流をする．このネットワーク上の “モノ” の流れをフロー
という．ここでは，費用をもつネットワーク上にフローを流す問題を扱う．容量，需要／供給条件を満たすフロー
のなかで，費用を最小化する最小費用流問題 (minimum cost flow problem) という．
最小費用流問題 (minimum cost flow problem)
入力: 有向グラフ G = (V, A)．各枝の上限容量 u : A → IR++ と単位流量あたりの費用 c : A → IR．各頂点の
需要／供給量 b : V → IR．
出力: 条件：
容量制約
流量保存則
0 ≤ ϕ(a) ≤ u(a) ∀a ∈ A
∑
∑
ϕ(v, w) −
ϕ(z, v) = b(v) ∀v ∈ V
∑
を満たす各枝のフロー ϕ : A → IR のなかで費用の総和： a∈A c(a)ϕ(a) が最小となる ϕ．
w:(v,w)∈A
z:(z,v)∈A
∑
1. 頂点の需要／供給量 b は， v∈V b(v) = 0 を満たすと仮定する．b(v) > 0 である頂点が供給点，b(v) < 0 で
ある頂点が需要点，b(v) = 0 である頂点が中継点である．
2. ここでは，簡単のために，供給点，需要点おのおの１点ずつである問題を扱う．これは，一般性を失うこと
なく仮定できる．
（なぜならば，与えられた問題に対して，供給点，需要点をあらたに追加して，供給点から，
b(v) > 0 である頂点への枝と b(v) < 0 から需要点への枝を加えれば，問題を変換できるからである．ただ
し，新たに加えた枝の容量は |b(v)| に等しく，費用は 0 とする．
' G
$
d
d
*
©
dX
©
:d d
»»
»
©
XX
zu
»
»
©
u
d
d
供給点 H
³
1 需要点
³
H
³
|b(v)| HH
d d d³ |b(v)|
jd
&
%
¢̧
AK
b(v) > 0
b(v) < 0
図 9: 複数の供給／需要点をもつ最小費用流問題を供給／需要点がおのおの１点ずつの問題への変換
3. 特に，すべての頂点 v で b(v) = 0 である最小費用流問題を最小費用循環流問題という．
4. 容量制約と流量保存則を満たすフロー ϕ を（実行）可能流 (feasible flow) という．特に，最小費用循環流問
題に対する可能流を循環流 (circulation flow) という．費用を最小とする可能流 ϕ∗ を最小費用流 (minimum
cost flow) という．
5. 最小費用流問題は線形計画問題であるので，単体法や内点法なので最小費用流を見つけられる．しかし，グ
ラフという離散構造を影にもつ問題であるので，問題の構造を利用した解法について学ぶ．
15
3.2
基本的性質
1. まず，任意のフロー ϕ に対する補助ネットワーク (auxiliary network)（あるいは残余ネットワーク (residual
network)）Nϕ = (Gϕ = (V, Aϕ ), uϕ , cϕ ) を定義する：
• Gϕ = (V, Aϕ ) は V （与えられたグラフの頂点集合）を頂点集合とし，枝集合 Aϕ は以下のように与
える．
Aϕ = {a ∈ A | ϕ(a) < u(a)} ∪ {ā | a ∈ A, ϕ(a) > 0}
ただし，ā は有向枝 a の向きを逆にした枝である．つまり，a = (v, v ′ ) のとき，ā = (v ′ , v) である．
• 残余容量 uϕ : Aϕ → IR++ は，
{
uϕ (a) =
u(a) − ϕ(a) (a ∈ A)
(ā ∈ A) ϕ(ā)
で与えられる．
• 枝費用 cϕ : Aϕ → IR は，
{
cϕ (a) =
(a ∈ A)
c(a)
−c(ā) (ā ∈ A) で与えられる．
2. 補助ネットワークは，フロー ϕ を流した後に，各枝の容量を超えることなく，あとどれだけ流せるのか，あ
るいは，逆向きにつけた枝はフローをもとに戻せるかを表す．
3. フロー ϕ と ϕ に対する補助ネットワーク Nϕ 上のフロー ψ : Aϕ → IR に対して，ϕ + ψ : A → IR を
ϕ(a) + ψ(a) − ψ(ā) (a ∈ Aϕ , ā ∈ Aϕ )
(ϕ + ψ)(a) =
ϕ(a) + ψ(a)
ϕ(a) − ψ(ā)
(a ∈ Aϕ , ā ̸∈ Aϕ )
∀a ∈ A
(a ̸∈ Aϕ , ā ∈ Aϕ )
とする．すなわち，補助ネットワーク上の逆向きの枝のフローは ϕ からフローを引き戻すようにする．
このとき，費用に関して，
∑
c(a)(ϕ + ψ)(a) =
a∈A
∑
a∈A
c(a)ϕ(a) +
∑
cϕ (a)ψ(a)
(4)
a∈Aϕ
が成り立つ．
4. ϕ が可能流，ψ が Nϕ 上の循環流のとき，ϕ + ψ は元のネットワーク上の可能流である．(ϕ + ψ は容量
制約，流量保存則ともに満たすことを確認せよ）
5. (4) 式と 4 より，ϕ に対する補助ネットワーク上に負の費用の循環流 ψ があったときには，ϕ よりも費用の
小さい可能流 ϕ + ψ が得られる．
6. 任意の循環流は，閉路上のフローの和で表せる．
7. 可能流 ϕ が最小費用流であるための代表的な条件．
有向閉路に含まれる枝の費用の和が負であるとき，その閉路を負閉路とよぶ．
16
例 ϕ = ψ1 + ψ2 + ψ3
8-vg
vg
2
4
5
3
S2 ¶ @
6
Rg
@
3 S¶
v6
3
¶
S
¡
/ S
¶
w ¡
ª
vg
3 ¾ 5 vg
5
ϕ
7
¡
µ
¡
vg
1
7
@
I
@
0-vg
vg
2
4
0
0
S2 ¶ @
6
@
Rg
0 S¶
v6
0
¶
S
¡
/ S
¶
w ¡
ª
vg
3 ¾ 2 vg
5
ψ1
5-vg
vg
2
4
5
0
S0 ¶ @
6
@
Rg
0 S¶
v6
0
¶
S
¡
/ S
¶
w ¡
ª
vg
3 ¾ 0 vg
5
ψ2
2
¡
µ
¡
vg
1
2
@
I
@
3-vg
vg
2
4
0
3
S0 ¶ @
6
@
Rg
3 S¶
v6
3
¶
S
¡
/ S
¶
w ¡
ª
vg
3 ¾ 3 vg
5
ψ3
5
¡
µ
¡
vg
1
5
@
I
@
0
¡
µ
¡
vg
1
0
@
I
@
図 10: 枝上の数がその枝のフロー量を表す．循環流 ϕ は，閉路上のフロー ϕ1 , ϕ2 , ϕ3 の和で表せる．
定理 3.1 （負閉路最適性条件）可能流 ϕ が最小費用流であるための必要十分条件は，ϕ に関する補助ネッ
トワーク Nϕ 上に負閉路が存在しないことである．
Nϕ 上の閉路 C に対して，Nϕ 上のフロー χC を
{
1 (a ∈ Aϕ (C))
χC (a) =
0 (a ̸∈ Aϕ (C))
証明:
とする．ただし，Aϕ (C) は C に含まれる枝集合を表す．すなわち，χC は C に含まれている枝のフローを 1
とした循環流である．
[必要性] 対偶を示す．Nϕ 上に負閉路 C が存在したとき，十分小さな τ に対して τ χC : Aϕ → IR は Nϕ 上の
∑
循環流であり， a∈Aϕ cϕ (a)(τ χC (a)) < 0 なので，(4) の関係より可能流 ϕ + τ χC は ϕ よりも費用が小さく
なる．
[十分性] ϕ∗ を最小費用流とする．ψ ∗ : Aϕ → IR を
{
max{ϕ∗ (a) − ϕ(a), 0}
∗
ψ (a) =
max{ϕ(a) − ϕ∗ (a), 0}
(a ∈ A)
(ā ∈ A)
とすると，ψ ∗ は Nϕ 上の循環流である．ここで，6 より，ψ ∗ は，いくつかの閉路 Q1 , Q2 , . . . , Qk 上への
フロー χQi : Aϕ → IR (1 ≤ i ≤ k) に分解される．すなわち，ある正数 τi (1 ≤ i ≤ k) に対して，ψ ∗ =
∑
1≤i≤k τi χQi となる．ところで，補助ネットワーク上に負閉路が存在しないので，任意の i(1 ≤ i ≤ k) に
∑
対して， a∈Aϕ cϕ (a)χQi (a) ≥ 0 が成り立つ．よって，
∑
a∈A
より，
3.3
3.3.1
∑
a∈A
∑
c(a)(ϕ∗ (a) − ϕ(a)) =
c(a)ϕ∗ (a) ≥
cϕ (a)ψ ∗ (a) =
a∈Aϕ
∑
a∈A
∑
1≤i≤k
τi (
∑
cϕ (a)χQi (a)) ≥ 0
a∈Aϕ
c(a)ϕ(a) が得られ，ϕ も最小費用流となる．
アルゴリズム
負閉路消去法
任意の可能流 ϕ から出発し，補助ネットワーク Nϕ 上に負閉路が存在する限り，この有向閉路に沿って，フロー
の更新を繰り返す負閉路消去法を以下に示す．
∑
αχC は補助ネットワーク上の循環流なのでステップ 2 で更新された ϕ は可能流であり， a∈Aϕ (C) cϕ (a) < 0 より，
∑
更新されたフローの費用は，α| a∈Aϕ (C) cϕ (a)| だけ減少する．ステップ 2 の操作を負閉路 C の消去 (cancelation)
という．負閉路最適性条件より，アルゴリズムが終了したとき ϕ が最小費用流であることが分かる．負閉路は，最
短路問題に対するアルゴリズムなどを用いて求めることができる．負閉路消去法の例を図 11 に示す．
17
負閉路消去法
ステップ 0 [初期化] 可能流 ϕ をみつける．
ステップ 1 [補助ネットワークの作成] 補助ネットワーク Nϕ = (Gϕ = (V, Aϕ ), uϕ , cϕ ) を作成し，負閉路 C を
見つける．負閉路が存在しなければ終了．
ステップ 2 [フローの更新] α := min{uϕ (a) | a ∈ Aϕ (C)} を求め，ϕ := ϕ + αχC と更新する．ステップ 1 へ．
0
問題例
i
Q2
Q
´
Q
s i
1
−3
3 i
3́ 枝上の数字は費用 c
Q1
´
Q ? 4
頂点の数字は需要／供給量 b
´
Q
s i
2´3́
0
各枝の上限容量は 2
i
Q1
1´3́
Q
´
´
Q
s i- i
1
i
3́
Q1
Q2
2
Q ? ´
Q
´
Q i
s
s
Q
初期フロー
フロー ϕ
2´3́
i
Q1
2´3́
Q
´
Q
s i- i
0
3́
Q1
´
2
Q
?
´
Q
s
i
i
Q2
Q
Q
s i
0
3́
´
1
?
´
i
目的関数値=16
目的関数値=14
目的関数値=13
補助ネットワーク
i2
i2
i
枝 上 の 数 字 は´ Q
3́ Q
kQ
Q
Q
kQ
´ Q
k
2´ ´
QQ
Q
´−2
´−2
´−2 6 Q
s
Q
s
cϕ
´
Q
Q
+́
+́
+́
−2
−2
−2 Q i
i
i
i
i
i
−1 1
1
1
Q
1
´
kQ
Q
QQ
−4
?´
s
Q i+́
−1
Q
k
Q
−1
α=1
´
´
−4
?
+́
Q i
α=1
3́
1
Q
Q
kQ
4´´
´
QQ
−4
?
´
s
Q i+́
−1
負閉路なし
図 11: 負閉路消去法の例．上段にフロー値，下段にその補助ネットワークを示す．補助ネットワーク上で選択し
た負閉路を太線で示す．
3.3.2
供給量が増えたとき —最短路繰り返し法—
供給点を s，需要点を t とする．(G = (V, A), u, c, b) に関する最小費用流 ϕ が得られているとする．ここで，
v=s
b(v) + 1
b′ (v) =
b(v) − 1
v=t
b(v)(= 0) v =
̸ s, t
に対しての最小費用流を求める．
1. Nϕ 上には負閉路がないので，s から t への最短路 P が得られる．この最短路 P に含まれる枝のフローを 1
としたフローを χP とする．すなわち，
{
χP (a) =
1 (a ∈ Aϕ (P ))
0 (a ̸∈ Aϕ (P ))
とする．ただし，Aϕ (P ) は P に含まれる枝集合を表す．α = min{1, {uϕ (a) | a ∈ Aϕ (P )}} を求め，ϕ′ :=
ϕ + αχP と更新しても，容量制約は満たす．もし，α = 1 ならば，b′ に対して流量保存則を満たす．
18
2. 補題 3.2 Nϕ′ 上に負閉路は存在しない．
証明:
もし，負閉路 C が存在したとしたら，C は P の逆向き枝を必ず含む．C の枝と P の枝を取り出し
たグラフ G′ を考える．ただし，頂点 v, v ′ 間に両向きの枝が存在する場合は，これらの枝は取り除く．多重
枝はそのままにしておく．このとき，G′ の枝はすべて，Nϕ 上の枝である．さらに，G′ の枝をすべて１度
づつ通る s から t への有向路が存在する．
∑
∑
∑
一方，G′ の枝集合を A(G′ ) で表すと， a∈A(G′ ) cϕ (a) = a∈Aϕ (P ) cϕ (a) + a∈A ′ (C) cϕ′ (a) が成り立つ．
ϕ
∑
∑
ここで，C は負閉路なので， a∈A(G′ ) cϕ (a) < a∈Aϕ (P ) cϕ (a) となり，P が最短路に反する．
G′
P
)
)
si
?
gX
y
X
z g
C
Wg
3S
S
wg
±
w
Ni
t
si
⇒
-
?
g g
Wg
3S
S
wg
±
w
N i
t
図 12: 最短路 P と負閉路 C （太線）の枝を取り出したグラフ G′ を構成する概念図
3. よって，流量保存則を満たすまで，補助ネットワーク上の最短路に沿ってフローの更新をくりかえせばよい．
このアルゴリズムを最短路繰り返し法という．
4. 最短路繰り返し法を用いれば，ϕ = 0 からスタートして，最小費用流を求められる．以下 ∂ϕ(s) はフロー ϕ
∑
∑
の s からの正味流出量，すなわち， w:(s,w)∈A ϕ(s, w) − z:(z,s)∈A ϕ(z, s) を表す．
最短路繰り返し法
ステップ 0 [初期化] ϕ = 0 とする．
ステップ 1 [補助ネットワークの作成] 補助ネットワーク Nϕ = (Gϕ = (V, Aϕ ), uϕ , cϕ ) を作成し，s から t への
最短路 P を見つける．
ステップ 2 [フローの更新] α := min{b(s) − ∂ϕ(s), min{uϕ (a) | a ∈ Aϕ (P )} を求め，ϕ := ϕ + αχP と更新す
る．ϕ が需要／供給量を満たしていたら終了．そうでなければ，ステップ 1 へ．
最短路繰り返し法の例を図 13 に示す．
19
0
問題例
i
Q (4, 2)
Q
s i
(1, 1) Q
−3
3́ 枝上の数字は (費用, 容量)
´
(2, 1)
?
´
i
頂点の数字は需要／供給量 b
3́
(2, 2) ´
´
3 i
Q
(4, 2) Q
Q
s
0
i
Q0
1´3́
Q
´
´
Q
s i- i
0
i
3́
Q0
Q0
0
Q ? ´
Q
´
Q
s i
Q
s
初期フロー
フロー ϕ
0´3́
i
Q0
2´3́
Q
´
s i- i
Q
1
3́
Q0
´
1
Q
?
´
s
Q
i
i
Q1
2´3́
Q
´
s i- i
Q
1
3́
Q1
´
1
Q
?
´
s
Q
i
目的関数値=0
目的関数値=5
目的関数値=11
補助ネットワーク
i4
i4
i4
枝 上 の 数 字 は3́ Q
´ QQ
´ Q
Q
kQ
2´
2´3́
Q
6
6 Q
´
´
−2
s
Q
−2
s
Q
s
Q
cϕ
´
´
+́
+́
i
i
i −1
i
i −1 −4Q i
1
3́
Q4
Q4
Q4
´
´
Q
Q ? 2´
Q
−2
−2
´
Q
s i+́´
Q
s i
Q
s i+́´
α=1
α=1
α=1
i
Q2
Q
s i
Q
0
3́
´
1
?
´
i
目的関数値=18
流量保存則を満たす
図 13: 最短路繰り返し法の例．上段にフロー値，下段にその補助ネットワークを示す．補助ネットワーク上で選
択した最短路を太線で示す．
演習問題
問題 19: 図 14 の例題において，負閉路消去法により最小費用（循環）流を求めよ．ただし，初期可能流を ϕ = 0
とする．
1) m
m (20, (10, −3)
(10,¡
3)
¶ @
µ
¡
I (40, 2)
7 @
¶
¶
(30,
3)
¡
@
¶
m
¶¶ (10, −7) m
¶(20, 3)
I
@
µ
¡
@ −7) ¶ ¶
¡
(20,
¶
?¡ (30, 5)
/
¶
@ ?
m
¾
m
¶
(20, −7)
図 14: 最小費用流問題の例 (1)．枝上の数字は（容量，費用）をあらわす．供給／需要量はすべて０．
問題 20: 図 15 の例題において，最短路繰り返し法により最小費用流を求めよ．
問題 21: 最小費用流問題を定式化すると，
Minimize
subject to
∑
∑
w:(v,w)∈A
(v,w)∈A cvw xvw
xvw −
∑
xzv = bv
(v ∈ V )：流量保存制約
z:(z,v)∈A
0 ≤ xvw ≤ uvw
となる．ただし，xvw は枝 (v, w) に流れるフロー量を表す．
20
((v, w) ∈ A)：容量制約
6) m
m (20, (10,¡
2)
µ
¡
7 6@ (35, 2)
¶
¶
@
(10,
1)
R
@
¡
¶ (15, 2) tm
sm
¶
(5, 6)
@
µ
¡
¡
(35,@4) ? ¶
(10, 7)
R ¶
@
¡
m
- m
(30, 2)
図 15: 最小費用流問題の例 (2)．枝上の数字は（容量，費用）をあらわす．s を供給点，t を需要点とし，供給量=
需要量= 35 とする．
1. 各頂点 v に対する bv と各枝 (v, w) に対する uvw がすべて整数で与えられているとき，この問題の最適
解のなかに，整数の値をとる解が存在することを説明せよ．
2. 双対問題と双補性の条件を述べよ．
3. 最小費用流 ϕ∗ に対し，Nϕ∗ に新たに頂点 s と s から各頂点 v(∈ V ) への枝を加える．新たに加えた枝
の長さを 0 とし，Nϕ∗ 上の枝の長さを cϕ∗ で与える．このとき，Nϕ∗ には負閉路が存在しないので，s
から各頂点 v への最短路 d(v) が求められる．この d と 2. で得られた双対変数との関係について述べよ．
問題 22: 問題 7 のアルバイト派遣問題を最小費用流問題として解け．
（負閉路消去法と最短路繰り返し法とどちら
を用いるのがよいか．
）
問題 23: 問題 20 において，各枝の容量，あるいは，需要／供給量が以下のように変化したとき，問題 20 で得た
解から最適解を求めよ．このとき，負閉路消去法と最短路繰り返し法とどちらを用いるのがよいか．
1. 供給量，需要量ともに 5 ずつ増加したとき．
2. すべての枝の容量が 10 ずつ増加したとき．
4
グラフの表現*
グラフを表現する方法には，行列による方法とリストによる方法がある．
(a) 行列による表現 1：
行を頂点に，列を枝に対応させ，(v, a) 要素を，
(枝 a の始点が頂点 v のとき)
1
(v, a) =
−1
0
(枝 a の終点が頂点 v のとき)
(それ以外)
と決めた行列で表すことができる．この行列を接続行列 (incidence matrix) という．無向グラフの場合には，
{
(v, a) =
1 (枝 a の端点が頂点 v)
0 (それ以外)
21
とする．多くのネットワーク流問題は接続行列を制約行列とする線形計画問題に定式化できる．
図 16 の有向グラフを表すと，
v1
a1
a2
a3
a4
a5
a6
a7
a8
a9
1
1
0
0
0
0
0
0
0
0
1
1
−1
0
0
0
−1
0
0
1
−1
0
−1
0
0
1
0
0
−1
0
0
0
0
0
0
0
v2
−1
v3
0
v4
0
v5 0
v6
0
0
0 −1
0
1
0
0
0
1
1
−1
0 −1
となる．接続行列では，ループを表せないことに注意．
²¯
²¯
a3 - v4
v2
±°
±°
a6¶ @ a
Sa
µ 6
a1¡
¡
@7
S4
¶
²¯
R²¯
@
¡
a5 S ¶
v1
v6
¶
S
±°
±°
@
µ
¡
¶ S
a9
a@
¡
2
¶
S ²¯
/
¶
S
w ¡
@
R²¯
v3 ¾
v5
±° a8 ±°
図 16: グラフの例
(b) 行列による表現 2：
行，列ともに頂点に対応する行列を考える．要素 (v, v ′ ) を，
{
(v, v ′ ) =
(v から v ′ への枝が存在する)
1
0 (そうでないとき)
と定めた行列を隣接行列 (adjancency matrix) という．無向グラフの場合には，向きを無視するので，(v, v ′ ) 要素
が 1 ならば，(v ′ , v) 要素も 1 となり，対称行列となる．図 1 の有向グラフを隣接行列で表すと，
v1
v2
v3
v4
v5
v6
v1
v2
v3
v4
v5
v6
0
1
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
となる．隣接行列では多重枝を表せないことに注意．
(c) リストによる表現：
行列表現はどちらも行列の大きさに比べて非零要素が少ない．よって，計算機上でグ
ラフを表現するときに，2 次元配列によって，接続行列や隣接行列を使うのは妥当とはいえない．一方で，各枝 a
の始点と終点を 1 次元配列でもつのみでは，ある頂点から出る枝や入る枝の情報を得るのに時間がかかる．そこ
で各頂点 v に対し，その頂点から出る枝や入る枝の集合をリスト構造3 を用いて表すことで，グラフを効率よく表
現できる．出る枝の集合，入る枝の集合のどちらをリストでもつのか，また，リストの種類として，単方向リス
3 リストについても，計算機科学の授業で扱いますので，お楽しみに！(^
22
^)v
ト，双方向リスト，巡回リストなどいずれを用いるかは，グラフにどのような変形を施すかによって選択されるべ
きである．
図 1 の有向グラフに対し，各頂点に接続する枝集合のリスト表現のイメージを図 17 に示す．左図が出る枝集合
のリスト，右図が入る枝集合のリスト表現を示す．他に，各枝の始点と終点を知るための配列が必要である．
v1 r - a1
v2 r - a3
v3 r - a5
v4 r - a6
v5 r - a8
v6 ·
·
r - a2
¶
¶
r - a4 ¶
¶
¶
¶
r - a7 ¶
¶
r - a9 ¶
¶
v1 ·
·
v2 r - a1
v3 r - a2
r - a5
¶
¶
r - a6 r - a8
v4 r - a3
v5
v6
¶
¶
r - a4 ¶
¶
r - a7 r - a9
¶
¶
図 17: 有向グラフのリスト表現
演習問題
問題 24: 以下のグラフの接続行列，隣接行列，リストによる表現をかけ．
a4
a4
ª
vm
2
k a8
Q
a2 QQ
j vm
vm
1
5
a3 *
:
aJ1
a6
J
^
a 4 ¼a7
vm
3 ¾ 5 vm
vm
2
Q a8
a2 QQ
vm
vm
1
5
a3
aJ1
a6
J
a7
a5 vm
vm
3
4
(a)
(b)
図 18: グラフの例
23
¶
¶
組合せ最適化問題
5
5.1
組合せ最適化 vs 線形計画
1.
組合せ最適化（離散最適化／整数計画）
線形計画
• 実行可能解（制約条件を満たす解）は
• 数十万変数の大規模な問題も計算可能
有限個
• すべての解を調べれば最適解は得られる
2. 実行可能解の個数の概算
巡回セールスマン問題 (Traveling Salseman Problem)
あるセールスマンが n 都市を巡回訪問する．任意の都市から出発して，のこりの都市をちょうど一度ずつ訪問
し，出発した都市に戻ってくる．各都市間の移動距離が与えられているとき，移動距離を最小にするような訪
問順序を決定せよ．
（ネットワーク上での問題定義は 3 ページ．
）
(a) 巡回セールスマン問題の実行可能解の個数は．
(b) 日本の 47 都道府県をまわる問題の実行可能解の個数を概算せよ．Stirling の近似式 n! =
√
2πn(n/e)n+(1/12n)
を用いる．
(c) １秒間に１千億 (1012 ) の実行可能解を出力する計算機があったとすると，47 都市に対するすべての実
行可能解を出力するにはどのくらいの時間がかかるか．
3. 最短路問題，最小費用流問題には，効率の良いアルゴリズム（多項式時間アルゴリズム）があったが，巡回
セールスマン問題はそのようなアルゴリズムが存在しないであろうと予想されている．
（クラス N P-困難に
属する．
）4 整数計画問題には，このように効率のよいアルゴリズムがみつかっていない問題がたくさんある．
では，どうするか？
4.
• 最悪の場合，時間がかかるかもしれないが，なるべく良い方法で厳密に最適解を求める．— 厳密解法
• 最適解を求めることをあきらめる．ある程度良いことが保証されている解を求める．— 近似解法
5. 厳密解法の枠組み
• 分枝限定法 (Branch and bound method)
• 分枝切除平面法 (Branch and cut method) 分枝限定法+多面体的アプローチ
• 動的計画法 (Dynamic programming)
6. 近似解法
• 近似スキーム．精度保証．最適解からどのくらい悪い解かの保証ができる方法
• メタヒューリスティック（タブーサーチ，遺伝的アルゴリズム，アニーリング法）
• 乱択アルゴリズム
4 効率のいいアルゴリズムの存在？などについては計算機科学の授業でちょこっとやります．
24
(^ ^;)
5.2
緩和問題
1. そのままでは解きにくい問題に対して，なんらかの条件（いくつかの制約）をなくして解きやすくする．
2. 名前のついている緩和法
連続緩和 整数条件をなくす．つまり，整数変数を連続変数としてあつかう．もっともポピュラーな緩和法．
ラグランジュ緩和 制約をなくすだけでなくて，なくした制約に係数をかけて，目的関数に組み込む．ある
制約をなくしたときに，問題の構造が活かされて解きやすくなるときに有効．
3. 連続緩和によって得られた解から，元問題の解に対して，どのような情報が得られるのか？
最大化
x1 + x2
3x1 + 5x2 ≤
条件
47
2
x1 − 2x2 ≤ 2
2x1 − x2 ≤ 7
x1 , x2 : 非負整数
(a) 上の整数計画問題の連続緩和問題を解け．
(b) 連続緩和問題の情報を利用して，上の整数計画問題の最適解は得られるか？
(c) 目的関数を，
「最大化 3x1 − 2x2 」としたときはどうか．
(d) 目的関数を，
「最大化 19x1 + 30x2 」としたときはどうか．
4. 緩和問題から得られる情報:
定理 5.1 (a) 緩和問題が実行可能解（制約条件を満たす解／許容解）をもたないとき，もとの問題も実行可能解をも
たない．
(b) 緩和問題の最適解がもとの問題の実行可能解のとき，この解はもとの問題の最適解でもある．
(c) もとの問題が最大化（最小化）問題のとき，
「緩和問題の最適値 ≥ (≤) もとの問題の最適値」．つまり，
緩和問題の最適値はもとの問題の最適値の上界値（下界値）．
証明:
Guide: もとの問題の実行可能解の集合 ⊆ 緩和問題の実行可能解の集合
25
ナップサック問題 —難しい問題の代表—
6
6.1
ナップサック問題
1. 線形制約が一つの整数計画問題：
n
∑
最大化
ci xi
i=1
n
∑
条件 ai xi ≤ b
i=1
xi：非負整数 (i = 1, . . . , n)
2. 変数が 0-1 に制限されているナップサック問題を 0-1 ナップサック問題とよぶ．
以下，0-1 ナップサック問題をあつかう．
3. 例題
例 6.1 遠足のお菓子の買い出し．お菓子は 500 円までa ．各お菓子に評価点をつけたとき，評価点の和を最大
にするようなお菓子の組合せを求めよ．ただし，おなじお菓子は一つしかもっていかない． 評価点
値段
○／×
あめ
ガム
りんご
ポッキー
きのこ
の里
ボタボタ
せんべい
ポテト
チップ
ラムネ
エンジェル
クッキー
バナナ
2
50
1
10
8
130
7
200
4
150
6
80
3
70
8
210
1
0
a 近頃の小学生は
300 円くらいだそうだ．
変数：
{
xi =
1 お菓子 i を選択する
0 お菓子 i を選択しない
定式化：
最大化
条件
2xあめ + xガム + 8xポッキー + 7xきのこ + 4xせんべい + 6xポテチ + 3xラムネ + 8xクッキー + xバナナ
50xあめ + 10xガム + 130xポッキー + 200xきのこ + 150xせんべい + 80xポテチ + 70xラムネ + 210xクッキー + 0xバナナ ≤ 500
xi ∈ {0, 1}
(i ∈ { お菓子 })
4. xバナナ = 1 と固定できる．
一般にナップサック問題では，以下を仮定している．
(a) ci , ai , b はすべて正
• ci ≥ 0, ai ≤ 0 のとき xi = 1 に固定
• ci ≤ 0, ai ≥ 0 のとき xi = 0 に固定
• ci ≤ 0, ai ≤ 0 のとき c′i = −ci , a′i = −ai , x′i = 1 − xi で置き換える．
∑n
(b) ai ≤ b (i = 1, . . . , n) かつ i=1 ai > b
5. 以降，例 6.1 のバナナは除く．
26
6. もし，ai （値段）がすべて等しいとき，答えは簡単に見つかる．
どれでも 1 個 10 円の駄菓子屋さんに 50 円もっていった．消費税を考えると，どれでもよいので，4 個まで変
える．このとき，欲しいものから順に 4 個買えばよい．
6.2
連続ナップサック問題 —上界値をもとめる—
1. ナップサック問題を連続緩和した問題を連続ナップサック問題とよぶ．
最大化
n
∑
c i xi
i=1
条件
n
∑
ai xi ≤ b
i=1
0 ≤ xi ≤ 1
(i = 1, · · · , n)
2. 連続ナップサック問題の最適解：
(a)
c2
cn
c1
≥
≥ ··· ≥
a1
a2
an
を満たすように添え字を付け換える．ci /ai を i の効率という．
(b) 効率のよいものから選択．
p−1
∑
ai ≤ b <
i=1
p
∑
ai
i=1
となる添え字 p に対して，
1
p−1
∑
xi =
ai )/ap
(b −
i=1
0
(i = 1, · · · , p − 1)
(5)
(i = p)
(i = p + 1, · · · , n)
定理 6.1 (5) で得られた解は，連続ナップサック問題の最適解である．
3. 例 6.1 に対する連続ナップサック問題の最適解：
評価点
値段
効率
解
あめ
ガム
りんご
ポッキー
きのこ
の里
ボタボタ
せんべい
ポテト
チップ
ラムネ
エンジェル
クッキー
2
50
0.040
1
1
10
0.100
1
8
130
0.062
1
7
200
0.035
0
4
150
0.027
0
6
80
0.075
1
3
70
0.043
1
8
210
0.038
16/21
上界値は 26.10．
27
貪欲算法
6.3
1. 0-1 ナップサック問題の一つの実行可能解を求める．最適ではなくてもよいが，なるべくよい解を求めたい．
2. 得られた解の目的関数値よりも最適値は小さくなることはない．よって，この目的関数値は最適値の下界値
（かかいち）を与える．
3. 0-1 ナップサック問題は，良さそうな解を簡単に見つけられる．
効率のよいものから順次チェック．制約条件を満たすならば加え，そうでなければ加えないという操作を繰り
返す．
このように，部分的な情報だけから変数を決めていくアルゴリズムを貪欲算法 (greedy algorithm) という．
4.
貪欲算法
ステップ 0: 各変数 i (i = 1, · · · , n) の効率 ci /ai を計算し，効率の大きい順に添え字を付け換える．残量を表
す b′ を b とし， k = 1 とする．
ステップ 1: ak ≤ b′ ならば，xk = 1，b′ = b′ − ak とする．そうでなければ (ak > b′ )，xk = 0 とする．
ステップ 2: k = n ならば終了．そうでなければ，k = k + 1 としてステップ 1 へ．
5. 貪欲算法では，連続ナップサック問題の最適解 (5) で，唯一つ整数でない値の xp を 0 に固定し，0 である変
数の中で 1 に変更できるものがあれば変更している．
6. 例 6.1 に貪欲算法を適用：
解
あめ
ガム
1
1
りんご
ポッキー
1
きのこ
の里
0
ボタボタ
せんべい
1
ポテト
チップ
1
ラムネ
1
エンジェル
クッキー
0
下界値は 24．
分枝限定法 (branch-and-bound method)
6.4
1. 分枝限定法とは，最適解が効率良く求められないような，どんな組合せ最適化問題にも有効な厳密解法の枠
組み．
• 基本的にはすべての解の列挙
2.
• 最適解になり得ない解は無視するように要領よく
3. すべての解を並べる，つまり全列挙について，まず考えよう．
例 6.1 の 0-1 ナップサック問題の解をすべて列挙すると，全部で 28 = 256 通りの解がある．この列挙をシス
テマティックに行うために，列挙木が便利である．
1 xあめ = 1 である組み合わせと xあめ = 0 である組み合わせに分ける．
2 xあめ = 1 の組み合わせのなかで，xガム = 1 である組み合わせと xガム = 0 の組み合わせとに分ける．xあめ = 0
の組み合わせに対しても同様．
..
.
28
!"#$%&'
*+,-./%&'
(
01213
(
(
)
(
)
) (
)
(
(
)
(
)
)
(
)
)
( )
45
256
図 19: ナップサック問題の解の全列挙
図 19 では，評価点の順に列挙木を構成．
4. 最適解になり得ない解を無視する工夫
実行不可能な解（組み合わせ）を排除
列挙木の中間点において，それまでに 1 に固定された変数 i の ai の合計（すなわち，選択したお菓子の合計
金額）を計算．この合計が b = 500 円を越えている場合は，この後の組み合わせに無関係に実行不可能．⇒
この点より先の列挙は省略できる！
（この例題の場合は 161 通りの実行可能解）
絶対に最適解になり得ない解（組み合わせ）の排除
xポッキー = 0, xクッキー = 0, xきのこ = 0 とした中間点より下にある解は最適解になり得ない．なぜならば，のこりの
変数をすべて 1 にしても，評価点の和は 16 であり，先に得た貪欲算法による最適値の下界値 24 よりも小さい
から．
ある中間点の下に最適解が存在するかどうかを調べる方法：
列挙木の中間点において，それまでに決められた変数を固定した問題を子問題とよぶ．次の定理は，最大化
問題に対しての性質．
定理 6.2 列挙木のある中間点における子問題の上界値が，もとの問題の下界値よりも小さければ，この中
間点の下には最適解は存在しない．また，子問題の緩和問題の最適解が元問題で実行可能ならば，この解が
中間点より下でもっともよい解である．
5. 0-1 ナップサック問題では...
ある中間点で，
• 1 に固定されている変数の添え字の集合=I
• 0 に固定されている変数の添え字の集合=O
• 残りの固定されていない変数の添え字の集合= F
29
とすると，この中間点における子問題は，
∑
最大化
ci +
i∈I
条件
∑
i∈I
∑
ci xi
i∈F
ai +
∑
ai xi ≤ b
i∈F
xi ∈ {0, 1}
(i ∈ F )
となる．この問題の上界値は，0-1 変数を連続変数に置き換えた連続ナップサック問題を解けば求められる．
例 6.1 で，I = { りんごポッキー，エンジェルクッキー }，O = { きのこの里，ポテトチップ } である中間
点で上界値を求めると，
解
あめ
ガム
1
1
りんご
ポッキー
1
きのこ
の里
0
ボタボタ
せんべい
1/5
ポテト
チップ
0
ラムネ
エンジェル
クッキー
1
1
で 22.8．この値は，貪欲算法で得られた下界値 24 よりも小さいので，この中間点の下に最適解が存在しない．
りんごポッキー
1
3
0
エンジェルクッキー
１
3
4
2
０
１
０
0
きのこの里
１
5
０
１
１
０
０
１
１
０
０
0
ポテチ１
０ １
１
０
０ １
０
１ ０
実行不可能
最適解なし
最適解なし
図 20: ナップサック問題の列挙の打ち切り
6. このように，列挙木の中間点で実行可能性やその下に最適解が存在するかどうかを調べてそれ以降の列挙を
打ち切る操作を限定操作という．これに対して，中間点から列挙を継続するために，固定する変数を選択し
て分岐を行なう操作を分枝操作という．
7. 分枝限定法 . . . 分枝操作と限定操作を繰り返して最適解を見つける方法．分枝限定法の過程で作成される列
挙木を分枝木ということもある．分枝限定法を進めていくなかで，現在まででもっともよい下界値を与える
解を暫定解，その値を暫定値という．分枝木のすべての中間点が打ち切られたとき，分枝限定法は終了し，
そのときの暫定解が最適解となる．
8. 分枝限定法は以下のように解釈することもできる．もとの問題
最大化
f (x)
条件
x∈S
30
の最適解をみつけることが困難であるとき，実行可能領域 S を S1 , · · · , Sk に分割し，子問題 i (i = 1, · · · k)
最大化
f (x)
x ∈ Si
条件
を作成する．ただし，S1 ∪ S2 ∪ · · · ∪ Sk = S ．これが分枝操作にあたる．そして各子問題の最適解を求める．
最適解を求めることが困難な場合はさらに小さな子問題に分割する．もし，分割した子問題すべての最適解
が得られたなら，その中でもっともよい解が元の問題の最適解となる．よって，この操作を再帰的に繰り返
せば分割した問題の最適解が得られる．また，子問題の最適解が得られなくても，子問題の実行可能領域内
に元の問題の最適解が存在しないことがわかれば十分．ここで分枝を打ち切れる．子問題を解き，さらに分
枝する必要があるかどうかを調べるのが限定操作である．分枝限定法では，分枝操作において，どのように
子問題に分割するか（すなわち列挙においてどの変数を固定するか），また，いくつかある子問題のどれか
ら限定操作を行なうかなどをうまく決めることが大切．
9. 例 6.1 に分枝限定法を適用してみよう．
前処理 暫定値を貪欲算法で得られた 24 とする．
分枝操作 1 I = { りんごポッキー }, O = ∅ とした子問題 1 と，I = ∅, O = { りんごポッキー } とした子問
題 2 を作成．
限定操作 1 子問題 1 は実行可能解をもつので連続緩和問題を解く．
解
あめ
ガム
1
1
りんご
ポッキー
1
きのこ
の里
0
ボタボタ
せんべい
0
ポテト
チップ
1
ラムネ
1
エンジェル
クッキー
16/21
となり，上界値は 26.1 で打ち切りはできない．
分枝操作 2 I = { りんごポッキー，エンジェルクッキー }, O = ∅ とした子問題 1-1 と，I = { りんごポッキー },
O = { エンジェルクッキー } とした子問題 1-2 を作成．
限定操作 2 子問題 1-1 は実行可能解をもつので連続緩和問題を解く．
解
あめ
ガム
0
1
りんご
ポッキー
1
きのこ
の里
0
ボタボタ
せんべい
0
ポテト
チップ
1
ラムネ
1
エンジェル
クッキー
1
となり，これは元問題の実行可能解であるので分枝を打ち切る．目的関数値は 26 で暫定値よりもよい
ので，暫定解を更新する．
限定操作 3 子問題 1-2 は実行可能解をもつので連続緩和問題を解く．
解
あめ
ガム
1
1
りんご
ポッキー
1
きのこ
の里
16/20
ボタボタ
せんべい
0
ポテト
チップ
1
ラムネ
1
エンジェル
クッキー
0
となり，上界値は 25.6 で暫定解よりも小さいので，ここで打ち切る．
限定操作 4 子問題 2 は実行可能解をもつので連続緩和問題を解く．
解
あめ
ガム
1
1
りんご
ポッキー
0
きのこ
の里
2/5
ボタボタ
せんべい
0
ポテト
チップ
1
ラムネ
となり，上界値は 22.8 で暫定解よりも小さいので，ここで打ち切る．
ここで分枝限定法は終了し，現在の暫定解が最適解となる．
31
1
エンジェル
クッキー
1
0 0g26.1
¡ @
りんごポッキー ¡
1
@0
@
¡
@
¡
130 1g26.1
0 4g22.8
·T
エンジェルクッキー ·1
T0
·
TT
·
340 2g26 130 3g25.6
図 21: ナップサック問題の例への分枝限定法の適用．各頂点の左の数字はそれまでに 1 に固定されたお菓子の合
計金額，右がその頂点での子問題の上界値をあらわす．
6.5
切除平面法
1. 切除平面法とは，整数計画問題において，連続緩和問題の解がもとの実行可能解でないときに，新たな制約
（線形不等式）を追加することを繰り返し，最適解を求める方法．追加する制約（線形不等式）は連続緩和
問題で得られた実行不可能解では満たさず，すべての実行可能解では満たすものである．
2. すべての実行可能解で満たされる制約（線形不等式）を妥当不等式という．すなわち，実行可能領域 S =
{x | Ax ≤ b, x ≥ 0, x : 整数 } であるとき，任意の x ∈ S で πx ≤ π0 を満たすような不等式のことを妥当
不等式という．
3. 5.2 緩和問題 3 の例：
x2
6
r
r
r
r
r
r
¢
b
¢
À b3x1 + 5x2 ≤ 47
2
b
r
d
rd
r
r
r
r ¢¢
b
b
b
¢
b
x1 ≤ 4
r
d
rd
rd b r ¾r 妥当不等式
r¢
b
¢
b
b
¢
r
d
rd
rd
rd
rdb
t r ©
AKx − 2x ≤ 2
b¢b
1
2
¢
©
b
¢©©b
r
d
rd
rd
rd ©rd¢© r b
©©¢¢
©
r
d
rd ©rd© r ¢ r
r
- x1
O
©
©
¢
Y
H
©
2x − x2 ≤ 7
¢ 1
4. いろいろな妥当不等式（カット）5 ：以下では，S = {x | Ax ≤ b, x ≥ 0, x : 整数 } の妥当不当式を考える．
(a) 整数丸めカット：不等式
∑n
i=1
∑n
ai xi ≤ b が S の妥当不等式のとき，u > 0 に対して， i=1 ⌊uai ⌋xi ≤ ⌊ub⌋
は S の妥当不等式である．
∑n
∑n
(b) Gomory カット：不等式 i=1 ai xi = b が S の妥当不等式のとき， i=1 (ai − ⌊ai ⌋)xi ≥ b − ⌊b⌋ は S の
妥当不等式である．
5 このほかにもたくさん妥当不等式は提案されている．とくに，混合整数計画問題に対して，Mixed Integer Rounding cut (MIR) や
Gomory mixed cut がよいとされている
32
(c) 持ち上げ：S ⊆ {0, 1}n ，すなわち，S の各変数は 0 か 1 の値をとるとき，S 1 = {x ∈ S | x1 = 1},
S 0 = {x ∈ S | x1 = 0} とする．
∑n
∑n
i. 不等式 i=2 ai xi ≤ b が S 0 の妥当不等式であり，max{ i=2 ai xi | x ∈ S 1 } ≤ b − a1 ならば，
∑n
i=1 ai xi ≤ b は S の妥当不等式である．
∑n
∑n
ii. 不等式 i=2 ai xi ≤ b が S 1 の妥当不等式であり，max{ i=2 ai xi | x ∈ S 0 } ≤ b + a1 ならば，
∑n
i=1 ai xi ≤ b + a1 は S の妥当不等式である．
5. 例 6.1 に対して，妥当不等式をつくる．制約式:
50xあめ + 10xガム + 130xポッキー + 200xきのこ + 150xせんべい + 80xポテチ + 70xラムネ + 210xクッキー ≤ 500
に u = 1/100 をかけて整数丸めカット得ると，
xポッキー + 2xきのこ + xせんべい + 2xクッキー ≤ 5
xきのこ を固定して，
S̃ 1 = {x | 50xあめ +10xガム +130xポッキー +150xせんべい +80xポテチ +70xラムネ +210xクッキー ≤ 500−200 = 300, xi ∈ {0, 1}}
S̃ 0 = {x | 50xあめ + 10xガム + 130xポッキー + 150xせんべい + 80xポテチ + 70xラムネ + 210xクッキー ≤ 500, xi ∈ {0, 1}}
とする．S̃ 1 の制約式に u = 1/100 をかけて整数丸めカットを得ると，
xポッキー + xせんべい + 2xクッキー ≤ 3
（これは，S̃ 1 の妥当不等式．
）max{xポッキー + xせんべい + 2xクッキー | x ∈ S̃ 0 } = 4 なので，
xポッキー + xきのこ + xせんべい + 2xクッキー ≤ 3 + 1 = 4
は持ち上げによる妥当不等式である．S̃ 0 の制約式に u = 1/100 をかけて整数丸めカットを得ると，
xポッキー + xせんべい + 2xクッキー ≤ 5
（これは，S̃ 0 の妥当不等式．
）max{xポッキー + xせんべい + 2xクッキー | x ∈ S̃ 1 } = 2 なので，
xポッキー + 3xきのこ + xせんべい + 2xクッキー ≤ 5
は持ち上げによる妥当不等式である．
6.6
動的計画法
1. 動的計画法とは，与えられた問題をいくつかの部分問題に分割し，小さな部分問題から順に大きな部分問題
を解いていき，最適解を得る方法．最適条件を漸化式で表す．
2. 0-1 ナップサック問題に対する動的計画法 1：
2 つのパラメータ d, k を導入した問題
最大化
k
∑
c i xi
i=1
条件
k
∑
ai xi ≤ d
i=1
xi ∈ {0, 1}
の最適値を z(d, k) とする．
33
(i = 1, · · · , k)
• z(b, n) はもとの 0-1 ナップサック問題の最適値．
•
{
z(d, 1) =
•
{
z(d, k) =
0
(a1 > d)
c1
(a1 ≤ d)
max{z(d, k − 1), ck + z(d − ak , k − 1)}
(ak ≤ d)
z(d, k − 1)
(ak > d)
d = 0, 1, · · · , b に対して z(d, k − 1) の値がわかっていれば，この漸化式を用いて z(d, k) を計算することがで
きる．d と k の表を作ると簡単に計算可能．
（ただし，ai はすべて整数を仮定）
例 6.1 に動的計画法を適用しよう．
k\d
あめ
ガム
ポッキー
きのこ里
0
0
0
0
0
10
0
1
1
1
20
0
1
1
1
30
0
1
1
1
40
0
1
1
1
50
2
2
2
2
60
2
3
3
3
70
2
3
3
3
80
2
3
3
3
90
2
3
3
3
100
2
3
3
3
110
2
3
3
3
120
2
3
3
3
130
2
3
8
8
140
2
3
9
9
150
2
3
9
9
160
2
3
9
9
170
2
3
9
9
180
2
3
10
10
190
2
3
11
11
200
2
3
11
11
..
.
3. z(d, k), d = 1, . . . , b, k = 1, . . . , n が得られたとき，
最適解の求め方
ステップ 0 d := b, k := n
ステップ 1 z(d, k) = z(d, k − 1) ならば， xk = 0 とし，そうでなければ xk = 1, d = d − ak とする．
ステップ２ k ≤ 1 ならば終了．そうでなければ，k = k − 1 として，ステップ１へ．
4. ナップサック問題に対する動的計画法は，ナップサックの容量 b と変数の数に計算の回数が依存．⇒ b が小
さな問題に対しては，効果的．
5. もう少し，小さな例：
アイテム
1
2
3
4
ci
1
2
4
3
ai
3
2
4
2
で b=5 である 0-1 ナップサック問題を解く．
k\d
0
1
2
3
4
5
1
0
0
0
1
1
1
2
0
0
2
2
2
3
3
0
0
2
2
4
4
4
0
0
3
3
5
5
z(b, n) が決まった経路を逆にたどれば，ナップサックの解を得る．
34
210
2
3
11
11
···
···
···
···
···
6. 0-1 ナップサック問題に対する動的計画法 2：
∑
∑
d(z, k) = min{
ai | S ⊆ {1, . . . , k},
ci = ｚ }
とする．つまり，価値の和
∑
i∈S ai .
i∈S
∑
i∈S
がちょうど z となる {1, . . . , k} のアイテムの組合せのなかで，最小の
i∈S ci
• max{z | d(z, n) ≤ b} がもとの 0-1 ナップサック問題の最適値．
• z は 0 からもとの 0-1 ナップサック問題の上界値 Z まで動かす．上界値としては，たとえば，
•
∑n
i=1 ci
や連続ナップサック問題の最適値など．
0
d(z, 1) =
{
d(z, k) =
(z = 0)
a1 (z = c1 )
∞ (それ以外)
min{d(z − ck , k − 1) + ak , d(z, k − 1)} (ck ≤ z)
d(z, k − 1)
(ck > z)
z = 0, 1, . . . Z に対して，d(z, k − 1) の値がわかっていれば，この漸化式を用いて，d(z, k) を計算すること
ができる．z と k の表を作ると簡単に計算可能．
（ただし，ci はすべて整数を仮定）
7. 5．の例に適用しよう．上界値 Z =
∑n
i=1 ci
とする．
k\z
0
1
2
3
9
10
1
0
3
∞
∞ ∞ ∞ ∞ ∞ ∞ ∞
∞
2
0
3
2
5
∞ ∞ ∞ ∞ ∞ ∞
∞
3
0
3
2
5
4
7
6
9
∞
∞
∞
4
0
3
2
2
4
4
6
6
9
8
11
4
5
6
7
8
max{z | d(z, n) ≤ b} が決まった経路を逆にたどれば，ナップサックの解を得る．
6.7
近似解法
1. 最適解の近似を効率的に計算．ある ε に対して，最適解よりも ε% だけ悪い解を許す場合に，効率よく解を
みつける．
2. 近似比 (=
最適値
)
得られた解の目的関数値
が悪くても２のアルゴリズム
(得られた解の値は，悪くても，最適値の 1/2 以上)
2 近似算法
0-1 ナップ サック 問 題 に 対 し て 貪 欲 算 法 を 適 用 し て 得 ら れ た 解 を x̂ と す る ．貪 欲 算 法 終 了 後 ，
n
∑
ci x̂i < max{ci | x̂i = 0} ならば，cp = max{ci | x̂i = 0} である添字 p に対して，
i=1
{
x̃i =
とし，
n
∑
1 (i = p)
0 (i ̸= p)
ci x̂i ≥ max{ci | x̂i = 0} ならば，x̃ = x̂ とする．
i=1
35
∑n
ci x∗i
≤ 2 となる．
3. 定理 6.3 最適解を x∗ としたとき，近似比： ∑i=1
n
i=1 ci x̃i
∑n
∑n
証明：
i=1 ci x̂i + cp は，連続ナップサック問題の最適値より小さくはない．よって， i=1 ci x̂i + cp ≥
∑n
∗
i=1 ci xi がなりたち，
n
n
n
∑
∑
1∑
ci x̂i , cp } ≥
ci x̃i = max{
ci x∗i 2
i=1
i=1
i=1
4. 2 近似算法で得られた解の値を２倍すれば，上界値として使える．
5. もっと時間をかけて良いので，近似比が小さくなるアルゴリズムは．
．
．
解の精度と計算時間のトレードオフ．
6. 任意の ε > 0 に対して，近似比が悪くても (1 + ε) のアルゴリズム（ただし，ci はすべて整数のとき）
（ε が小さいと最適値に近づく）
(1 + ε) 近似算法
ステップ 0 2 近似算法で解 x̃ を求める．z̃ =
ステップ 1 t =
εz̃
n
∑n
i=1 ci x̃i
とする．
とし，c̄i = ⌊ci /t⌋ とする．
ステップ 2 c̄ に対する 0-1 ナップサック問題の最適解 x̄ をみつける．
（動的計画法２を使う．上界値 Z = 2z̃/t
とできる．
）
ステップ 3
∑
ci x̃i と
∑
ci x̄i の大きい方の解を x̌ として出力．
∑n
ci x∗i
≤ 1 + ε となる．
定理 6.4 最適解を x としたとき， ∑i=1
n
i=1 ci x̌i
∗
証明：
ci
ci
− 1 < c̄i ≤
なので，
t
t
∑
∑
∑
∑
∑
∑
∑
ci x̄i ≥ t
c̄i x̄i ≥ t
c̄i x∗i >
(ci − t)x∗i ≥
ci x∗i − tn =
ci x∗i − ε
ci x̃i
よって，
∑
ci x̌i >
∑
ci x∗i − ε
• ステップ 2 で動的計画法の 2 を使うと，上界 Z =
で，ci の大きさに無関係．
∑
ci x̌i
2z̃
2n
2n
=
となり，表の大きさは，
× n となるの
t
ε
ε
• ε が小さくなると表が大きくなり，計算時間がかかるようになるが，最適解に近づく．
36
演習問題
問題 25: 以下の 0-1 ナップサック問題を分枝限定法を用いて解け．ただし，分枝変数（新たに固定する変数）は，
各問題の連続緩和問題を解いたときに連続値となった変数とせよ．
最大化
条件
7x1 + 12x2 + 8x3 + 5x4 + 10x5
2x1 + 3x2 + 5x3 + 2x4 + 8x5 ≤ 11
xi ∈ {0, 1}
(i = 1, 2, 3, 4, 5)
問題 26: 問題 25 のナップサック問題を２通りの動的計画法で解け．
問題 27: 以下のナップサック問題を分枝限定法を用いて解け．
最大化
条件
x1 + 8x2 + 7x3 + 2x4
3x1 + 8x2 + 6x3 + 3x4 ≤ 27
x1 , x4 ∈ {0, 1, 2, 3, 4}
x2 , x3 ∈ {0, 1, 2}
問題 28: 整数丸めカットが妥当不等式であることを示せ．
問題 29: 例 6.1 に対し，xきのこ 以外を固定したときの持ち上げによる妥当不等式を導け．
問題 30: 連続ナップサック問題
最大化
n
∑
c i xi
i=1
条件
n
∑
ai xi ≤ b
i=1
0 ≤ xi ≤ 1
(i = 1, · · · , n)
に対して，
1. 双対問題と相補性の条件を述べよ．
2. 6.2 節で述べたアルゴリズムで得られる解が連続ナップサック問題の最適解であることを示せ．
（相補性
を満たすように双対変数を定め，これらが双対条件を満たすことを示せばよい）
問題 31: ２通りの動的計画法の長所短所を述べよ．どのような問題にどちらを用いるのがよいか．
37
問題 32: 2 近似算法で最適解が得られない問題例を作成せよ．
問題 33: (1 + ε) 近似算法のステップ 1 で t = max{1, εz̃
n } としても近似比が悪くならないことを示せ．
解法の代表的な枠組の復習（別問題への適用）
7
7.1
貪欲解法
1. 局所的な情報から解を順次構成していく方法．
2. 0-1 ナップサック問題では，近似解法に一役買っていた．
3. 問題の構造によってうまく働く場合と，まったくダメな場合とある．
(a) うまく働く例「最小木問題」
入力： 連結な無向グラフ G = (V, A) と各枝 a の費用 c(a).
出力： 枝の費用の和が最小となる全域木
集合 T は枝を格納する．アルゴリズムが終わったとき T の枝からなる全域木が出力される．
貪欲算法（最小木問題）
ステップ 0: c(a1 ) ≤ c(a2 ) ≤ · · · と費用を昇順に並べる．T = ∅, j = 1 とする．
ステップ 1: T に aj を加えても，閉路ができないとき，T := T ∪ {aj } とする．
ステップ 2: すべての枝を調べたならば終了．そうでなければ，j = j + 1 としてステップ 1 へ．
定理 7.1 貪欲解法は最小木問題の最適解をみつける．
(b) ダメな例「巡回セールスマン問題」
入力： 完全グラフ G = (V, A) と各枝 a の費用 c(a).
出力： 枝の費用の和が最小となる巡回路（すべての頂点をちょうど１度ずつ通る閉路）
集合 T は枝を格納する．アルゴリズムが終わったとき T の枝からなる巡回路が出力される．
貪欲算法（巡回セールスマン問題）
ステップ 0: c(a1 ) ≤ c(a2 ) ≤ · · · と重みを昇順に並べる． T = ∅, j = 1 とする．
ステップ 1: T ∪ {aj } をすべて含む巡回路があるとき，T := T ∪ {aj } とする．
ステップ 2: T が巡回路を構成したら終了．そうでなければ，j = j + 1 としてステップ 1 へ．
7.2
分枝限定法
1. 基本的には全列挙．分枝操作，限定操作は問題の構造を活かして工夫．
2. ナップサック問題は分枝限定法で比較的容易に解けることが知られている．
38
1 vk
vk
2
4
2¶ @ 1
1¡ S2
@
S ¶
¡
vk
vk
6
1
S
¶
@1
¶ S
¡
1
@ ¶
S ¡
k
k
v3
M v5
図 22: 貪欲算法で良い解が得られない巡回セールスマン問題の例．枝上の数字はその枝の費用．
3. 巡回セールスマン問題を分枝限定法で解いてみよう．
¶
³
巡回セールスマン問題は最小化問題だから，ナップサック問題の時と下界値，上界値の役割が逆転する
ことに注意！
µ
´
分枝操作 各枝を巡回路として通るか通らないかで２つに分ける．
• 必ず通ると固定されている枝の集合=I
• 必ず通らないと固定されている枝の集合=O
• 残りの固定されていない枝の集合=F
限定操作 実行可能性のチェック．下界値計算．
• I を含み O を含まない巡回路が存在するか．存在しなければ，実行不可能となり打ち切り．巡回路
が唯一にきまれば，打ち切り．
• I を含み O を含まない巡回路の下界値として，
「I の枝の費用の和+F の中から小さい順に巡回路を
構成するのに必要な枝数分の費用の和」を用いる．暫定値 < 下界値ならば打ち切り．
図 23 に対する巡回セールスマン問題に適用してみよう．暫定解を巡回路 (1-2-3-4-5-1) とすると，暫定値は
5
²¯
²¯
2
2
4
±°
±°
2
¶
1 ¡ S4
¡
S
¶
²¯
¡
S ¶
1
¶
S
2
6
±°
@
¶ S
4@
S ²¯
¶
@²¯
S
¶
3
5
1
±°
±°
4
図 23: 巡回セールスマン問題の問題例．枝上の数字はその枝の費用．
15. 以降，分枝限定法における分枝木の例を図 24 に示す．
7.3
動的計画法
1. 小さな自明な部分問題から順に大きな部分問題を解いていき，最適解を得る方法．
2. 巡回セールスマン問題に対する動的計画法
頂点 V = {1, 2, . . . , n} とする．任意の U ⊆ {2, . . . , n} と x ∈ U に対し，t(U, x) を {1} ∪ U のすべての頂点
を経由する 1 から x への道の最小の費用とする．
39
0g
¡ @
@
¡
@
¡
I = {a12 } ¡
= {a12 }
@O
g11
10
8 1g
¡ @
¡
@
¡
@
I = {a12 , a23 } ¡
@ gI = {a12 }, O = {a23 }
g
2
5 10
8
¯\
¿T
¿ I = {a
T 12 , a23 } I = {a12¯, a24 }\
I = {a12 , }
\\O = {a23 , a24 }
O =T
{a
O = {a¯¯23 }
I = {a12 , a23 , a34 } ¿
34 }
T
¿
3g
4g
6g
9g12
15 (1-2-3-4-5-1)
15 (1-2-3-5-4-1) ¯ L10
¯ L
I = {a , a }
I = {a12 , a24 , a43 }
¯
L O = {a1223 , a2443 }
O = {a23 } g
g
7
8
10(1-2-4-3-5-1) 14(1-2-4-5-3-1)
図 24: 巡回セールスマン問題の例への分枝限定法の適用．各頂点の数字は下界値を表す．
• min{t({2, . . . , n}, x) + c(x, 1) | x ∈ {2, . . . , n}} が最適値
• t({x}, x) = c(1, x)
• t(U, x) = min{t(U \ {x}, y) + c(y, x) | y ∈ U \ {x}}
図 23 の例を解いてみよう．
\ x
{2}
{3}
{4}
{5}
{2, 3}
{2, 4}
{2, 5}
{3, 4}
{3, 5}
{4, 5}
{2, 3, 4}
{2, 3, 5}
{2, 4, 5}
{3, 4, 5}
{2, 3, 4, 5}
2
1
6
7
8
8
7
12
9
3
4
3
7
5
5
6
12
10
4
5
3
6
10
5
10
7
8
5
4
5
5
11
4
9
8
6
t({2, 3, 4, 5}, x) + c(x, 1)
10
14
13
10
U
3. 最短路問題に対するアルゴリズムも動的計画法の一例．
7.4
近似解法
1. 最適解をみつけるのが困難なとき，なるべく良い解を効率よく求める．
2. “メトリック巡回セールスマン問題” に対する近似解法．
40
メトリック巡回セールスマン問題
枝の重み c > 0 が三角不等式，すなわち，任意の u, v, z ∈ V に対し，
c(u, v) + c(v, z) ≥ c(u, z)
を満たす巡回セールスマン問題．
近似比 (=
得られた解の目的関数値
)
最適値
が悪くても 2 のアルゴリズム. (巡回セールスマン問題は最小化問題なので，
最大化問題のときと近似比が分母，分子逆になっていることに注意．)
2 近似算法
ステップ 0: c を重みとした最小全域木を求める．最小全域木の枝集合を T とする．
ステップ 1: T の枝を２回ずつ通る路 T ′ を構成する．
ステップ 2: 路 T ′ をたどりながら，一度通った頂点は通過するようにして巡回路を構成する．
図 23 の例を解いてみよう．
4k
2k
2¶
1¡
¶
¡
1k 2
¶
¶
¶
3k 1 5k
4k
2k
7
¶
µ
¡
¶
¡6
¶¶
¡
¡
¡
ª
k
1
¶¶
¶¶
¶
?
/
¶
¾ - 5k
3k
最小全域木 T
T′
2k
¡
1k
K
µ
¡
¶
¶
¶
¶
?
3k
7
¶
4k
?
5k
巡回路
∑
c(a)
定理 7.2 2 近似算法で得られた巡回路の枝集合を T̂ 最適な巡回路の枝集合を T とすると，近似比: ∑ a∈T̂
≤2
a∈T ∗ c(a)
となる．
∗
証明：
∑
∑
• 巡回路から任意の枝を取り除くと全域木となるので， a∈T c(a) < a∈T ∗ c(a).
∑
∑
• T ′ の構成法より， a∈T ′ c(a) = 2 a∈T c(a)
∑
∑
• 枝の重みが三角不等式を満たすので， a∈T̂ c(a) ≤ a∈T ′ c(a)
∑
∑
以上より， a∈T̂ c(a) ≤ 2 a∈T ∗ c(a)
3. 巡回セールスマン問題に対して，任意のパラメータ ε(> 1) に対し，最適値の ε 倍以下の解を求める近似解
法はできない（と信じられている）
演習問題
問題 34: 貪欲解法は最小木問題の最適解をみつけることを証明せよ．
41
問題 35: 巡回セールスマン問題の下界値を求める方法を調べよ．
問題 36: 図 25 の巡回セールスマン問題を分枝限定法，動的計画法で解け．
5
7
²¯
²¯
7
4
2
±°
±°
5¶ @ 8
3 ¡ S4
¡
@
S
¶
²¯
¡
@²¯
S ¶
6
1
¶
S
6
±°
±° 3
@
¡
¶ S
1@
¡3
¶
S ²¯
@²¯
¶
S ¡
3
5
2
±°
±°
4
3
2
図 25: 巡回セールスマン問題の問題例．枝上の数字はその枝の費用．
問題 37: n 頂点の巡回セールスマン問題に対する動的計画法では表の大きさはどのくらいになるか．
問題 38: 最短路問題に対するアルゴリズムが動的計画法とみなせる理由を説明せよ．
問題 39: 巡回セールスマン問題に対する近似解法について調べよ．
42
おまけ
巡回セールスマン問題の実行可能解の個数 (n − 1)!/2 / 2.8 × 1057 / 1030 世紀以上
x2
ちなみに，ビックバン依頼経過した推定秒数は 1021 ．
6
連続緩和問題を解く ¢
r
r
r
r
r
r
b
¢
À b3x1 + 5x2 ≤ 47
2
b
r
d
rd
r
r
r
r ¢
b
¢
b
b
¢
b
r
d
rd
rd b r
r
r¢
b
¢
b
b
b¢b
r
d
rd
rd
rd
rdb
AKx − 2x ≤ 2
t¢ r ©
1
2
¢
©
b
¢©©b
r
d
rd
rd
rd
rd¢© r b
©
¢
©
©
r
d
rd ©rd©© r ¢¢ r
r
- x1
O
©
Y¢2x − x ≤ 7
H
©©
2
¢ 1
6
b
qb bbq
@
b @
b @
bq
bq
bq b
b@
b
@
bq
bq
bq
bq b
bq r ( 9 , 2)
opt. ¢@ 2
bq
bq
bq
bq ©bq¢ @
©
@
©
bq
bq
bq©
-@
O
@
6
6
b
qb bbq
b
b
bq
bq
bq b
b
b
bq
bq
bq
bq b
bq
¢
bq
bq
bq
bq ©bq¢ opt.
©
bq
bq
bq©©
O
43
b opt.
bq bbq
b
bQ
bq
qb qbQ
bQ
bQ
b
Q
bq
qb qb qb b
qb r
¢Q
bq
qb qb qb ©qb¢ QQ
©
Q
Q
bq
qb qb©©
O