Document

点素パス問題に対するアルゴリズム
小林佑輔
東京大学大学院情報理工学系研究科
組合せ最適化セミナー 2012 年 7月 13日
最短点素パス問題
講演内容


イントロダクション
効率的に解けるケース
 ２点素パス問題
 k点素パス問題
（Robertson-Seymour のアルゴリズム）
 その他の結果



最短点素パス問題
演習
近年の発展（最大点素パス問題）
最短点素パス問題 (Min-Sum)
Input: 頂点対 (s1, t1),…, (sk, tk)，各辺 e の長さ l(e)
Find: 点素パス P1,…, Pk (Pi : si → ti )
s.t. パスの合計長さ最小
 自然な最適化問題
 ほとんどの場合で計算複雑度が未解決
最短点素パス問題 (Min-Sum)
Input: 頂点対 (s1, t1),…, (sk, tk)，各辺 e の長さ l(e)
Find: 点素パス P1,…, Pk (Pi : si → ti )
s.t. パスの合計長さ最小
s1
 自然な最適化問題
 ほとんどの場合で計算複雑度が未解決
s2
s3
t1
t2
解決済のケース
 NP困難な点素パス問題に対応
NP困難
 最小費用流問題に帰着できる場合
多項式時間
 平面グラフで，s1,..., sk が同一面上，t1,..., tk が同一面上
多項式時間（Colin de Verdière & Schrijver, 2008）
t3
参考：点素パス問題の計算量
k : 定数
k : 変数
有向グラフ
無向グラフ
NP-困難
多項式時間 (平面グラフ)
多項式時間 (非巡回的)
NP-困難
多項式時間
線形時間 (平面グラフ)
k : 頂点対数
NP-困難
Min-Sum 点素パス問題の難しさ
点素パス問題
 難しさ
：頂点対の繋ぎ方が指定されている
 解法の鍵：繋げるか否かに関係ない頂点を取り除く
組み合わせるのが困難
最小費用流問題
 難しさ
：費用が最小である保証が必要
 解法の鍵：フローの多面体的表現＋双対概念
Min-Sum 点素パス問題の難しさ
点素パス問題
 難しさ
：頂点対の繋ぎ方が指定されている
 解法の鍵：繋げるか否かに関係ない頂点を取り除く
組み合わせるのが困難
最小費用流問題
 難しさ
：費用が最小である保証が必要
 解法の鍵：フローの多面体的表現＋双対概念
多項式時間で解ける場合
 最小費用流問題に帰着できる場合
 平面グラフで，s1,..., sk が同一面上，t1,..., tk が同一面上
（Colin de Verdière & Schrijver, 2008）
現状：最小費用流問題＋グラフの特殊性の利用
Min-Sum 点素パス問題の難しさ
点素パス問題
難しいポイント
難しさ
：頂点対の繋ぎ方が指定されている
 解法の鍵：繋げるか否かに関係ない頂点を取り除く
 カット条件
最小費用流問題
 幾何的な条件
+組み合わせるのが困難
最適性
 難しさ
：費用が最小である保証が必要
を同時に扱う必要がある
 解法の鍵
：フローの多面体的表現＋双対概念
多項式時間で解ける場合
 最小費用流問題に帰着できる場合
 平面グラフで，s1,..., sk が同一面上，t1,..., tk が同一面上
（Colin de Verdière & Schrijver, 2008）
現状：最小費用流問題＋グラフの特殊性の利用
Min-Sum 点素パス問題に対する成果
(K. and Sommer, 2009)
成果：特殊ケースの解決
無向平面グラフでターミナルが高々２つの面上にあるとき
k=2 の Min-Sum 点素パス問題は多項式時間で解ける
s1
t1
t2
t2
s2
本研究
s1
s2
s1
t1
s2
t1
t2
Colin de Verdière & Schrijver
t1
t2
s1
s2
最小費用流問題
Min-Sum 点素パス問題の難しさ
 カット条件
 幾何的な条件
+ 最適性
を同時に扱う必要がある

これまで紹介：
「幾何的な条件」が扱いやすいケース

これから話す：
「カット条件」が扱いやすいケース
J. Erickson and A. Nayyeri:
Shortest non-crossing walks in the plane, SODA 2011
Shortest non-crossing walks
Input: 頂点対 (s1, t1),…, (sk, tk)，各辺 e の長さ l(e)
Find: 合計長さ最小の walk P1,…, Pk (Pi : si → ti )
s.t. walk は互いにクロスしない
t1
s1
s2
OK
t2
例
s1
t2
s1
s2
s2
t1
NG
t1
t2
t2
s1
s2
NG
t1
Shortest non-crossing walks
Input: 頂点対 (s1, t1),…, (sk, tk)，各辺 e の長さ l(e)
Find: 合計長さ最小の walk P1,…, Pk (Pi : si → ti )
s.t. walk は互いにクロスしない
t1
s1
s2
OK
t2
例
s1
t2
s1
s2
s2
t1
NG
t1
t2
t2
s1
s2
NG
t1
定理 (Erickson-Nayyeri, 2009)
ターミナルが
h
個の面の周上にあるとき，
O(h2)
2
n log k の計算時間で解ける
例
s1
s2
t1
t2
obstacle
h=2
定理 (Erickson-Nayyeri, 2009)
obstacle
ターミナルが
h
個の面の周上にあるとき，
O(h2)
2
n log k の計算時間で解ける
関連研究
 h=1
のとき個別に最短路求めるだけ
 h=2
のとき O(n log k) 時間
(Takahashi-Suzuki-Nishizeki, 1992)
 h : 一般のとき NP-hard
例
s1
s2
t1
t2
(Bastert-Fekete, 1998)
obstacle
h=2
定理 (Erickson-Nayyeri, 2009)
obstacle
ターミナルが
h
個の面の周上にあるとき，
O(h2)
2
n log k の計算時間で解ける
細かい注意
ターミナルと Obstacle の間を
他のパスが通らないものとする
例
s1
s2
t1
t2
obstacle
h=2
定理 (Erickson-Nayyeri, 2009)
obstacle
ターミナルが
h
個の面の周上にあるとき，
O(h2)
2
n log k の計算時間で解ける
方針
いくつかの walk をとり，それらに沿って切り開く
S’T’-walks
どのペアも同じ面上
s2
s1
t1
t2
t3
s3
s2
s1
t1
t2
t3
s3
演習
obstacle
各 i に対して， si と ti が共通の面の周上のとき，
Shortest non-crossing walks が多項式時間で
解けることを示せ．
（計算時間はとりあえず気にしない）
どのようなパスで切り開くか？
最適解の部分解の候補
どのようなパスで切り開くか？
最適解の部分解の候補
同じ homotopy class の中で最短のもの
定義
2つの walk α, β が同じ homotopy class
∃連続写像 h: [0,1]×[0,1] → （平面 - obstacle）
s.t.
h(0, ･ ) = α, h(1, ･ ) = β
h(･ , 0) = α(0) = β(0), h(･ , 1) = α(1) = β(1)


α
β
α
同じ
β
obstacle
違う
最適解の性質
観察
Shortest non-crossing walks の最適解において
各 walk は，同じ homotopy class の中で最短
略証 α が同じ homotopy class の中で最短だとすると，
合計長さが短くできるので．
s3
s2
P2
s1 α
P1
P3
t3
s3
t2
s2
t1
s1 α
P2
P3
t3
t2
t1
最適解の性質
観察
Shortest non-crossing walks の最適解において
各 walk は，同じ homotopy class の中で最短
略証 α が同じ homotopy class の中で最短だとすると，
同じ
homotopy class の中で最短のパスが
合計長さが短くできるので．
s最適解に使われるパスの候補
s3
3
t
s2
P2
s1 α
P1
P3
3
P2
t2
s2
t1
s1 α
P3
t3
t2
t1
アルゴリズム
STEP 1
すべての homotopy class の組合せに対し，
最短の S’T’-walks Ω’ を計算
STEP ２
Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ
STEP ３
得られた ST-walks の中で最短のものを出力
アルゴリズム
（1）個数を 2
O(h2)
で抑える
STEP 1
すべての homotopy class の組合せに対し，
最短の S’T’-walks Ω’ を計算
STEP ２
（2）どう計算するか？
Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ
STEP ３
得られた ST-walks の中で最短のものを出力
補題
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
各 ωi は σ と高々 22h-2 回しかクロスしない
補題
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
各 ωi は σ と高々 22h-2 回しかクロスしない
s2
この補題を認めると．．．
最短パス σ1, … , σh-1 を用いて
h 個の obstacle faces を繋ぐ
σ1
s1
t3
t2
t1
s3
σ2
補題
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
各 ωi は σ と高々 22h-2 回しかクロスしない
s2
この補題を認めると．．．
最短パス σ1, … , σh-1 を用いて
h 個の obstacle faces を繋ぐ
σi を用いて切り開き，σi , si, ti の
接続関係を表すグラフ Π を作成
Π は高々 2
O(h2)
通り
t3
s1
σ1
σ2
t2
t1
s3
σ1
s2
t3
σ2
s1
t2
t1
σ1
σ2
s3
Π
補題
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
各 ωi は σ と高々 22h-2 回しかクロスしない
s2
この補題を認めると．．．
t3
s1
最短パス σ1, … , σh-1 を用いて 2O(h)
t2
σ1 × (2t O(h)) O(h)
1
h 個の obstacle faces を繋ぐ
弦の引き方並行枝の本数
σi を用いて切り開き，σi , si, ti の
接続関係を表すグラフ Π を作成
Π は高々 2
O(h2)
通り
s3
σ1
s2
σ2
t3
σ2
s1
t2
t1
σ1
σ2
s3
Π
演習

頂点数 n のサイクルが与えられたときに，
互いに交わらない弦の引き方が 2O(n) 通り
であることを示せ．
walks の復元
Π から walk を復元したい
s2
t3
s1
homotopy class は決まるので σ1
各 walk 毎に最短のものを探す
σ2
t2
t1
s3
σ1
s2
t3
σ2
s1
t2
t1
σ1
σ2
s3
Π
walks の復元
Π から walk を復元したい
s2
s1
homotopy class は決まるので σ1
各 walk 毎に最短のものを探す
計算時間： 2O(h) n
σ2
t2
t1
s3
例えば，s3→σ1→σ2→t3 なら，
グラフ 3 つを貼りあわせて最短路
t3
σ1
s2
t3
σ2
s1
t2
t1
σ1
σ2
s3
Π
アルゴリズム（再掲）
（1）個数を 2
O(h2)
で抑える
STEP 1
すべての homotopy class の組合せに対し，
最短の S’T’-walks Ω’ を計算
STEP ２
（2）どう計算するか？
Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ
STEP ３
得られた ST-walks の中で最短のものを出力
補題
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
各 ωi は σ と高々 22h-2 回しかクロスしない
あとは補題を示せばよい．
簡単のため，「2k 回しかクロスしない」を示す
準備
X(σ, Ω) : σ が交差する walk を順に並べた index 列
X(σ, Ω) の部分列が even
どの index も偶数回現れる
主張１
X(σ, Ω) は非空で even な部分列を持たない
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
X(σ, Ω) : σ が交差する walk を順に並べた index 列
主張１
X(σ, Ω) は非空で even な部分列を持たない
証明
σ
even な部分列を持つと，walks を繋ぎ直して
より短い ST-walks が得られるので矛盾．
1 1 3 1 8 3 5 3
2 2 4 2 7 4 6 4
同じ色を繋ぎかえる
1 → 4
5 → 8
9 → 12
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
X(σ, Ω) : σ が交差する walk を順に並べた index 列
主張１
X(σ, Ω) は非空で even な部分列を持たない
証明
σ
even な部分列を持つと，walks を繋ぎ直して
より短い ST-walks が得られるので矛盾．
1 1 3 1 8 3 5 3
2 2 4 2 7 4 6 4
σ
1 1 3 1 8 3 5 3
2 2 4 2 7 4 6 4
同じ色を繋ぎかえる
1 → 4
5 → 8
9 → 12
演習
この繋ぎかえで，クロスが
生じないことを示せ
主張２
長さ 2k 以上の X(σ, Ω) は，非空で even な部分列を持つ
演習
主張２を証明せよ
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
X(σ, Ω) : σ が交差する walk を順に並べた index 列
X(σ, Ω) の部分列が even
どの index も偶数回現れる
補題
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
各 ωi は σ と高々 22h-2 回しかクロスしない
簡単のため，「2k 回しかクロスしない」を示す
主張１
X(σ, Ω) は非空で even な部分列を持たない
主張２
長さ 2k 以上の X(σ, Ω) は，非空で even な部分列を持つ
主張１，主張２より，示された．
アルゴリズム（再掲）
（1）個数を 2
O(h2)
で抑える
STEP 1
すべての homotopy class の組合せに対し，
最短の S’T’-walks Ω’ を計算
STEP ２
（2）どう計算するか？
Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ
STEP ３
得られた ST-walks の中で最短のものを出力
定理 (Erickson-Nayyeri, 2009)
アルゴリズム（再掲）
ターミナルが h 個の面の周上にあるとき，
2
O(h2)
STEP 1
O(h2)
（1）個数を 2
n log k の計算時間で解ける
で抑える
すべての homotopy class の組合せに対し，
最短の S’T’-walks Ω’ を計算
STEP ２
（2）どう計算するか？
Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ
STEP ３
得られた ST-walks の中で最短のものを出力
まとめ：最短点素パス問題
自然な最適化問題
 ほとんどの場合で計算複雑度が未解決


現状
 カット条件
 幾何的な条件
のどちらかが扱いやすい場合のみ

Download Report