3.ネットワーク計画
はじめに
グラフ上の最適化問題
最短路問題(始点から終点までの最短路,
カーナビ)
最大流問題
最小費用流問題
輸送問題・割当問題
交通流割当問題( ITS, ロードプライシング)
最長路問題(最長片道切符,一番長いしりと り)
巡回セールスマン問題,ハミルトン閉路(すべ ての節点を一度だけ通って戻ってくる)
グラフの連結性(電話網,信頼性ネットワー ク)
スケジューリング(配送計画,アポロ計画,
PERT ,時間割作成など)
などなど
グラフ G=(V,E)
節点( node )の集合 V と,枝( arc または link ) の集合 E からなる
枝には,長さ,容量,コストなどの制約がある
枝に向きがある:有向グラフ ない:無向グラフ
モデル化の例:作業計画,研究室配属(二部グ
ラフのマッチング)などなど
1
2
3
5
7 6
4 無向グラフの例
(11,,22,),3,(41,,53,),6(,72,4),(2,5),(3,4),(3,6),(4,7),(5,6),(5,7),(6,7)
E
V 枝
節点
各枝は双方向に進める(物を流せられる)
節点 5
枝 (6,7)
1
2
3
5
7 6
4 有向グラフの例
(11,,22,),3,(41,,53,),6(,72,4),(2,5),(4,3),(3,6),(4,7),(6,5),(5,7),(6,7)
E
V 枝
節点
各枝は矢印の方向にのみ進める(物を流せられる)
節点番号の
順序に注意
最短路問題
各枝の距離(または時間)が与えられたとき,始点(ノード1)か ら終点(ノード7)までの路(パス)の中で,最も短いものを見つ ける問題
1
2
3
5
7 6
4
1
7
2
5
1
2
8
3
4 3
枝の長さ
始点 終点
最短路:(1,2)(2,4)(4,3)(3,6)(6,7) 長さ10 路(パス):枝を並べたもの
最大流問題
各枝の容量が与えられたとき,ソース(ノード1)からシンク(ノー ド7)への流量(フロー)の最大値を求める問題
1
2
3
5
7 6
4
7
4
4
2
1
4
2
3
4 3
ソース シンク
枝の容量
6
2 1
3
3
3 3
3
2 0
最適フロー(最大値:8)
8
最大流最小カット定理
8
同じ問題で,無向グラフ(双方向にフローを流せる)になった場 合.
1
2
3
5
7 6
4
7
4
4
2 1
4
2
3
4 3
送電ネットワークなど
7
2 1
3
4
3 4
3
2 1
ソース シンク
同じ問題で,無向グラフ(双方向にフローを流せる)になった場 合.
1
2
3
5
7 6
4
7
4
4
2 1
4
2
3
4 3
送電ネットワークなど
7
2 1
3
4
3 4
3
2 1
ソース シンク
最大値 9
i j i j とすればよい
最小費用流問題
各枝の容量と,1単位フローを流すときのコストが与えられたと き,ソース(ノード1)からシンク(ノード7)まで5単位フローを費 用最小で流すには,どのようにフローを流せばよいか?
1
2
3
5
7 6
4
(5,1)
(1,5)
(3,2)
(3,2)
(1,1)
(4,3)
(4,8)
(3,1)
(3,5) (3,2)
(容量, 1 単位あ たりのコスト)
2
3 0
3
1
1 1
3
1 2
5
最適フロー(最小コスト:44)
ソース シンク
交通流割当問題(ユーザー最適化)
O:出発地(Origin) D:目的地(Destination)
O D
A
B
①経路A,Bがどちらも渋滞していない→旅行者は経路B(距離 が短い=速い)を選択する
交通流割当問題(ユーザー最適化)
O:出発地(Origin) D:目的地(Destination)
②Bを利用する旅行者が増える→渋滞する→時間がかかる
O D
A
B
交通流割当問題(ユーザー最適化)
O:出発地(Origin) D:目的地(Destination)
③Bの方が移動時間が長くなる→Aを利用しはじめる
O D
A
B
交通流割当問題(ユーザー最適化)
O:出発地(Origin) D:目的地(Destination)
④最終的に移動時間は一致
O D
A
B
均衡流
問題例のまとめ
最短路問題,最大流問題,最小費用流問題,
輸送問題,割当問題(マッチング),オイラー 閉路(一筆書き)など
最長路問題,巡回セールスマン問題,ハミル トン閉路,一般のスケジューリング問題,配送 計画など
簡単
難しい(最長路+スケジューリングの例)
講義の内容
最短路問題の解法:ダイクストラ法
ネットワークシンプレックス法
計算量,その他の話題
組み合わせ的アルゴリズムの紹介
最大流,最小費用流をシンプレックス法で解く
ダイクストラ法(最短路問題の解法)
最適性の原理
終点までの最短路においては,途中の節点 までも始点からの最短路
始点 ノードi 終点
最適制御の基本原理でもある
最短路
枝の長さはすべて非負と仮定
以下の記号を導入
E j
i
a
ij 0 ( , )
の直前にある節点 最短路において,節点
の補集合 節点の集合
一致している からの最短路の距離と
が始点
からの距離の上限値 始点
i i
p
S V
S S
S
s i
d V S
s i
d
: ) (
\ :
) ( : : ) (
ダイクストラ法のアルゴリズム
へ.
として
に対し なるすべての枝
かつ
とする.
を選ぶ.
なる節点 いとき ならば終了.そうでな
その他の節点 始点
1 Step
) ( ,
) ( )
( )
( )
(
) , ( )
, (
\ ,
: 2 Step
) ( min
) ( : 1 Step
: ) 0
( , ,
: 0 Step
v j
p a
v d j
d a
v d j
d
j v S
j E
j v
v S
S v
S S
v S
i i d v
d
V S
s i i
d V S
S
vj
vj
1
2
3
5
7 6
4
1
7
2
5 1
2
8
3
4 3
例題: STEP 0 (初期化)と STEP 1 ( 1 回目)
1 , 2 , 3 , 4 , 5 , 6 , 7
,
S V S
0
( ) 1
min )
( v d i i S v
d なる
始点からの暫定距離 :
) (i
d p (i ) : 直前のノード
1
S
1
2
3
5
7 6
4
1
7
2
5 1
2
8
3
4 3
STEP 2 ( 1 回目)
1 , 2 , 3 , 4 , 5 , 6 , 7
S S
0
5 5
) 1 ( )
3 ( ,
1 1
) 1 ( )
2
( d d d
d
1
S
1
2
3
5
7 6
4
1
7
2
5 1
2
8
3
4 3
STEP 1 ( 2 回目)
1 , 2 , 3 , 4 , 5 , 6 , 7
S S
1
5
1
1
5 5
) 1 ( )
3 ( ,
1 1
) 1 ( )
2
( d d d
d
( ) 2
min )
( v d i i S v
d なる
1 2
S S 1
0
1
2
3
5
7 6
4
1
7
2
5 1
2
8
3
4 3
STEP 2 ( 2 回目)
1 , 2 , 3 , 4 , 5 , 6 , 7
S
S
1
5
0
1
1
8 7
) 2 ( )
5 ( ,
3 2
) 2 ( )
4
( d d d
d
1 , 2
S
1
2
3
5
7 6
4
1
7
2
5 1
2
8
3
4 3
STEP 1 ( 3 回目)
1 , 2 , 3 , 4 , 5 , 6 , 7
S
S
1 8
3
5
0
1
2
1
2
8 7
) 2 ( )
5 ( ,
3 2
) 2 ( )
4
( d d d
d d ( v ) min d ( i ) i S なる v 4
1 , 2
S
1 , 2 4
S
1
2
3
5
7 6
4
1
7
2
5 1
2
8
3
4 3