Microsoft PowerPoint - H20第10回最短経路問題-掲示用.ppt

プログラミング言語

I 第10回

最短経路問題

埼玉大学工学部

電気電子システム工学科

最短経路問題とは

„

始点から終点へ行く経路が複数通りある

場合に、最も短い経路を見つける問題

最短経路問題の応用例

„

カーナビゲーション

„

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

„

経路

=道路

„

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

„

経路の短さ

=所要時間の短さ

„

鉄道乗り換え案内

„

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

„

経路

=路線

„

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

„

経路の短さ

=料金の安さ

問題の定式化

„

定式化

: 問題の意味が変化しないことに注

意して、明確な形式に問題を整理すること

„

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

„

あいまいな点をなくす

„

さらに、問題を解くプログラムが容易に作

成できるような定式化を行うことが重要

グラフ

„

プログラミングに適した問題定式化の道具

としてよく用いられる

„

1個以上の

点

(ノード)と2つの点を結ぶ

枝

か

らなる

点

枝

グラフ

(その2)

„

点を共有する枝の集合を

パス

(path、経路)

という

„

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

„

一般に始点と終点が同じパスは複数通り

存在する

(1通りしか存在しない場合や、

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

始点

終点

パス

グラフ

(その3)

„

枝に

重み

を与える

„

パスの重みは、

枝重みの和

とする

始点

終点

パス

: 重み12

2

1

9

6

3

5

2

2

始点・終点が同じ複数通りのパス

パスによって重みは異なる

枝重み

最短経路問題の定式化

„

グラフ

によって問題を

入力

　　　　　　

(始点、終点、枝重み)

„

鉄道乗り換え案内の場合

„

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

横浜

品川

東京

上野

赤羽

大宮

池袋

新宿

渋谷

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

280円

260円

160円

150円 150円

150円

290円

160円

160円

150円

160円

2,750円

最小値原理

„

始点

sから終点tへの最短経路上の点をvと

すると、パス

p(s,v)とパスp(v,t)はともに

最短経路である

s

始点

終点

sからtへの最短経路

t

sからvへの

最短経路

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

始点

最短経路アルゴリズム

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

1

最短経路アルゴリズム

1(その3)

„

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

始点

2

1

s

3

6

a

d

b

c

f

e

0

3

₂

4

1 0

2

2

₄

5

3

6

1

2

1

s

3

6

a

d

b

c

f

e

3

₂

4

1 0

2

0

2

_4→2

5

3

6

1

2

2

1

s

3

6

a

d

b

c

f

e

3 2

4

1 0

0

₂

5

3

1

2

2

2

1

s

3

6

a

d

b

c

f

e

3 2

4

1 0

0

5→4

3

最短経路アルゴリズム

1(その4)

„

アルゴリズムのポイント

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

さらに枝

1本で到達する点のうち、

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

1

2

s

7

3

4

2

2

4

5

3

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]

ダイクストラ法の実装

int

s, 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への経路長を更新

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

int

s, 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

;

if

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

}

}

十分大きな正数

枝

(s,j)が存在しない

始点

s=0

とする

点

sは最短経路決定

点数

N

点

sは経路長が最短

点

jへの経路長を更新

最短経路既定の点は除外

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

„

経路長最短の点を

1つ選び経路を決定

„

その点から

1本の枝で接続する点について

経路長を調べなおす

„

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

繰り返す

)

(

N

2

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

j

i

枝の有無を

表す

2次元

配列

e[i][j]

の例

0がほとんど

配列による枝表現の問題

„

枝の有無

(e[i][j]==1か否か)を調べる処

理が必要

„

枝が無くても

(e[i][j]=0)を記憶する必要が

あるためメモリを大量に消費し、速度低下

(スラッシング)

配列に代わる、不規則なデータを

効率よく記録する方式が必要

リスト構造

リストの管理

„

リストの要素

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

タを備える

„

ポインタを用いて要素をつなげる

=

リスト

データ領域

ポインタ

要素

次の要素を指す

リストの実装

„

構造体によって、データ領域と次要素への

ポインタをまとめて管理する

例

要素の構造体型を宣言

typedef struct

Edge {

struct

Edge *next;

int

i,j; // 点1, 点2

int

w; // 枝重み

} EDGE;

次要素へのポインタ

データ領域

例

リストの先頭を指すポインタを宣言

EDGE *edge_top =

NULL

;

リストの実装

(その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

5

3

4

6

6

最短経路長の

決まっている点

経路長を

更新する点

新たに最短経路長

の決まった点

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

7

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

„

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

NULL

点

2

枝重み

点

2

枝重み

点

2

枝重み

0

0

0

edge[0]

NULL

点

2

枝重み

点

2

枝重み

点

2

枝重み

1

1

1

edge[1]

edge[2]

点

2

枝重み

1

点ごとに

接続する

枝数は変化

点

2

2

点

0に接続する

枝のリスト

点

1に接続する

枝のリスト

ダイクストラ法と組合わせる

場合、メンバ「点

1」は不要

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

int

s, 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

;

if

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

}

}

十分大きな正数

始点

s=0

とする

最短経路既定の点は除外

点

sは最短経路決定

点数

N

点

sは経路長が最短

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

始点

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

なぜか

?

まだ最短経路の決まっていない点を経由した方が

経路長が短くなるパスが存在するかもしれないため

Bellman方程式

„

点

j

の最短経路長を

u

_j

とするとき、

u

_j

が満たす関係式・・・

Bellman方程式

{

u

w

}

j

s

u

_i

_ij

i

j

= min

+

∀

≠

0

=

s

u

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法実装

int

s,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

実行時間

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

„

最短経路は不定

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

„

「経路にループを含まない」という制約を

与えると意味のある問題として定式化される

効率よく最短経路を求めるアルゴリズムは

見つかっていない

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

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

性格が異なる

組み合わせ最適化問題

„

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

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

„

例

: 最短経路問題

„

条件

: 始点から終点への連続した枝集合

(経路)

„

評価尺度

: 枝重み和が小さい

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

„

組み合わせ最適化問題を

3つに分類

„

P: 多項式可解な問題

„

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

られる

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

„

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

„

都合良く選択肢を選ぶと、問題サイズの多項

式オーダの手数で解が得られる

„

PでもNPでもない問題

„

PやNPよりも難しい問題

問題の困難さ

„

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

„

P問題の例

„

ソート

(並べ替え)

„

最短経路問題

„

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

NP

P

全組み合わせ問題

NP問題

„

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

„

都合良く選択肢を選ぶと、問題サイズの多項

式オーダの手数で解が得られる

„

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

„

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

„

セールスマンの巡回問題

„

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

セールスマンの巡回問題

„

問題の定義

「

N個の都市を順に訪問するための旅費が

最小になる訪問順を求めよ」

„

都市間の旅費は非負

„

最短経路

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

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

?

すべての訪問順を列挙して最小費用の順路を

求める方法しか知られていない ⇒

O

(N

!

)

NP問題とP問題

„

NP問題の解には、

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

„

多項式オーダの解法が存在しないことは

証明されていない

„

もしかすると

NP=P

かもしれない

„

NP問題のどれか1つについて多項式オーダ

の解法が見つかれば

NP=P

すべての

NP問題が多項式オーダで解ける!

まとめ

„

問題定式化とグラフ

„

最短経路問題

„

効率よい解法

„

ダイクストラ法

„

Bellman-Ford法

„

リスト構造

„

組み合わせ最適化問題と

NP