コンピュータ基礎特論

Ａ０４班：組み合わせ最適化における指数
サイズ多項式時間近傍の設計
明治大学理工学部情報科学科
玉木久夫井口幸洋
目次
１．アプローチの概要
２．理論的基礎：分枝分割アルゴリズム
３．具体的な問題への応用
アプローチの概要
基本的には局所探索
近傍を巨大（指数サイズ）にとる
– 悪い局所最適に補足される可能性を低下させたい。
– 多項式時間で近傍内の最適化ができるように近傍を
設計する。
– 主なツール：「幅」の小さい分割が可能なグラフを利
用した動的計画法
– 具体的な問題：巡回セールスマン問題、集合被覆問
題、クリーク被覆問題、グラフ描画問題 …
理論的な基礎：グラフの分枝分割
定義[Robertson & Seymour 91] グラフGの分枝分割とは、
Gの辺集合を葉集合とし、内部頂点の次数３であるような
木のことを言う。
• 木の辺が、グラフのカット（頂点集合）に対応
cf. 木分割では、木のノードがカット（頂点集合）に対応
• 分枝分割Tの幅： Tの辺に対応するカットの大きさの最
大値
• グラフGの分枝幅： Gの分枝分割の幅の最小値
• 分枝幅決定問題[Seymour & Thomas 94]：
一般のグラフではＮＰ完全
平面グラフではO(n2)時間アルゴリズム（刻み幅決定問題に帰着）
分枝分割と木分割：例
Gの分枝分割の例
G
2
f
e
c
4
3
h
g
b
g
i
a
d
b
f
c
a
1
e
5
d
Gの木分割の例
i
2,4,5
6
1,2,3
2,3,5
3,5,6
h
分枝分割と木分割：例
Gの分枝分割の例
G
2
f
e
c
4
3
h
g
b
g
i
a
d
b
f
c
a
1
e
5
d
Gの木分割の例
i
2,4,5
6
1,2,3
2,3,5
3,5,6
h
分枝分割と木分割：例
Gの分枝分割の例
G
2
f
e
c
4
3
h
g
b
g
i
a
d
b
f
c
a
1
e
5
d
Gの木分割の例
i
2,4,5
6
1,2,3
2,3,5
3,5,6
h
刻み分割
G
2
f
4
a
1
e
c
g
d
b
3
h
定義グラフGの分枝分割とは、
Gの頂点集合を葉集合とし、内
部頂点の次数３であるような木
のことを言う。
4
5
3
i
6
5
2
1
6
刻み分割
G
2
f
4
a
1
e
c
g
d
b
3
h
定義グラフGの分枝分割とは、
Gの頂点集合を葉集合とし、内
部頂点の次数３であるような木
のことを言う。
4
5
3
i
6
5
2
1
6
平面グラフの分枝分割アルゴリズムの改良
Seymour と Thomas によるO(n4) 時間アルゴリズム
O(n2)時間の幅決定手続きをO(n2) 回呼び出す
→ 幅決定手続きの呼び出しはO(n) 回、それ以
外の幅決定は、O(n)時間で以前の呼び出し結果
から判断 … O(n3) 時間アルゴリズム
Qianping Gu 氏と共著
ICALP 05
ACM Transactions on Algorithms (accepted 07)
平面グラフの刻み幅決定
理解の努力と拡張の試み
ねずみ捕りゲーム
環境：平面グラフ G, 正整数 k
プレイヤ：ねずみ
ねずみ捕り
– ねずみは G の頂点に住み、辺を通って移動する。
– ねずみ捕りはG の面に住み、双対辺を通って移動する。
– お互いに、相手が見える。
– ねずみ捕りは、騒音を発してねずみの移動を妨害する。
Gの辺 e が通行不能  e とねずみ捕りのいる面または辺を通る、
長さ k 未満の閉じた双対歩道が存在する。
e
ゲームの手順
（１）
が面を選ぶ
（２）
が頂点を選ぶ
以下のラウンドを繰り返す
(a)
が現在の面に接する辺を選び、その上に移動
(b)
が通行可能な辺を（いくつでも）通って行ける頂
点を選び移動
(c)
が、辺から今までいたのと反対の面に移動
k=4
ゲームの手順
（１）
が面を選ぶ
（２）
が頂点を選ぶ
以下のラウンドを繰り返す
(a)
が現在の面に接する辺を選び、その上に移動
(b)
が通行可能な辺を（いくつでも）通って行ける頂
点を選び移動
(c)
が、辺から今までいたのと反対の面に移動
k=4
ゲームの手順
（１）
が面を選ぶ
（２）
が頂点を選ぶ
以下のラウンドを繰り返す
(a)
が現在の面に接する辺を選び、その上に移動
(b)
が通行可能な辺を（いくつでも）通って行ける頂
点を選び移動
(c)
が、辺から今までいたのと反対の面に移動
k=4
ゲームの手順
（１）
が面を選ぶ
（２）
が頂点を選ぶ
以下のラウンドを繰り返す
(a)
が現在の面に接する辺を選び、その上に移動
(b)
が通行可能な辺を（いくつでも）通って行ける頂
点を選び移動
(c)
が、辺から今までいたのと反対の面に移動
k=4
ゲームの手順
（１）
が面を選ぶ
（２）
が頂点を選ぶ
以下のラウンドを繰り返す
(a)
が現在の面に接する辺を選び、その上に移動
(b)
が通行可能な辺を（いくつでも）通って行ける頂
点を選び移動
(c)
が、辺から今までいたのと反対の面に移動
k=4
ゲームの手順
（１）
が面を選ぶ
（２）
が頂点を選ぶ
以下のラウンドを繰り返す
(a)
が現在の面に接する辺を選び、その上に移動
(b)
が通行可能な辺を（いくつでも）通って行ける頂
点を選び移動
(c)
が、辺から今までいたのと反対の面に移動
k=4
勝敗決定
の勝利（
の捕捉）：
が
のいる頂点と接する面にいて、
のいる頂点の次数が k 未満である。
k=4
の勝利＝永久に捕捉を免れる
平面グラフの刻み幅の特徴付け
定理（Seymour&Thomas 94)
G: 平面グラフ
k: 正整数
Gの刻み幅が k 以上
⇔ (G, k)上のねずみ捕りゲームがねずみ必
勝
ねずみ捕りゲームの理解と拡張の試み
• ねずみ捕りゲームによる特徴付けの理解を、幅
決定アルゴリズムの実際的な改良に生かす。
–
ねずみ捕捉の局所的な十分条件
• ねずみ捕りゲームの拡張（努力中）
– ひとつの交差で平面に描画できるグラフ
– 線形ボンド分割の最適幅決定
局所的捕捉
ねずみ取りが面 f, ねずみが頂点 vにいる状態がねずみ取
り必勝であるための十分条件:
vの次数が k 未満で、図の赤と青の閉じた双対歩道のどち
らも長さが k 未満
v
f
•刻み幅決定アルゴリズムの前処理に利用
メモリと計算時間の節約
•すべての頂点が、ひとつの面からこの条件で捕捉される
場合： Tamaki02 の線形時間刻み分割ヒューリスティック
具体的な問題（１）巡回セールスマン問題
• 特定研究発足前に、巨大近傍アプローチによっ
て発見したツアー（ＴＳＰＬＩＢの d18512) の最適
性が Cook ら（2005) によって示された。
• 刻み分割に基いた平面グラフＴＳＰソルバの改良
整備をした。
• 平面グラフソルバのユークリッド距離ＴＳＰヒュー
リスティックへの応用：解構築、改良のあらゆる
段階でさまざまな案を実装・実験した。
具体的な問題（2）集合被覆問題
近傍：現在解において、選択されている集合のい
くつかを開放し、他の集合で置き換えて得られる
解
ハイパーグラフの分枝分割に基いた近傍内最適化
アルゴリズムを実装・実験した。
具体的な問題（３）グラフ描画問題
（１）平面グラフのコンパクト描画問題
頂点は整数格子点
辺は直線分
辺長２乗和最小化問題として定式化
近傍：すべての頂点を独立に隣接点に移動してできる解
（２）平面グラフの低縮退描画問題
頂点は整数格子点
辺は直線分
隣接２辺のなす角の正弦の絶対値の最小値を最大化
近傍：８通りの方向ベクトルのひとつに対し、各頂点を独立にその
方向に移動するまたは移動しないでできる解
近傍内最適化：分枝分割に基いた動的計画法
小近傍アプローチと比較して効果を確認

Download Report