拡張ダイクストラ法

77

78

図4-1(b) 拡張ダイクストラ法の探索過程(N=3；ノード2)

図4-1(c) 拡張ダイクストラ法の探索過程(N=3；ノードt)

図 4-1(a)はノード 1 のラベル集合の計算過程を示している．始点ノードsから

ノード1への途中経路は e_{1 を通る経路と} e₂,e₅ を通る経路がある．2つの経 路から計算されるノード1のラベルはそれぞれ (1,10,10,20),(1,30,35,40)となる．

生成されたラベルを比較すると，_(1,10,10,20)は _(1,30,35,40) に対して優越してい る．よってノード 1 のラベル集合は L₁(1,10,10,20)となる．図 4-1(b)はノード 2 までのラベル集合，図4-1(c)は終点ノードtのラベル集合の計算過程を表している．

そ れ ぞ れ の ラ ベ ル 集 合 は ， L₂ {(2,20,20,30),(2,20,15,35)} , )}

40 , 25 , 25 , ( ), 30 , 30 , 20 ,

{(t t

L_t  と計算される．終点ノードにおいて，他のラベルに 優越されなかった(t,20,30,30),(t,25,25,40)がパレート最適解となる．

79

次に拡張ダイクストラ法の詳細な計算手順を下記に示す．

拡張ダイクストラ法の計算手順

STEP 1：(初期化)L_v{(s,0,0,,0)}，W_v ，_v_s STEP 2：ノード_vの隣接ノード集合W_vを求める．

STEP 3：(隣接ノードへの途中経路探索) STEP 3-1：隣接ノード(W_v)^{を選択する．}

STEP 3-2：_{(v,l1v,l2v,,lNv){(,l1,l2,,lN)|((,l1,l2,,lN)Lv)( v)}}を 選択する．

STEP 3-3：start(e_i)が_v，end(e_i)がのエッジ e_i について )

, , ,

,

( l_1v c_i1 l_2v c_i2  l_Nv c_iN を求め，

) ,

, ,

, ( ) , , , ,

( l₁^*_ l₂^*_  l^*_N   l_1vc_i1 l_2vc_i2  l_Nvc_iN とする．

STEP 3-4： の全てのラベルと (,l₁^*_,l₂^*_,,l_N^*_) を比較する．

) , , , ,

( l₁^*_ l^*_2  l_N^*_ がパレート最適解ならば L_v に記憶する．

STEP 3-5：STEP 3-2 で全ての (v,l_1v,l_2v,,l_Nv) を選択し終えていたら STEP

3-6 へ進む．それ以外は STEP 3-2 に戻る．

STEP 3-6：STEP 3-1 でW_vの全ての隣接ノードを選択し終えていれば STEP 4

へ進む．それ以外は STEP 3-1 へ戻る．

STEP 4：(既知の途中経路から隣接ノードへの途中経路探索とラベル計算) STEP 4-1： (W_v)^{を選択する．}

STEP 4-2：ノードに連結するノード に対し，(,l_1,l_2,,l_N)L_v を選択 する．

STEP 4-3： start(e_i)が，end(e_i)がのエッジ e_i について )

, , ,

,

( l_1 c_i1 l_2 c_i2 l_N c_iN を求め，

) ,

, ,

, ( ) , , , ,

( l₁^*_ l₂^*_  l^*_N   l_1 c_i1 l_2 c_i2  l_N c_iN とする．

STEP 4-4：L_vの全てのラベルと (,l₁^*_,l₂^*_,,l^*_N) を比較する．

) , , , ,

( l₁^*_ l^*_2  l_N^*_ がパレート最適解ならばL_vに記憶する．

STEP 4-5：STEP 4-2ですべての (,l_1,l_2,,l_N) を選択し終えていれば STEP

4-6 へ進む．それ以外は STEP 4-2 に戻る．

STEP 4-6：STEP 4-1で W_v の全てのノードが選択されていれば STEP 5 へ進 む．それ以外は STEP 4-1 へ戻る．

STEP 5：(ノードの移動・パレート最適解の出力)

STEP 5-1：vtかつ STEP 2 ですべてのノード _v(V) を選択し終えていれば，

Lv

80

STEP 5-2 に進む．それ以外は v(W_v) を選択し vv として STEP 2 へ戻る．

STEP 5-2：すべてのパレート最適解

)}

( ) ) , , , ((

| ) , , , ,

{( l_1 l_2  l_N  l_1 l_2 l_N L_v   t を出力して計算を終了 する．

次に STEP 3-4 と STEP 4-4 で行うパレート最適解判定について下記に詳細を 示す．

パレート最適解の判定

STEP 1：L_vと (,l₁^_,l₂^_,,l^*_N) を受け取る．

STEP 2：(,l₁_,l₂_,,l_N_){(,l_1,l_2,,l_N)|((,l_1,l_2,,l_N)L_v)( )}を選 択する．

STEP 3：j1,2,,N の全てに対して l^_j l_j が成立しているならば STEP 5 へ進む．それ以外は，L_v L_v_{(_,l₁^_,l₂^_,_,l^_N)}とし STEP 4 へ進む．

STEP 4：j1,2,,N の全てに対して l^_j l_j が成立しているラベル をL_v L_v\{(,l₁_,l₂_,,l_N_)}とする．

STEP 5：STEP 2ですべての (,l₁_,l₂_,,l_N_) が選択されていれば L_v を返す．

それ以外はSTEP 2へ戻る．

N

j1,2,, に対して，目的関数値g_j(x)に対応した座標軸g_jが張るN 次元空 間を考えると，拡張ダイクストラ法の探索過程は，原点を始点としてg_jが増加す る方向へ伸びていく線分として表現できる．図4-2(a)はN 2，図4-2(b)はN 3 の場合を示した．図中の点は，始点ノード_sから終点ノードtまでの経路で通過 する途中ノードを示している．そして最終的に，始点ノードsから終点ノードtま での経路 x はN 次元空間上の 1 点 (座標は (g₁(x),g₂(x),,g_N(x))) として表 されることになる．

81

図4-2(a) 拡張ダイクストラ法の経路探索イメージ (N=2)

図4-2(b) 拡張ダイクストラ法の経路探索イメージ (N=3)

82

次に，図 4-3(a)に示したネットワークを対象に，探索空間上で拡張ダイクスト

ラ法によりパレート最適解を判定する過程を，下記の図 4-3(b)と図4-3(c)の 2 次 元空間上で説明する．探索空間上で拡張ダイクストラ法の計算過程を詳細に図示 すると，空間における1点はノード上にある1つのコストラベルを表す．ラベル は該当ノードに到達するまでの総コストであり，1つのノード上には該当ノード に到達するまでの経路の数のラベルが存在する．図 4-3(b)に示したように，v₁に 到達する経路が2通りあれば，探索空間上にもv₁までの総コストとして2点が図 示される．拡張ダイクストラ法では，同一ノード上のラベル間でパレート最適解 の判定を行っている．図4-3(b)のv₁のラベルを示す2つの点は，どちらも互いに 被支配領域に存在していないので，2 点からv₁に隣接する別のノードへの経路探 索を進める．

図 4-3(c)は，v₂におけるラベルの判定を図示したものである．v₂のラベルにつ

いては，v₁を経由した経路の点は，_sから直接v₂へ到達した経路の点と比べ各目 的関数値が高い領域に存在している．そのため，図 4-3(c)に示したようにv₁を経 由した経路の点から他ノードへの経路探索は制限される．

以上のように，拡張ダイクストラ法の計算過程は，終点ノード_tまでの途中に 存在するノードへの経路も含め，すべて空間上で考えることが出来る．以後空間 上において，パレート最適解の判定により途中で探索が停止し，拡張ダイクスト ラ法において生成されないラベルは図示しないものとする．

図4-3(a) ネットワーク上での最適解判定過程

83

図4-3(b) 拡張ダイクストラ法の最適解判定イメージ (1)

図4-3(c) 拡張ダイクストラ法の最適解判定イメージ (2)

84