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

プログラミング言語I 第10回
最短経路問題
埼玉大学工学部
電気電子システム工学科
伊藤 和人
最短経路問題とは
„
始点から終点へ行く経路が複数通りある
場合に、最も短い経路を見つける問題
経路の短さの決め方によって様々な応用
Copyright © 2008 Kazuhito Ito
最短経路問題の応用例
„
カーナビゲーション
„
„
„
„
„
現在地から目的地まで最短時間のルート
経路=道路
交差点において走る道路を変更してもよい
経路の短さ=所要時間の短さ
鉄道乗り換え案内
„
„
„
„
始発駅から目的駅まで料金最低のルート
経路=路線
駅において路線を乗り換えてもよい
経路の短さ=料金の安さ
Copyright © 2008 Kazuhito Ito
問題の定式化
„
定式化: 問題の意味が変化しないことに注
意して、明確な形式に問題を整理すること
„
„
„
条件と解の性質を明確にする
あいまいな点をなくす
さらに、問題を解くプログラムが容易に作
成できるような定式化を行うことが重要
Copyright © 2008 Kazuhito Ito
グラフ
„
„
プログラミングに適した問題定式化の道具
としてよく用いられる
1個以上の点(ノード)と2つの点を結ぶ枝か
らなる
点
枝
グラフの例
Copyright © 2008 Kazuhito Ito
グラフ(その2)
„
„
„
点を共有する枝の集合をパス(path、経路)
という
パスの始点と終点を定める
一般に始点と終点が同じパスは複数通り
存在する(1通りしか存在しない場合や、
1つも存在しない場合あり)
始点
終点
パス
Copyright © 2008 Kazuhito Ito
グラフ(その3)
„
„
枝に重みを与える
パスの重みは、枝重みの和とする
5
枝重み
始点
2
6
3
1
9
2
2
終点
パス: 重み12
始点・終点が同じ複数通りのパス
パスによって重みは異なる
Copyright © 2008 Kazuhito Ito
最短経路問題の定式化
„
„
グラフによって問題を入力
(始点、終点、枝重み)
重み最小のパスを見つける
鉄道乗り換え案内の場合
„
乗換駅を点、枝重みを料金とすればよい
渋谷
横浜
260円
160円
品川
池袋
150円 150円
150円
赤羽
150円
東京
上野
大宮
290円
160円
160円
280円
Copyright © 2008 Kazuhito Ito
新宿
160円
2,750円
最小値原理
„
始点
始点sから終点tへの最短経路上の点をvと
すると、パスp(s,v)とパスp(v,t)はともに
最短経路である
s
sからvへの
最短経路
v
vからtへの
最短経路
t
終点
sからtへの最短経路
終点以外の最短経路を順次求めて、
最終的に終点への最短経路を求める
Copyright © 2008 Kazuhito Ito
問題の分類
„
„
„
枝重みが0または正の場合
枝重みが0、正、負で負ループがない場合
枝重みが0、正、負で負ループがある場合
ループ: 始点と終点が一致したパス
負ループ: 枝重み和が負のループ
5
2
1
3
1
-8
Copyright © 2008 Kazuhito Ito
2
0
枝重みが0、正、負で
負ループがある場合
負ループ: 重み-2
最短経路アルゴリズム1
„
枝重みが0または正の場合を考える
2
始点
s
6
2
始点
a
1
0
b
3
2
4
c 1
3
0
d
2
0
a
1
b
3
2
4
c 1
6
3
0
d
2
Copyright © 2008 Kazuhito Ito
s
始点sから他の点
への最短経路を求める
始点sから点bへの
最短経路が1である
と決定できる
なぜか?
最短経路アルゴリズム1(その2)
„
枝重みが0または正の場合
2
始点
s
2a
1
0
1
b
3
2
3 4
c 1
6
3
0
d
2
6
aを経由
パス重みは2以上
cを経由
パス重みは3以上
dを経由
パス重みは6以上
枝重みが0または正であるので、
点a, c, dを経由するどのパスも
重みが1以上となるため
Copyright © 2008 Kazuhito Ito
最短経路アルゴリズム1(その3)
„
次に経路が最短な点を求める
2
2 a
0
e
4
1 1b 3 2
5
始点
f
s
3 4
c 1
6
3
0
d
6
2
0 e 2
2 a
2
1 1b 3 2
5
f
s
3 4
c 1
6
3
0
d
6
2
Copyright © 2008 Kazuhito Ito
2
2 a
1
0
1
b
e
3
4→2
2
5
f
3 4
c 1
6
3
0
d
6
2
0 e 2
2 a
2
1 1b 3 2
5→4
f
s
3 4
c 1
6
3
0
d
6
2
s
最短経路アルゴリズム1(その4)
„
アルゴリズムのポイント
ダイクストラ法
最短経路長の定まった点から、
さらに枝1本で到達する点のうち、
経路長最短の点は、最短経路と決定できる
1
Copyright © 2008 Kazuhito Ito
4
2
3
7
さらに枝1本で
到達する点
7
3 4
2
s
最短経路長の
決まっている点
6
4
2
5
6
経路長が最小
⇒最短経路を
決定できる点
C言語によるグラフ表現1
„
„
2次元配列を用いる方法
枝が結ぶ2点(i,j)
i
„
j
配列要素e[i][j]が枝を表す
e[i][j]=1: 枝あり
e[i][j]=0: 枝なし
„
i⇒j と j⇒i を区別しない場合
e[j][i] = e[i][j] とする
Copyright © 2008 Kazuhito Ito
C言語によるグラフ表現1(続き)
„
枝(i,j)の重み ・・ w[i][j]が記憶
i
j
w[i][j]
„
i⇒j と j⇒i を区別しない場合
w[j][i] = w[i][j] とする
Copyright © 2008 Kazuhito Ito
始点s=0とする
ダイクストラ法の実装
点数N
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++ ){
点sは最短経路決定
f[s] = 1;
for( j=0 ; j<N ; j++ ){
枝(s,j)が存在しない
if( e[s][j] != 1 ) continue;
if( u[s]+w[s][j] < u[j] ) u[j]=u[s]+w[s][j];
}
点jへの経路長を更新
minLen = 9999;
最短経路既定の点は除外
for( j=0 ; j<N ; j++ ){
if( f[j] == 1 ) continue;
if( u[j] < minLen ){ minLen = u[j]; s = j; }
}
点sは経路長が最短
}
Copyright © 2008 Kazuhito Ito
長さだけでなく経路を記録
始点s=0とする
点数N
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++ ){
点sは最短経路決定
f[s] = 1;
for( j=0 ; j<N ; j++ ){
枝(s,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 */
}
点jへの経路長を更新
minLen = 9999;
最短経路既定の点は除外
for( j=0 ; j<N ; j++ ){
if( f[j] == 1 ) continue;
if( u[j] < minLen ){ minLen = u[j]; s = j; }
}
点sは経路長が最短
}
Copyright © 2008 Kazuhito Ito
ダイクストラ法の計算複雑度
„
„
„
経路長最短の点を1つ選び経路を決定
その点から1本の枝で接続する点について
経路長を調べなおす
すべての点について経路が決定するまで
繰り返す
2
O( N )
Copyright © 2008 Kazuhito Ito
プログラムの実行時間
„
ノード数Nとプログラム実行時間の関係
100.00
N=8000
約500Mバイト
10.00
秒
1つのノード
当たり4本の
予想 枝の場合
N=7000
約400Mバイト
1.00
PentiumIV
2.4GHz
512MBメモリ
0.10
0.01
100
Copyright © 2008 Kazuhito Ito
1000
N
10000
100000
プログラムの問題点
„
配列による枝表現はメモリを大量に必要と
し、かつ効率が悪い
010000000000000000000000000000000000000000000000000000
101000000000000000000011000000000000000000000000000000
010110000000000000000000000000000000000000000000000000
001010000000000000000000000000000000000000000000000000
001101000000000000000000000000000000000000000000000000
000010110000000000000000000000000000000000000000000000
000001010000000000000000000000000000000000000001000000
000001100000000000000000000000000000000000000100000100
000000000110000000000000000000000000000000000000000100
000000001010000000000000000000000000000000000000000000
000000001101000000000000000000000000000000000000000010
000000000010100000000000000000000000000000000000100000
000000000001010000000000000000000000000000000000000000
000000000000101001000000000000000000000000000000000010
000000000000010100100000000000000000000000000000000000
000000000000001000000000000000000000000000000010100000
000000000000000001000000100000000000000000000101000000
000000000000010010100000000000000000000000000000000000
000000000000001001010000000010000000000000000000000000
000000000000000000101000000000000000000000000000000000
000000000000000000010100000000000000000000000000010000
000000000000000000001000000000001001000000000000000000
010000000000000000000001000000000000000000000000001000
010000000000000000000010100000000000000000000000000000
…
Copyright © 2008 Kazuhito Ito
i
j
枝の有無を
表す2次元
配列e[i][j]
の例
0がほとんど
配列による枝表現の問題
„
„
枝の有無(e[i][j]==1か否か)を調べる処
理が必要
枝が無くても(e[i][j]=0)を記憶する必要が
あるためメモリを大量に消費し、速度低下
(スラッシング)
配列に代わる、不規則なデータを
効率よく記録する方式が必要
リスト構造
Copyright © 2008 Kazuhito Ito
リストの管理
„
リストの要素
データ領域の他に、次の要素を指すポイン
タを備える
ポインタ
次の要素を指す
要素
データ領域
„
ポインタを用いて要素をつなげる=リスト
Copyright © 2008 Kazuhito Ito
リストの実装
„
構造体によって、データ領域と次要素への
ポインタをまとめて管理する
要素の構造体型を宣言
例 typedef struct Edge {
struct Edge *next;
int i,j; // 点1, 点2
int w; // 枝重み
} EDGE;
次要素へのポインタ
データ領域
リストの先頭を指すポインタを宣言
例 EDGE *edge_top = NULL;
Copyright © 2008 Kazuhito Ito
リストの実装(その2)
„
3本の枝を
記録するリスト
リストの例
edge_top
点1
点2
枝重み
„
点1
点2
枝重み
NULL
点1
点2
枝重み
リストの
末尾では
nextメンバは
NULL
リストを順にたどる処理
EDGE *ep;
for( ep=edge_top ; ep != NULL ; ep=ep->next ){
… /* リスト要素に対する処理 */
}
Copyright © 2008 Kazuhito Ito
ダイクストラ法における枝リスト
„
最短経路が決まるたびに、その点から
枝1本でつながる点の経路長更新
各点に接続する枝リストがあると便利
最短経路長の
決まっている点
1
s
6
4
2
7
3 4
2
新たに最短経路長 4 3 2
7
の決まった点
Copyright © 2008 Kazuhito Ito
5
6
経路長を
更新する点
ダイクストラ法のための枝リスト
„
各点に接続する枝のリスト
edge[0]
点0に接続する
枝のリスト
0
点2
枝重み
0
点2
枝重み
NULL
0
点2
枝重み
edge[1]
点1に接続する
枝のリスト
1
点2
枝重み
1
点2
枝重み
1
点2
枝重み
点ごとに
接続する
枝数は変化
NULL
1
点2
枝重み
edge[2]
Copyright © 2008 Kazuhito Ito
2
点2
枝重み
ダイクストラ法と組合わせる
場合、メンバ「点1」は不要
リストを用いたダイクストラ法
始点s=0とする
点数N
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++ ){
点sは最短経路決定
f[s] = 1;
for( ep=edge[s] ; ep!=NULL ; ep=ep->next ){
if( u[s]+ep->w < u[ep->j] ){
sに接続する枝
u[ep->j]=u[s]+ ep->w;}
を順に調べる
}
minLen = 9999;
点ep->jへの経路長を更新
for( j=0 ; j<N ; j++ ){
最短経路既定の点は除外
if( f[j] ) continue;
if( u[j] < minLen ){ minLen = u[j]; s = j; }
}
点sは経路長が最短
}
Copyright © 2008 Kazuhito Ito
プログラムの実行時間
„
ノード数Nとプログラム実行時間の関係
100.00
N=8000
約500Mバイト
秒
10.00
配列利用
N=40000
約1Mバイト
N=7000
約400Mバイト
1.00
リスト構造
利用
0.10
PentiumIV
2.4GHz
512MBメモリ
0.01
100
Copyright © 2008 Kazuhito Ito
1000
N
10000
100000
最短経路アルゴリズム2
„
負の枝重みが存在する場合
2
始点
s
6
a
1
0
b
3
-1
-4
c 1
3
0
d
-2
ダイクストラ法では最短経路を見つけられない
なぜか?
まだ最短経路の決まっていない点を経由した方が
経路長が短くなるパスが存在するかもしれないため
Copyright © 2008 Kazuhito Ito
Bellman方程式
„
点jの最短経路長をujとするとき、
ujが満たす関係式・・・Bellman方程式
us = 0
u j = min {ui + wij } ∀j ≠ s
i
最小値原理より
始点
Copyright © 2008 Kazuhito Ito
s
ui w
ij
i
j
uj
Bellman方程式を解く
„
„
Bellman方程式の解=最短経路
漸化的に解く
u[i]が更新されたら、枝(i,j)が存在する
点jについてu[j]を更新する
すべての点jについてu[j]が変化しなく
なったら、解が得られている
Bellman-Ford法
Copyright © 2008 Kazuhito Ito
始点s=0とする
リストを用いた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;
経路長が短くなったら
}
更新フラグを1に
}
} while ( update );
Copyright © 2008 Kazuhito Ito
経路長更新の場合再度繰り返し
do - while文
„
条件が成り立つ間、文を実行
do 文 while( 式 );
意味: まず1回文を実行する。
式が真の間、文を実行。
文
式
式
False
False
True
文
True
do-while文の実行の様子
Copyright © 2008 Kazuhito Ito
“while(式) 文;”の実行の様子
Bellman-Ford法の計算複雑度
„
„
„
すべての枝を順に調査
経路長が更新されたら、再度調査実行
負ループがなければ最短経路を構成する
枝数はN未満・・・更新は高々N-1回
実行時間 O (NE )
Copyright © 2008 Kazuhito Ito
負ループのある最短経路問題
„
„
最短経路は不定
⇒ 負ループを繰り返すごとに経路長は減少
「経路にループを含まない」という制約を
与えると意味のある問題として定式化される
効率よく最短経路を求めるアルゴリズムは
見つかっていない
負ループが存在する場合の最短経路問題は
負ループが存在しない場合の問題とは
性格が異なる
Copyright © 2008 Kazuhito Ito
組み合わせ最適化問題
„
„
„
„
ある条件を満足する解候補のうち、
ある評価尺度が最適になる解を選ぶ問題
例: 最短経路問題
条件: 始点から終点への連続した枝集合
(経路)
評価尺度: 枝重み和が小さい
Copyright © 2008 Kazuhito Ito
組み合わせ最適化問題の困難さ
„
„
組み合わせ最適化問題を3つに分類
P: 多項式可解な問題
„
„
NP: 非決定的多項式可解な問題
„
„
問題サイズの多項式オーダの手数で解が得
られる
⇒計算複雑度が多項式オーダの解法が存在
都合良く選択肢を選ぶと、問題サイズの多項
式オーダの手数で解が得られる
PでもNPでもない問題
„
PやNPよりも難しい問題
Copyright © 2008 Kazuhito Ito
問題の困難さ
„
組み合わせ最適化問題の分類とその関係
全組み合わせ問題
NP
P
„
P問題の例
„
„
„
ソート(並べ替え)
最短経路問題
オペレーションズ・リサーチ
Copyright © 2008 Kazuhito Ito
NP問題
„
NP: 非決定的多項式可解な問題
„
„
都合良く選択肢を選ぶと、問題サイズの多項
式オーダの手数で解が得られる
工学的に有用な問題が多数含まれる
„
„
„
負ループを含む最短経路問題
セールスマンの巡回問題
タスク・スケジューリング問題　など
Copyright © 2008 Kazuhito Ito
セールスマンの巡回問題
„
„
„
問題の定義
「N個の都市を順に訪問するための旅費が
最小になる訪問順を求めよ」
都市間の旅費は非負
最短経路(最小費用)を求める問題
一見すると最短経路問題として解けそう?
すべての訪問順を列挙して最小費用の順路を
求める方法しか知られていない ⇒ O (N !)
Copyright © 2008 Kazuhito Ito
NP問題とP問題
„
NP問題の解には、
今のところ非多項式オーダの手数が必要
„
„
„
多項式オーダの解法が存在しないことは
証明されていない
もしかするとNP=Pかもしれない
NP問題のどれか1つについて多項式オーダ
の解法が見つかればNP=P
すべてのNP問題が多項式オーダで解ける!
Copyright © 2008 Kazuhito Ito
まとめ
„
„
„
問題定式化とグラフ
最短経路問題
効率よい解法
„
„
„
„
ダイクストラ法
Bellman-Ford法
リスト構造
組み合わせ最適化問題とNP
Copyright © 2008 Kazuhito Ito