全文

(1)

3.ネットワーク計画

(2)

はじめに

グラフ上の最適化問題

最短路問題(始点から終点までの最短路,

カーナビ)

最大流問題

最小費用流問題

輸送問題・割当問題

(3)

交通流割当問題( ITS, ロードプライシング)

最長路問題(最長片道切符,一番長いしりと り)

巡回セールスマン問題,ハミルトン閉路(すべ ての節点を一度だけ通って戻ってくる)

グラフの連結性(電話網,信頼性ネットワー ク)

スケジューリング(配送計画,アポロ計画,

PERT ,時間割作成など)

などなど

(4)

グラフ G=(V,E)

節点( node )の集合 V と,枝( arc または link ) の集合 E からなる

枝には,長さ,容量,コストなどの制約がある

枝に向きがある:有向グラフ ない:無向グラフ

モデル化の例:作業計画,研究室配属(二部グ

ラフのマッチング)などなど

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

(6)

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 枝

節点

各枝は矢印の方向にのみ進める(物を流せられる)

節点番号の

順序に注意

(7)

最短路問題

各枝の距離(または時間)が与えられたとき,始点(ノード1)か ら終点(ノード7)までの路(パス)の中で,最も短いものを見つ ける問題

7 6

1

7

2

5

1

2

8

3

4 3

枝の長さ

始点 終点

最短路:(1,2)(2,4)(4,3)(3,6)(6,7) 長さ10 路(パス):枝を並べたもの

(8)

最大流問題

各枝の容量が与えられたとき,ソース(ノード1)からシンク(ノー ド7)への流量(フロー)の最大値を求める問題

7 6

7

4

4

2

1

4

2

3

4 3

ソース シンク

枝の容量

6

2 1

3

3

3 3

3

2 0

最適フロー(最大値:8)

8

最大流最小カット定理

8

(9)

同じ問題で,無向グラフ(双方向にフローを流せる)になった場 合.

7 6

7

4

4

2 1

4

2

3

4 3

送電ネットワークなど

7

2 1

3

4

3 4

3

2 1

ソース シンク

(10)

同じ問題で,無向グラフ(双方向にフローを流せる)になった場 合.

7 6

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 とすればよい

(11)

最小費用流問題

各枝の容量と,1単位フローを流すときのコストが与えられたと き,ソース(ノード1)からシンク(ノード7)まで5単位フローを費 用最小で流すには,どのようにフローを流せばよいか?

7 6

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

ソース シンク

(12)

交通流割当問題(ユーザー最適化)

O:出発地(Origin) D:目的地(Destination)

O D

A

B

①経路A,Bがどちらも渋滞していない→旅行者は経路B(距離 が短い=速い)を選択する

(13)

交通流割当問題(ユーザー最適化)

O:出発地(Origin) D:目的地(Destination)

②Bを利用する旅行者が増える→渋滞する→時間がかかる

O D

A

B

(14)

交通流割当問題(ユーザー最適化)

O:出発地(Origin) D:目的地(Destination)

③Bの方が移動時間が長くなる→Aを利用しはじめる

O D

A

B

(15)

交通流割当問題(ユーザー最適化)

O:出発地(Origin) D:目的地(Destination)

④最終的に移動時間は一致

O D

A

B

均衡流

(16)

問題例のまとめ

最短路問題,最大流問題,最小費用流問題,

輸送問題,割当問題(マッチング),オイラー 閉路(一筆書き)など

最長路問題,巡回セールスマン問題,ハミル トン閉路,一般のスケジューリング問題,配送 計画など

簡単

難しい(最長路+スケジューリングの例)

(17)

講義の内容

最短路問題の解法:ダイクストラ法

ネットワークシンプレックス法

計算量,その他の話題

組み合わせ的アルゴリズムの紹介

最大流,最小費用流をシンプレックス法で解く

(18)

ダイクストラ法(最短路問題の解法)

最適性の原理

終点までの最短路においては,途中の節点 までも始点からの最短路

始点 ノードi 終点

最適制御の基本原理でもある

最短路

(19)

枝の長さはすべて非負と仮定

以下の記号を導入

E j

i

a

ij

 0 ( , ) 

の直前にある節点 最短路において,節点

の補集合 節点の集合

一致している からの最短路の距離と

が始点

からの距離の上限値 始点

i i

p

S V

S S

S

s i

d V S

s i

d

: ) (

\ :

) ( : : ) (

(20)

ダイクストラ法のアルゴリズム

 

   

へ.

として

に対し なるすべての枝

かつ

とする.

を選ぶ.

なる節点 いとき ならば終了.そうでな

その他の節点 始点

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

   

 

 

 

(21)

7 6

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

(22)

7 6

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

(23)

7 6

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

(24)

7 6

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

(25)

7 6

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 ) mind ( i ) i Sなる v 4

  1 , 2

 S

    1 , 2 4

S

(26)

7 6

1

7

2

5 1

2

8

3

4 3

1 , 2 , 4, 3 , 5 , 6 , 7

 S

S

1 8

3 

5

0

1

2

1

2

1 , 2 , 4

 S

以下,同じ手順が繰り返される

STEP 1 ( 3 回目)終了時

(27)

演習課題

例題の続きをダイクストラ法でおこなって,最 短路を求めよ.

締切: 5 月 30 日(木) 1 6時,Ⅳ系事務室

Updating...

参照

Updating...

関連した話題 :