制約付き最短路問題に対する実験的解析 上智大学 宮本裕一郎 o 1 d (7, 15) (9,4) (12,4)

Presentation on theme: "制約付き最短路問題に対する実験的解析 上智大学 宮本裕一郎 o 1 d (7, 15) (9,4) (12,4)"— Presentation transcript:

1 制約付き最短路問題に対する実験的解析 上智大学 宮本裕一郎 o 1 d 2 3 4 5 6 (7, 15) (9,4) (12,4)
(1,6) (4,4) (5,2) (2,6) (0, 0) (7,15) (9,7) (0,0) (8,21) (11,19) (12,17) (10,13) (13,11) (14,9) (12,19) (13,10) (16,8) (17,6) (17,19) (15,16) (17,15) (19,11) 上智大学 宮本裕一郎

2 ただし，定められた予算上限を超えてはいけない．
制約付き最短路問題のイメージ 制約付き 最短路問題のイメージ 各地点間の移動時間 がわかっている． 出発地から目的地までの経路のうち 移動時間最小の経路を見つけよ． ・移動費用 ただし，定められた予算上限を超えてはいけない． 東京 函館 盛岡 青森 （3時間，2万5千円） （3時間，5千円） （3時間，3千円） （5時間，1万2千円） 予算上限が 2万円ならば 制約付き最短路 最短路 2002年9月19日 アルゴリズム研究会

3 数理計画問題（整数線形計画問題）としての定式化
G=(V,E)：有向グラフ (te,ce)：枝eの（移動時間，移動費用） U：費用上限 o：出発地点 d：目的地点 線形緩和解が整数解になるとは限らない サブセットサムを帰着可能→（弱）NP-困難 ナップサック問題に類似 start(e)：枝eの始点 end(e)：枝eの終点 非負整数 2002年9月19日 アルゴリズム研究会

4 ネットワーク設計問題に制約がある場合には
問題の背景 参考文献にはいろいろ応用があると書いてありますが・・・ システムの費用が枝ごとの費用の和になっている ネットワーク設計問題 大規模な問題を解くためにメタ解法を開発 解近傍を計算する際に サブルーチンとして最短路問題 ネットワーク設計問題に制約がある場合には サブルーチンとして制約付き最短路問題 2002年9月19日 アルゴリズム研究会

5 厳密アルゴリズム 擬多項式（Dijkstraベース，Bellman-Fordベース） 指数（分枝限定法，第k最短路への帰着）
既存の研究 問題の種類 上限制約だけのもの 下限制約があるもの 制約が複数あるもの ・・・ 解法 厳密アルゴリズム 擬多項式（Dijkstraベース，Bellman-Fordベース） 指数（分枝限定法，第k最短路への帰着） 多項式時間近似アルゴリズム （目的関数に依存，解の数を多項式個に限定） 発見的アルゴリズム （Lagrange緩和ベース，最も多い） 本研究の位置づけ 既存の擬多項式時間厳密アルゴリズムを改良 計算量を若干軽減，O(n2C(log n + C)) 実際の計算時間は？ log C)) n：点数 C：入力定数 2002年9月19日 アルゴリズム研究会

6 という再帰方程式をもとに，出発点から近い順に最短路を確定
Dijkstra法の簡単な説明 枝(v,w)があるとき， wへの最短路長≦vへの最短路長＋枝長 という再帰方程式をもとに，出発点から近い順に最短路を確定 Dijkstra法 ステップ1：∀v∈V＼o, Lv=∞ Lo= 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日 アルゴリズム研究会

7 Dijkstra法の簡単な例 ∞ 7 9 12 7 7 8 11 12 8 8 o 1 d 2 3 4 5 6 7 9 12 10 10 9 9 2002年9月19日 アルゴリズム研究会

8 Dijkstra法の拡張 各点に （時間）距離を表す スカラー値のラベルを保持 各点に （時間，費用）を表す ベクトル値のラベルを保持
ラベルを複数保持 パレート解だけ保持 各点に ラベルを1つ保持 出発地点から（時間距離で） 近いラベルから確定 そのまま 2002年9月19日 アルゴリズム研究会

9 提案するアルゴリズムの簡単な例 (時間，費用) 費用上限=18 (∞, ∞) (0, 0) o 1 d 2 3 4 5 6 (7, 15)
(9,4) (12,4) (1,6) (4,4) (5,2) (2,6) (7,15) (7,15) (7,15) (8,21) (10,13) (10,13) (10,13) (13,10) (13,10) (13,10) (15,16) (15,16) (12,19) (17,15) (19,11) (17,19) (9,7) (9,7) (9,7) (13,11) (11,19) (13,11) (13,11) (0, 0) (0,0) (16,8) (14,9) (14,9) (14,9) (12,17) (12,17) (12,17) (12,4) (12,4) (12,4) (17,6) 2002年9月19日 アルゴリズム研究会

10 ステップ1：∀v∈V＼o, Lv={(∞, ∞)} Lo={(0,0)} S=空
アルゴリズムの概要 拡張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日 アルゴリズム研究会

11 確定していないラベルのうち 時間が最小のものを選んで確定 後続する点のラベル集合を更新
アルゴリズムの正当性 確定していないラベルのうち 時間が最小のものを選んで確定 後続する点のラベル集合を更新 確定したラベルよりも時間が 大きいラベルのみ出現 いつかは最適解のラベルが出現 巡回なし ラベルは1つずつ確定 各点で確定されるラベルの 総数の上界はパレート解の数 枝重みが整数 ↓ 擬多項式個 擬多項式回の確定で終了 2002年9月19日 アルゴリズム研究会

12 既存のアルゴリズムとの違い (19,11) (14,9) (14,9) (14,9) 先ほどの確定操作 (15,16) (17,6)
(17,15) 6 d (5,2) (19,11) (22,8) 既存の確定操作 (14,9) (17,6) (14,9) (14,9) (17,6) (15,16) (17,6) (17,15) 6 d (5,2) 2002年9月19日 アルゴリズム研究会

13 計算量の算定 P:パレート解の数の上限 →各点のラベル数の上限=P →全体で確定されるラベル数の上限=nP
→各点でのラベル集合の更新回数=nPn ラベルをまとめて更新（既存） ラベル集合を時間の 昇順のリストで保存 →O(P) →O(P2)【制約がk本の場合】 ラベルを１つ更新（新規） ラベル集合を時間の 昇順のリストで保存 →O(P) →O(P) 【制約がk本の場合】 ラベル集合を平衡木で保存 →O(log P) →無理？ 【制約がk本の場合】 kは定数と見なしている 2002年9月19日 アルゴリズム研究会

14 総計算量（旧）→O(n2P(log n + P)) 総計算量（新）→O(n2P(log n + log P))
総計算量の算定 どのラベルを 確定するか 探索にヒープを使っているため 総計算量（旧）→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)×枝移動時間最大値} P≦Ck-1 総計算量（旧）→O(n2 Ck-1(log n + C2k-2)) 総計算量（新）→O(n2 Ck-1(log n + Ck-1)) （kは定数と見なしている） Bellman-Ford法ベース O(nmC2k-2) 2002年9月19日 アルゴリズム研究会

15 パレート解でなくなるものの除去→O(P log P)→O(log P) 内点に子孫の区間を保持
2-3木 例えば，平衡木の中でも2-3木を使用 子の数は2あるいは3個 葉にのみラベルを保持 (1,9)～(8,1) (4,4) 根から葉への距離は一定 (1,9)～(3,7) (5,6)～(8,1) (1,9) (3,7) (5,6) (6,5) (8,1) 新要素がパレート解か？→O(log P) 新要素の挿入→ O(log P) パレート解でなくなるものの除去→O(P log P)→O(log P) 内点に子孫の区間を保持 2002年9月19日 アルゴリズム研究会

16 [1,n]2上の点を一様にn回発生，それをラベルとして更新
予備（パレート解ラベル集合判定）実験 [1,n]2上の点を一様にn回発生，それをラベルとして更新 実験結果（10回試行した平均値） 計算時間（秒）（対数） 平衡木 リスト 平衡木 リスト n（対数） 2002年9月19日 アルゴリズム研究会

17 予備（パレート解ラベル集合判定）実験（やりなおし）
[1,n]2の対角領域に点を一様にn回発生，それをラベルとして更新 計算時間（秒）（対数） 10回試行した平均値 リスト 平衡木 n（対数） 2002年9月19日 アルゴリズム研究会

18 ベンチマーク問題を用いた計算実験 Beasley And Christofides [1989]より 2002年9月19日
アルゴリズム研究会

19 ベンチマーク問題を用いた計算実験 問題が小さすぎて参考にならない 2002年9月19日 アルゴリズム研究会

20 計算実験（問題例の説明） 一辺の点数n（例の場合3） と 枝の移動時間・移動費用の最大値MAX を設定 出発 地点 一様乱数[0,MAX]
により設定 1 2 3 始点は1，終点はn2 6 4 5 費用上限はn・MAX 目的 地点 9 8 7 2002年9月19日 アルゴリズム研究会

21 旧方式はラベルが多い，確定回数が少ないとは限らない 新方式はリストの方が速い
計算実験結果 点数100(=10×10)，枝数約400，10回試行 旧方式はラベルが多い，確定回数が少ないとは限らない 新方式はリストの方が速い 2002年9月19日 アルゴリズム研究会

22 勝つまでやっても意味はないのでこのへんで
計算実験結果 平均出次数約4，10回試行 平衡木を使った方が遅い，平均ラベル数が少なすぎ 勝つまでやっても意味はないのでこのへんで 2002年9月19日 アルゴリズム研究会

23 Dijkstra法ベースのアルゴリズムを改良 計算実験の結果、平衡木を使う方法は それほど速くなかった。
まとめ Dijkstra法ベースのアルゴリズムを改良 計算実験の結果、平衡木を使う方法は それほど速くなかった。 2002年9月19日 アルゴリズム研究会

24 Ahuja, Magnanti and Orlin, Lagrangian relaxation and network
参考文献 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日 アルゴリズム研究会