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

(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円

290円

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

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

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

1 s

3

6 a

d

b

c

f

e

3 2

4 1 0

2

0 ₂

5

3

6

1

2

1 s

3

6 a

d

b

c

f

e

3 2

4 1 0

2

0 5→4

3

6 最短経路アルゴリズム

1(その4)

アルゴリズムのポイント

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

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

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

1

2 s

7

3

4

2

4

5

3

4

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

最短経路既定の点は除外

(4)

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

経路長最短の点を

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 010000000000000000000010100000000000000000000000000000 …

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

;

(5)

リストの実装

(その2)

リストの例

リストを順にたどる処理

edge_top

NULL

点2

枝重み

点2

枝重み

点2

枝重み

点1

3本の枝を

記録するリスト

リストの

末尾では

nextメンバは

NULL

EDGE *ep;

for

( ep=edge_top ; ep !=

NULL

; ep=ep->next ){

…

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

}

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

最短経路が決まるたびに、その点から

枝

1本でつながる点の経路長更新

1

2 s

7

3

4

2

4

5

3

4

6

6 最短経路長の

決まっている点

経路長を

更新する点

新たに最短経路長

の決まった点

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

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

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

NULL

点2

枝重み

点2

枝重み

点2

枝重み

0

0 edge[0]

NULL

点2

枝重み

点2

枝重み

点2

枝重み

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

始点

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

なぜか?

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

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

(6)

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

実行時間

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

最短経路は不定

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

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

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

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

見つかっていない

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

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

性格が異なる

(7)

組み合わせ最適化問題

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

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

例: 最短経路問題

条件

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

(経路)

評価尺度

: 枝重み和が小さい

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

組み合わせ最適化問題を

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問題が多項式オーダで解ける!

(8)

まとめ

問題定式化とグラフ

最短経路問題

効率よい解法

ダイクストラ法

Bellman-Ford法

リスト構造

組み合わせ最適化問題とNP

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

プログラミング言語

I 第10回

最短経路問題

埼玉大学工学部

電気電子システム工学科

伊藤 和人

最短経路問題とは



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

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

経路の短さの決め方によって様々な応用

最短経路問題の応用例



カーナビゲーション

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

経路=道路

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

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



鉄道乗り換え案内

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

経路=路線

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

経路の短さ=料金の安さ

問題の定式化



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

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

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

あいまいな点をなくす



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

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

グラフ



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

としてよく用いられる



1個以上の

点

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

枝

か

らなる

点

枝

グラフの例

グラフ

(その2)



点を共有する枝の集合を

パス

(path、経路)

という



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



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

存在する

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

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

始点

終点

パス

グラフ

(その3)



枝に

重み

を与える



パスの重みは、

枝重みの和

とする

始点

終点

パス

: 重み12

2

伊藤和人