時間制約付き最短路 - Sophia University Private Home

制約付き最短路問題に対する
実験的解析
(7,15) 1
4
(1,6)
(8,21)
(4,4) (10,13)
(13,10)
(5,2)
(2,6)
(12,19)
(15,16)
(17,15)
(17,19)
(19,11) d
(4,4)
(7, 15)
(1,6)
o (9,4)
(9,7) 2 (4,4) (13,11)
(11,19) 5
(0,
(0,0)
0)
(5,2)
(16,8)
(12,4)
(1,6)
(4,4) (14,9) (5,2)
(12,4) 3
(5,2) (12,17) 6
(17,6)
上智大学
宮本裕一郎
制約付き最短路問題のイメージ
制約付き最短路問題のイメージ
各地点間の移動時間・移動費用
がわかっている．
出発地から目的地までの経路のうち
移動時間最小の経路を見つけよ．
ただし，定められた予算上限を超えてはいけない．
予算上限が
2万円ならば
（3時間，5千円）
（3時間，3千円）
青森
函館
盛岡
（5時間，1万2千円）
東京
2002年9月19日
（3時間，2万5千円）
アルゴリズム研究会
2
数理計画問題（整数線形計画問題）としての定式化
minimize
t x
eE
e e
v  o,
1

subject to
x

x

v  d,
v V ,
 1


e
e
eE|start ( e ) v eE|end ( e ) v 
 0 otherwise,
c x
eE
e e
U,
xe  0,1, e  E.
G=(V,E)：有向グラフ
線形緩和解が整数解になるとは限らない
(te,ce)：枝eの（移動時間，移動費用）
start(e)：枝eの始点
サブセットサムを帰着可能→（弱）NP-困難
U：費用上限
end(e)：枝eの終点
非負整数
o：出発地点ナップサック問題に類似
d：目的地点
2002年9月19日
アルゴリズム研究会
3
問題の背景
参考文献にはいろいろ応用があると書いてありますが・・・
システムの費用が枝ごとの費用の和になっている
ネットワーク設計問題
大規模な問題を解くためにメタ解法を開発
解近傍を計算する際に
サブルーチンとして最短路問題
ネットワーク設計問題に制約がある場合には
サブルーチンとして制約付き最短路問題
2002年9月19日
アルゴリズム研究会
4
既存の研究
問題の種類
•上限制約だけのもの
•下限制約があるもの
•制約が複数あるもの
•・・・
解法
•厳密アルゴリズム
擬多項式（Dijkstraベース，Bellman-Fordベース）
指数（分枝限定法，第k最短路への帰着）
本研究の位置づけ
•多項式時間近似アルゴリズム
既存の擬多項式時間厳密アルゴリズムを改良
（目的関数に依存，解の数を多項式個に限定）
計算量を若干軽減，O(n2C(log n + C))
log C))
•発見的アルゴリズム
実際の計算時間は？
（Lagrange緩和ベース，最も多い） n：点数
C：入力定数
2002年9月19日
アルゴリズム研究会
5
Dijkstra法の簡単な説明
枝(v,w)があるとき，
wへの最短路長≦vへの最短路長＋枝長
という再帰方程式をもとに，出発点から近い順に最短路を確定
Dijkstra法
ステップ1：∀v∈V＼o, Lv=∞
Lo=0
S=V
ステップ2： S=空ならばアルゴリズム終了
そうでないならばLv=min{Lv:v∈S}を満たすvを探す
ステップ3： ∀(v,w) ∈E, Lw=min{Lw, Lv+枝長},
S=S＼v, ステップ2に行く．
2002年9月19日
アルゴリズム研究会
6
Dijkstra法の簡単な例
∞
7
∞
8
1
1
4
2
4
5
0
o
7
∞
9
2
9
12
2002年9月19日
d
12
∞
4
3
4
5
4
5
1
12
∞
10
∞
11
∞
1
5
5
アルゴリズム研究会
6
7
Dijkstra法の拡張
各点に
（時間）距離を表す
スカラー値のラベルを保持
各点に
（時間，費用）を表す
ベクトル値のラベルを保持
各点に
ラベルを複数保持
パレート解だけ保持
各点に
ラベルを1つ保持
出発地点から（時間距離で）
近いラベルから確定
2002年9月19日
アルゴリズム研究会
そのまま
8
提案するアルゴリズムの簡単な例
(時間，費用)
(∞, ∞)
(7,15)
(∞, ∞)
(1,6)
1
(9,4)(9,7)
(0,
(0,0)
0)
(12,4)
(2,6)
(13,10)
(12,19)
(15,16)
(17,15)
(∞, ∞)
(∞, ∞)
(1,6)
2
4
(10,13)
(8,21)
(4,4)
(5,2)
(7, 15)
(∞, ∞)
o
費用上限=18
(4,4)
(5,2)
(11,19)
(13,11)
(19,11) d
(4,4) (17,19)
5
(16,8)
(1,6)
(∞, ∞)
(12,4)
(4,4)
3
(5,2)
(∞,
(14,9)
∞)
(12,17)
(5,2)
6
(17,6)
2002年9月19日
アルゴリズム研究会
9
アルゴリズムの概要
拡張Dijkstra法
ステップ1：∀v∈V＼o, Lv={(∞, ∞)}
Lo={(0,0)}
S=空
ステップ2： {Ｕv∈V Lv}＼S=空ならばアルゴリズム終了（解なし）
そうでないならば
t*=min{t:(t,c)∈{Ｕv∈VLv}＼S}を満たす(t*,c)を探す
(t*,c) ∈Ldならば終了．(t*,c)が最適解
そうでないならばステップ3へ
ステップ3： (t*,c) ∈Lvとする。
∀(v,w) ∈E,
Lw=LwＵ{(t + te,c + ce)},
Lwから実行不可能なもの，パレート解でないものを省く
S=SＵ(t,c), ステップ2に行く．
2002年9月19日
アルゴリズム研究会
10
アルゴリズムの正当性
•確定していないラベルのうち
時間が最小のものを選んで確定
•後続する点のラベル集合を更新
•ラベルは1つずつ確定
•各点で確定されるラベルの
総数の上界はパレート解の数
枝重みが整数
↓
擬多項式個
2002年9月19日
•確定したラベルよりも時間が
大きいラベルのみ出現
•いつかは最適解のラベルが出現
•巡回なし
擬多項式回の確定で終了
アルゴリズム研究会
11
既存のアルゴリズムとの違い
(19,11)
(14,9)
先ほどの確定操作
(17,6)
6
(15,16)
(17,15)
(5,2)
d
(19,11)
(22,8)
(14,9)
既存の確定操作
(17,6)
6
2002年9月19日
(15,16)
(17,15)
(5,2)
アルゴリズム研究会
d
12
計算量の算定
P:パレート解の数の上限
→各点のラベル数の上限=P
→全体で確定されるラベル数の上限=nP
→各点でのラベル集合の更新回数=nPn
ラベルをまとめて更新（既存）
ラベル集合を時間の
昇順のリストで保存
→O(P)
→O(P2)【制約がk本の場合】
kは定数と見なしている
2002年9月19日
ラベルを１つ更新（新規）
ラベル集合を時間の
昇順のリストで保存
→O(P)
→O(P) 【制約がk本の場合】
ラベル集合を平衡木で保存
→O(log P)
→無理？【制約がk本の場合】
アルゴリズム研究会
13
総計算量の算定
どのラベルを
確定するか
探索にヒープ
を使っている
ため
総計算量（旧）→O(n2P(log n + P))
総計算量（新）→O(n2P(log n + log P))
P≦max{U, (n-1)×枝移動時間最大値}≡C
総計算量（旧）→O(n2C(log n + C))
総計算量（新）→O(n2C(log n + log C))
Bellman-Ford法ベース
O(nmC)
制約がk本の場合
C≡min{U1, U2,…, Uk,(n-1)×枝移動時間最大値}
総計算量（旧）→O(n2 Ck-1(log n + C2k-2))
総計算量（新）→O(n2 Ck-1(log n + Ck-1))
（kは定数と見なしている）
2002年9月19日
アルゴリズム研究会
P≦Ck-1
Bellman-Ford法ベース
O(nmC2k-2)
14
2-3木
例えば，平衡木の中でも2-3木を使用
(4,4)
子の数は2あるいは3個
葉にのみラベルを保持
(1,9)～(8,1)
根から葉への距離は一定
(1,9)～(3,7)
(1,9)
(3,7)
(5,6)～(8,1)
(5,6)
(6,5)
(8,1)
新要素がパレート解か？→O(log P)
内点に子孫の区間を保持
新要素の挿入→ O(log P)
パレート解でなくなるものの除去→O(P log P)→O(log P)
2002年9月19日
アルゴリズム研究会
15
予備（パレート解ラベル集合判定）実験
[1,n]2上の点を一様にn回発生，それをラベルとして更新
実験結果（10回試行した平均値）
n
10
100
1000
10000
100000
1000000
10000000
計算時間（秒）（対数）
1.5
1
0.5
0
-0.5
-1
-1.5
-2
-2.5
-3
-3.5
1
2
3
4
5
6
平衡木
2002年9月19日
7
平均計算時間（秒）
平均ラベル数
平衡木
リスト
0.002
0.001
0.21
0.004
0.003
0.365
0.008
0.006
0.422
0.022
0.021
0.864
0.146
0.135
1.385
1.246
1
1.193
13.579
12.614
1.457
系列1
平衡木
リスト
系列2
リスト
n（対数）
アルゴリズム研究会
16
予備（パレート解ラベル集合判定）実験（やりなおし）
[1,n]2の対角領域に点を一様にn回発生，それをラベルとして更新
10回試行した平均値
計算時間（秒）（対数）
1
0.5
n
10
100
1000
10000
100000
平均計算時間（秒）
平均ラベル数
平衡木
リスト
0.001
0.001
0.33
0.005
0.004
1.803
0.012
0.015
6.22
0.033
0.142
17.144
0.245
4.206
60.289
0
-0.5
1
2
-1
-1.5
-2
3
リスト
4
5
系列1
系列2
平衡木
-2.5
-3
-3.5
2002年9月19日
アルゴリズム研究会
n（対数）
17
ベンチマーク問題を用いた計算実験
問題例点数枝数確定回数平均ラベル数計算時間（秒）
rcsp1
100 955
52
1.023
0.03
0.04
48
1.626
0.05
rcsp2
100 955
33
0.889
0.04
0.03
33
1.067
0.04
rcsp3
100 959
35
1.916
0.03
0.03
35
2.174
0.05
rcsp4
100 959
48
0.823
0.04
0.03
44
3.122
0.08
rcsp9
200 2040
29
0.098
0.03
0.05
27
0.049
0.02
rcsp10
200 2040
22
0.067
0.03
0.03
21
0.033
0.02
rcsp11
200 1971
44
1.3
0.11
0.03
108
5.885
0.1
rscp12
200 1971
44
1.276
0.07
0.04
109
5.192
0.1
2002年9月19日
計算方式
新（リスト）
新（平衡木）
旧
新（リスト）
新（平衡木）
旧
新（リスト）
新（平衡木）
旧
新（リスト）
新（平衡木）
旧
新（リスト）
新（平衡木）
旧
新（リスト）
新（平衡木）
旧
新（リスト）
新（平衡木）
旧
新（リスト）
新（平衡木）
旧
アルゴリズム研究会
Beasley
And
Christofides
[1989]より
18
ベンチマーク問題を用いた計算実験
問題例点数枝数確定回数平均ラベル数計算時間（秒）計算方式
rcsp17
500 4858
376
2
0.09 新（リスト）
0.1 新（平衡木）
292
6.546
0.17 旧
rcsp18
500 4858
363
1.897
0.11 新（リスト）
0.1 新（平衡木）
283
6.245
0.16 旧
rcsp19
500 4978
111
0.675
0.07 新（リスト）
0.06 新（平衡木）
136
3.315
0.1 旧
rcsp20
500 4978
99
0.841
0.06 新（リスト）
0.08 新（平衡木）
148
3.549
0.12 旧
問題が小さすぎて参考にならない
2002年9月19日
アルゴリズム研究会
19
計算実験（問題例の説明）
一辺の点数n（例の場合3）
と
枝の移動時間・移動費用の最大値MAX
を設定
出発
一様乱数[0,MAX]
地点
により設定
1
2
3
始点は1，終点はn2
4
7
2002年9月19日
5
8
6
9
費用上限はn・MAX
目的
地点
アルゴリズム研究会
20
計算実験結果
点数100(=10×10)，枝数約400，10回試行
最大重み平均確定回数平均ラベル数計算時間（秒）計算方式
10
340
1.47
0.01 新（リスト）
0.02 新（平衡木）
375
22.48
0.2 旧
100
413
1.98
0.01 新（リスト）
0.02 新（平衡木）
494
59.29
1.13 旧
1000
462
1.97
0.01 新（リスト）
0.03 新（平衡木）
592
65.51
1.49 旧
旧方式はラベルが多い，確定回数が少ないとは限らない
新方式はリストの方が速い
2002年9月19日
アルゴリズム研究会
21
計算実験結果
平均出次数約4，10回試行
点数最大重み平均確定回数平均ラベル数
900
10
16929
2.57
100
25910
4.39
1000
25371
4.08
2500
10
93473
3.05
100
149844
5.45
1000
163795
6.18
4900
10
298119
3.38
100
506732
6.98
1000
564165
8.42
計算時間（秒）
リスト平衡木
0.4
0.42
0.62
0.74
0.58
0.68
2.67
2.9
4.13
5.13
4.52
5.42
9.08 10.49
15.81 20.06
20.27 28.57
平衡木を使った方が遅い，平均ラベル数が少なすぎ
勝つまでやっても意味はないのでこのへんで
2002年9月19日
アルゴリズム研究会
22
まとめ
Dijkstra法ベースのアルゴリズムを改良
計算実験の結果、平衡木を使う方法は
それほど速くなかった。
2002年9月19日
アルゴリズム研究会
23
参考文献
Ahuja, Magnanti and Orlin, Lagrangian relaxation and network
optimization, Network flows:Section16, Plentis holl, 1993.
主にLagrangu緩和に関する話題と，応用が載っている．
Beasley and Christofides, An algorithm for the resource constrained
shortest path problem, Networks, Vol. 19 (1989), pp. 379—394.
ここではLagrangu緩和を下界とした分枝限定法を提案している．
ベンチマーク問題も提供されている．
Puri and Tripakis, Algorithms for the multi-constrained routing
problem, Proceedings of SWAT2002, pp.338—347.
Bellman-Ford法に基づく多項式時間近似スキームを提案している．
擬多項式時間アルゴリズムも提案している．
計算実験結果も報告している．
2002年9月19日
アルゴリズム研究会
24

Download Report