最短経路問題とは

(1)

プログラミング言語 I 第 10 回最短経路問題

埼玉大学工学部電気電子システム工学科伊藤和人

最短経路問題とは

始点から終点へ行く経路が複数通りある場合に、最も短い経路を見つける問題経路の短さの決め方によって様々な応用

最短経路問題の応用例

カーナビゲーション

現在地から目的地まで最短時間のルート

経路=道路

交差点において走る道路を変更してもよい

経路の短さ=所要時間の短さ

鉄道乗り換え案内

始発駅から目的駅まで料金最低のルート

経路=路線

駅において路線を乗り換えてもよい

経路の短さ=料金の安さ

問題の定式化

定式化: 問題の意味が変化しないことに注意して、明確な形式に問題を整理すること

条件と解の性質を明確にする

あいまいな点をなくす

さらに、問題を解くプログラムが容易に作成できるような定式化を行うことが重要

グラフ

プログラミングに適した問題定式化の道具としてよく用いられる

1 個以上の点 ( ノード ) と 2 つの点を結ぶ枝からなる

点枝

グラフの例

グラフ ( その 2)

点を共有する枝の集合をパス(path、経路) という

パスの始点と終点を定める

一般に始点と終点が同じパスは複数通り存在する (1 通りしか存在しない場合や、

1つも存在しない場合あり)

始点

終点パス

(2)

グラフ ( その 3)

枝に重みを与える

パスの重みは、枝重みの和とする

始点

終点パス: 重み12 2

1 9

6 3 5

2 2

始点・終点が同じ複数通りのパスパスによって重みは異なる

枝重み

最短経路問題の定式化

グラフによって問題を入力

　　　　　　 ( 始点、終点、枝重み )

鉄道乗り換え案内の場合

乗換駅を点、枝重みを料金とすればよい

横浜

品川東京上野

赤羽大宮新宿池袋

渋谷

重み最小のパスを見つける

280円 260円

160円 150円150円 150円 160円 290円

160円 160円 150円

2,750円

最小値原理

始点sから終点tへの最短経路上の点をvとすると、パス p(s,v) とパス p(v,t) はともに最短経路である

始点 s 終点

sからtへの最短経路 sからvへの t

最短経路

vからtへの v 最短経路

終点以外の最短経路を順次求めて、

最終的に終点への最短経路を求める

問題の分類

枝重みが0または正の場合

枝重みが 0 、正、負で負ループがない場合

枝重みが0、正、負で負ループがある場合

ループ: 始点と終点が一致したパス

負ループ: 枝重み和が負のループ

負ループ: 重み-2 2

1 -8

1 3 5

2 0

枝重みが0、正、負で負ループがある場合

最短経路アルゴリズム 1

枝重みが 0 または正の場合を考える

始点sから点bへの最短経路が1であると決定できる

なぜか?

2 1

s 3 6

a

d b c 0

3 2 4

1 0 2

始点

始点sから他の点への最短経路を求める

2 1

s 3 6

a

d b c 0

3 2 4

1 0 2

始点

最短経路アルゴリズム 1( その 2)

枝重みが 0 または正の場合

2 1

s 3 6

a

d b c 0

3 2 4

1 0 2

枝重みが0または正であるので、

点a, c, dを経由するどのパスも重みが1以上となるため始点

2

3 6

cを経由パス重みは3以上 dを経由パス重みは6以上 aを経由パス重みは2以上 1

(3)

1

最短経路アルゴリズム 1( その 3)

次に経路が最短な点を求める

始点

2 1

s 3 6

a

d b

c f

0 e

3 2

4 1 0 2

2 4

3 5

6

1

2 1

s 3 6

a

d b

c f

e

3 2

4 1 0 2

2 0 4→2

3 5

6 1

2

2 1

s 3 6

a

d b

c f

e 3 2 4

1 0 2

0 2

3 5

6

1

2 2

2 1

s 3 6

a

d b

c f

e 3 2 4

1 0 2

0

5→4 3

最短経路アルゴリズム 1( その 4)

アルゴリズムのポイント

最短経路長の定まった点から、

さらに枝1本で到達する点のうち、

経路長最短の点は、最短経路と決定できる

1 2

s

7

3 4

2 2

4

3 5

4

6

6 7

最短経路長の決まっている点

さらに枝1本で到達する点

経路長が最小

⇒最短経路を決定できる点

ダイクストラ法

C言語によるグラフ表現1

2次元配列を用いる方法

枝が結ぶ 2 点 (i,j)

配列要素e[i][j]が枝を表す

i ⇒ j と j ⇒ i を区別しない場合 e[j][i] = e[i][j] とする

j i

e[i][j]=1: 枝あり e[i][j]=0: 枝なし

C言語によるグラフ表現1(続き)

枝(i,j)の重み・・ w[i][j]が記憶

i ⇒ j と j ⇒ i を区別しない場合 w[j][i] = w[i][j] とする

j i

w[i][j]

ダイクストラ法の実装

ints, minLen, j, m, u[N], f[N]={0};

for( j=0 ; j<N ; j++ ) u[j] = 9999;

s = 0; u[s] = 0;

for( m=1 ; m<N ; m++ ){

f[s] = 1;

for( j=0 ; j<N ; j++ ){

if( e[s][j] != 1 ) continue;

if( u[s]+w[s][j] < u[j] ) u[j]=u[s]+w[s][j];

}

minLen = 9999;

for( j=0 ; j<N ; j++ ){

if( f[j] == 1 ) continue;

if( u[j] < minLen ){ minLen = u[j]; s = j; } } }

十分大きな正数

枝(s,j)が存在しない

始点s=0とする

最短経路既定の点は除外点sは最短経路決定

点数N

点sは経路長が最短

点jへの経路長を更新

長さだけでなく経路を記録

ints, minLen, j, m, u[N], f[N]={0}, prev[N];

for( j=0 ; j<N ; j++ ) u[j] = 9999;

s = 0; u[s] = 0;

for( m=1 ; m<N ; m++ ){

f[s] = 1;

for( j=0 ; j<N ; j++ ){

if( e[s][j] != 1 ) continue;

if( u[s]+w[s][j] < u[j] ){

u[j]=u[s]+w[s][j]; prev[j]=s;} /* jの直前はs */

}minLen = 9999;

for( j=0 ; j<N ; j++ ){

if( f[j] == 1 ) continue;

枝(s,j)が存在しない

始点s=0とする

点sは最短経路決定点数N

点jへの経路長を更新最短経路既定の点は除外

(4)

ダイクストラ法の計算複雑度

経路長最短の点を 1 つ選び経路を決定

その点から 1 本の枝で接続する点について経路長を調べなおす

すべての点について経路が決定するまで繰り返す

) ( N

²

O

プログラムの実行時間

ノード数 N とプログラム実行時間の関係

0.01 0.10 1.00 10.00 100.00

100 1000 10000 100000

N

秒

PentiumIV 2.4GHz 512MBメモリ予想

N=8000 約500Mバイト N=7000 約400Mバイト

1つのノード当たり4本の枝の場合

プログラムの問題点

配列による枝表現はメモリを大量に必要とし、かつ効率が悪い

010000000000000000000000000000000000000000000000000000 101000000000000000000011000000000000000000000000000000 010110000000000000000000000000000000000000000000000000 001010000000000000000000000000000000000000000000000000 001101000000000000000000000000000000000000000000000000 000010110000000000000000000000000000000000000000000000 000001010000000000000000000000000000000000000001000000 000001100000000000000000000000000000000000000100000100 000000000110000000000000000000000000000000000000000100 000000001010000000000000000000000000000000000000000000 000000001101000000000000000000000000000000000000000010 000000000010100000000000000000000000000000000000100000 000000000001010000000000000000000000000000000000000000 000000000000101001000000000000000000000000000000000010 000000000000010100100000000000000000000000000000000000 000000000000001000000000000000000000000000000010100000 000000000000000001000000100000000000000000000101000000 000000000000010010100000000000000000000000000000000000 000000000000001001010000000010000000000000000000000000 000000000000000000101000000000000000000000000000000000 000000000000000000010100000000000000000000000000010000 000000000000000000001000000000001001000000000000000000 010000000000000000000001000000000000000000000000001000 010000000000000000000010100000000000000000000000000000

…

j

i

枝の有無を表す2次元配列e[i][j]

の例 0がほとんど

配列による枝表現の問題

枝の有無(e[i][j]==1か否か)を調べる処理が必要

枝が無くても(e[i][j]=0)を記憶する必要があるためメモリを大量に消費し、速度低下 ( スラッシング )

配列に代わる、不規則なデータを効率よく記録する方式が必要

リスト構造

リストの管理

リストの要素

データ領域の他に、次の要素を指すポインタを備える

ポインタを用いて要素をつなげる = リスト

データ領域ポインタ要素

次の要素を指す

リストの実装

構造体によって、データ領域と次要素へのポインタをまとめて管理する

例

要素の構造体型を宣言 typedef structEdge {

structEdge *next;

inti,j; // 点1, 点2 intw; // 枝重み } EDGE;

次要素へのポインタデータ領域

例

リストの先頭を指すポインタを宣言 EDGE *edge_top = NULL;

(5)

リストの実装 ( その 2)

リストの例

リストを順にたどる処理

edge_top

NULL 点2

枝重み

点2 枝重み

点2 枝重み点1 点1 点1

3本の枝を記録するリスト

リストの末尾では nextメンバは NULL

EDGE *ep;

for( ep=edge_top ; ep != NULL; ep=ep->next ){

…/* リスト要素に対する処理*/

}

ダイクストラ法における枝リスト

最短経路が決まるたびに、その点から枝 1 本でつながる点の経路長更新

1 2

s

7

3 4

2 2

4

3 5

4

6

6 最短経路長の

決まっている点

経路長を更新する点新たに最短経路長

の決まった点

各点に接続する枝リストがあると便利

7

ダイクストラ法のための枝リスト

各点に接続する枝のリスト

NULL 点2

枝重み

点2 枝重み

0 0 0

edge[0]

NULL 点2

枝重み

点2 枝重み

1 1 1

edge[1]

edge[2]

点2 枝重み

1

点ごとに接続する枝数は変化

点2 枝重み

2 点0に接続する枝のリスト

点1に接続する枝のリスト

ダイクストラ法と組合わせる場合、メンバ「点1」は不要

リストを用いたダイクストラ法

ints, minLen, j, m, u[N], f[N]={0};

EDGE edge[N], *ep; /* 枝リストを設定する処理は省略*/

for( j=0 ; j<N ; j++ ) u[j] = 9999;

s = 0; u[s] = 0;

for( m=1 ; m<N ; m++ ){

f[s] = 1;

for( ep=edge[s] ; ep!=NULL; ep=ep->next ){

if( u[s]+ep->w < u[ep->j] ){

u[ep->j]=u[s]+ ep->w;}

}minLen = 9999;

for( j=0 ; j<N ; j++ ){

if( f[j] ) continue;

始点s=0とする

最短経路既定の点は除外点sは最短経路決定

点数N

sに接続する枝を順に調べる点ep->jへの経路長を更新

プログラムの実行時間

ノード数 N とプログラム実行時間の関係

0.01 0.10 1.00 10.00 100.00

100 1000 10000 100000

N

秒

PentiumIV 2.4GHz 512MBメモリリスト構造

利用 N=8000 配列利用

約500Mバイト N=7000 約400Mバイト

N=40000 約1Mバイト

最短経路アルゴリズム 2

負の枝重みが存在する場合

2 1

s 3 6

a

d b c 0

3 -1 -4

1 0 -2 始点

ダイクストラ法では最短経路を見つけられないなぜか?

まだ最短経路の決まっていない点を経由した方が経路長が短くなるパスが存在するかもしれないため

(6)

Bellman 方程式

点 j ^{の最短経路長を} u

_j

^{とするとき、}

u

_j

^{が満たす関係式・・・} Bellman 方程式

{ ^u ^w } ^j ^s

u

_i _ij

j

= min

i

+ ∀ ≠

= 0 u

s

w_ij

i j

始点 s

u_i

u_j

最小値原理より

Bellman 方程式を解く

Bellman 方程式の解 = 最短経路

漸化的に解く

u[i] が更新されたら、枝 (i,j) が存在する点 j について u[j] を更新する

すべての点 j について u[j] が変化しなくなったら、解が得られている

Bellman-Ford法

リストを用いた Bellman-Ford 法実装

ints,update,minL,i,u[N], prev[N];

EDGE *edge_top, *ep;

for( i=0 ; i<N ; i++ ) u[i] = 9999;

s = 0; u[s] = 0;

do{

update = 0;

for( ep=edge_top ; ep != NULL; ep=ep->next ){

if( u[ep->i]+ep->w < u[ep->j] ){

u[ep->j] = u[ep->i]+ ep->w;

prev[ep->j] = ep->i;

update = 1;

}

} while} ( update );

十分大きな正数 /*リストを正しく作成する必要あり(ここでは省略) */

始点s=0とする

経路を記録経路長が短くなったら更新フラグを1に

do - while文

条件が成り立つ間、文を実行

do

文

while(

式 );

意味: まず1回文を実行する。

　　　　式が真の間、文を実行。

式文

True

False

式文 True

False

do-while文の実行の様子 “while(式) 文;”の実行の様子

Bellman-Ford 法の計算複雑度

すべての枝を順に調査

経路長が更新されたら、再度調査実行

負ループがなければ最短経路を構成する枝数は N 未満・・・更新は高々 N-1 回

) (NE O

実行時間

負ループのある最短経路問題

最短経路は不定

⇒ 負ループを繰り返すごとに経路長は減少

「経路にループを含まない」という制約を与えると意味のある問題として定式化される

効率よく最短経路を求めるアルゴリズムは見つかっていない

負ループが存在する場合の最短経路問題は

負ループが存在しない場合の問題とは

性格が異なる

(7)

組み合わせ最適化問題

ある条件を満足する解候補のうち、

ある評価尺度が最適になる解を選ぶ問題

例: 最短経路問題

条件 : 始点から終点への連続した枝集合 (経路)

評価尺度 : 枝重み和が小さい

組み合わせ最適化問題の困難さ

組み合わせ最適化問題を 3 つに分類

P: 多項式可解な問題

問題サイズの多項式オーダの手数で解が得られる

⇒計算複雑度が多項式オーダの解法が存在

NP: 非決定的多項式可解な問題

都合良く選択肢を選ぶと、問題サイズの多項式オーダの手数で解が得られる

PでもNPでもない問題

PやNPよりも難しい問題

問題の困難さ

組み合わせ最適化問題の分類とその関係

P 問題の例

ソート(並べ替え)

最短経路問題

オペレーションズ・リサーチ

NP P

全組み合わせ問題

NP問題

NP: 非決定的多項式可解な問題

都合良く選択肢を選ぶと、問題サイズの多項式オーダの手数で解が得られる

工学的に有用な問題が多数含まれる

負ループを含む最短経路問題

セールスマンの巡回問題

タスク・スケジューリング問題　など

セールスマンの巡回問題

問題の定義

「 N 個の都市を順に訪問するための旅費が最小になる訪問順を求めよ」

都市間の旅費は非負

最短経路 ( 最小費用 ) を求める問題

一見すると最短経路問題として解けそう?

すべての訪問順を列挙して最小費用の順路を求める方法しか知られていない ⇒

O ( N ! )

NP 問題と P 問題

NP 問題の解には、

今のところ非多項式オーダの手数が必要

多項式オーダの解法が存在しないことは証明されていない

もしかすると

NP=P

最短経路問題とは

プログラミング言語 I 第 10 回 最短経路問題