算法の設計と解析

全文

(1)

算法の設計と解析

第六回

2004.12.06

テスト参考

N = 2 n , N = 2 n−1 , g(n) = 7g(n 1) β T (n) =

b n = 1

aT ( n c + b n other a, b, c N +

T (n) =

 

 

O(n) a < c O(n log n) a = c O(n log ca) a > c

2 < a < 3

最小全域木

全域木の定義

G(V, E), V :

点の集合、EV

× V

辺の集合

G(V, E)

のすべての辺を含む木

2

4 3

1 2

4 3

1

2

4 3

1

1:

一般的には複数の取り方がある。

グラフ

G(V,E,W),W

は辺の重み

E V × V

上の関数、ω(i, j) =

ω(j, i)i, j V

を考え、T

G(V, E)

の全域

木とするとき

X

e∈T

ω(e) min

とする。Tを求めよ。

1

(2)

1 4

6 5

3

2

1 4

2

2:

辺長は

7

で最小

Greedy Algorithm

0.1 ω(i, j)

e k

と番号を付け直す

ω(i, j) e k , k = 1, ..., |E|

0.2e k

を小さいものから並べる。e

1 e 2 ... e |E|

としておく。

1.e 1

を選ぶ

2.

ループが発生しない限り小さいものから

e k

を選ぶ

3.

すべての点が選ばれれば終了

X ω(e) max, ω(e) > 0, v(e) = 1 ω(e)

とすれば、

X

ω(e) min X

v(e) max

ソートの一般化順序が決まっていれば良い。E

= {e 1 , ..., e m }

の要求に関して順序

(半順序)

< (≤)

を考える。

π

< (≤)

に関するソートとする。

E = {e 1 , ..., } e i R 3 (n

次元ベクトル)

e i < e j ⇔ |e i | < |e j | e i < e j e j e i

の要素がすべて正)

E

から独立なるベクトルを選ぶ

e i = (0, ...1, 1, ...)

要素が

1,0

のベクトル ソート

E = {e 1 , ..., e n }

の要素を

<

の順に従って並べかえる

置換置換する際の要素の個数は

2

次元なら

2

個、3 元なら

3!

個、n次元なら

n!

ある。その中から、求める性質のものを

1

つ構成する。

最小全域木 最小化

X

e

k

∈T

ω(e k ) min

e k T

であるとして、求めたいのは

T

である。しかし、この式では

T

は求められない。

GA e k

を小さいものから付加することによって

T

を構成した。

x = (x 1 , ...x n ), x 1 ∈ {0, 1}

m = |E|

x i =

0

e i

T

の要素でない

1

e i

T

の要素である

P

e

k

∈T ω(e k ) P m

i=1 x i ω(e i ) min

2

(3)

f(x) min : x

の値を求める

f (x) = x T ω

ω = (ω(e 1 )ω(e 2 )...ω(e n )) T

(1)

一般形

(線形計画問題)

f (x) = φ T x

を最小化する

x

を求める。

φx R n

x

に関する条件

Ax b b R m

A R m×n m × n

次行列

(2)

3

Updating...

参照

Updating...

関連した話題 :