d - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第10回
10. 中央値と順序統計量
• n 要素の集合の i 番目の順序統計量 (order
statistic): その集合で i 番目に小さい要素
• 最小値 (minimum): i = 1
• 最大値 (maximum): i = n
• 中央値 (median):
– n が奇数のとき i = (n+1)/2
– n が偶数のとき i  (n  1) / 2とi  (n  1) / 2
– いずれの場合も i  (n  1) / 2
2
選択問題 (selection problem)
• 入力: n 個の異なる数の集合 A, 整数 i (1  i  n)
• 出力: A 中のちょうど i 1 個の他の要素より大きい
要素 x  A
• 選択問題は O(n lg n) 時間で解ける
– A の要素をソートする
– 出力配列の i 番目の要素を返す
• 選択問題は O(n) 時間で解ける
3
10.2 平均線形時間の選択法
• 順序統計量は (n) 時間で求まるが複雑
• まず，平均的に O(n) 時間のアルゴリズムを考える
data RANDOMIZED_SELECT(data *A, int p, int r, int i)
// A[p..r] の中で i 番目に小さい要素を返す
{
int q, k;
if (p == r) return A[p];
q = RANDOMIZED_PARTITION(A,p,r); // q: 分割の位置
k = q – p + 1;
// k: 左部分の要素数
if (i <= k) return RANDOMIZED_SELECT(A,p,q,i);
else
return RANDOMIZED_SELECT(A,q+1,r,ik);
4
}
• q = RANDOMIZED_PARTITION(A,p,r);の実行後
– 2つの空でない部分配列 A[p..q], A[q+1..r] に分かれる
– 左側の各要素は右側よりも小さい
– k = q – p + 1; は左側の要素数
• i  k ならば i 番目の要素は左側の i 番目
• i  k ならば i 番目の要素は右側の i  k 番目
• 部分配列のサイズが 1 になるまで繰り返す
5
平均実行時間の上界
• T(n): n 要素の集合での選択問題の平均時間
• 分割の左側のサイズが
– 1 になる確率 = 2/n
– i になる確率 = 1/n (i = 2,3,...,n1)
• T(n) は単調増加と仮定する
n 1
1

T n    T max 1, n  1   T max k , n  k   O(n)
n
k 1

n 1

1
  T n  1  2  T k   O(n)
n
k  n / 2 

2 n 1

T k   O(n)

n k  n / 2 
6
• RANDOMIZED_SELECTの最悪実行時間は(n2)
よって 1/n T(n1) = O(n)
• T(n)  cn と仮定すると
2 n 1
T n  
 ck  dn
n k  n / 2 
n / 2 1 
2c  n 1
   k   k   dn
n  k 1
k 1 
2c  1
1   n   n  
  n  1n      1     dn
n 2
2   2   2  
cn n
 cn  1    1  dn
n2 2
1
3
 c n    dn
2
4
if c(n / 4  1 / 2)  dn 
 cn
7
10.3 最悪線形時間の
選択アルゴリズム
アルゴリズム SELECT: i 番目に小さい要素を返す
1. 入力配列の n 要素をグループに分割
–
–
5要素のグループ n/5 個
n mod 5 要素のグループ高々1個
2. n/5 個の各グループを(挿入ソート等で)ソートし，
それぞれの中央値を求める
3. SELECTを再帰的に用いてステップ2で求めた
n/5 個の値の中央値 x を求める
8
4. PARTITIONを修正したものを用い，入力配列を x
によって分割する．左側の要素数を k とする.
5. i  k ならば，左側で i 番目に小さい要素を再帰
的に見つける．
i  k ならば，右側で ik 番目に小さい要素を再帰
的に見つける．
9
SELECTの実行時間の解析
• 分割に用いた x より大きい要素数の下界を求める
• ステップ 2 で求めた中央値の少なくとも半分は x
(中央値の中央値) 以上
• 中央値が x 以上のグループには，x 以上の値が 3
個以上ある
• x 以上となる要素数は少なくとも
  1  n    3n
3      2  
6
  2  5    10
10
• 同様に，x 以下となる要素数も少なくとも 3n/106
• ステップ 5 で再帰的に呼ばれる SELECT の部分
問題のサイズは高々 7n/10+6
• ステップ 1,4: O(n) 時間
• ステップ 2: 5 要素のソートを n/5 回⇒ O(n)時間
• ステップ 3: T(n/5) 時間
(1)
n  80のとき

T ( n)  
T n / 5  T 7n / 10  6  On  n  80のとき
11
• n  80 に対して T(n)  cn と仮定する.
c を十分大きくとれば
T (n)  c n / 5  c7n / 10  6  On 
 cn / 5  7cn / 10  6c  On 
 9cn / 10  7c  On 
 cn
• よって，SELECTの最悪実行時間は線形
• これは比較しか用いていない
12
• クイックソートの pivot として厳密な中央値を
用いれば，最悪計算量が O(n log n) になる
• ただし，SELECTが複雑なので実行速度は
速くない
• また，in-placeではなくなる
13
最短路問題とダイクストラ法
• 有向グラフ G = (V, E) を考える
– V: 節点集合, 節点数 n
– E: 枝集合, 枝数 m
• グラフ G の各枝 (i,j)  E は長さ aij を持つ
• ある節点 s  V から別の節点 t  V への路の中で，
最も長さの短いものを見つける問題を最短路問題
15
という
2
4
50
30
20
10
1
5
80
3
15
14
• 下のネットワークで節点 1 を s, 節点 5 を t とすると，
s から t へは 1245, 1235,1345,
12345,135 の5つの路がある
• 路の長さはそれぞれ 95, 85, 120, 110, 95 なので，
最短路は 1235 である
• 大規模なネットワークでは全ての路を数え上げる
方法は実用的ではない
15
2
50
4
30
20
10
1
5
80
3
15
15
最適性の原理
• 節点 s から t への最短路 P が得られているとする
• 路 P に含まれる節点を1つ任意に選び, r とする
• 路 P は s から r までの部分 P1 と， r から t への
部分 P2 に分割できる．このとき，P1 は s から r へ
の最短路で，P2 は r から t への最短路となる
– もし P1 より短い s から r への路 P1’が存在するなら，
P1’と P2 をつないだ路は P2 より短くなる
• このような性質を最適性の原理と呼ぶ
P1
P
r
2
s
P1’
t
16
• ある節点 s からネットワークの他の全節点への最
短路を求める問題を考える
• ダイクストラ法は，枝の長さに関する非負条件
aij  0 ((i,j)  E) の仮定の下で，節点 s から各節
点 i  V への最短路の長さの上限値 d(i) を更新し
ていく反復アルゴリズム
• 計算の途中では，d(i) の値が s から i への真の最
短路の長さに等しいことがわかっている節点が存
在する．そのような節点の集合を S で表す
• S は S の補集合 V  S を表す
17
ダイクストラ (Dijkstra) 法
(0) S := , S := V, d(s) := 0, d(i) :=  (i  V  {s})
とおく
(1) S = V なら計算終了．そうでないなら，
d (v)  min d (i) | i  S  である節点 v  S を選ぶ
(2) S : S  {v}, S : S  {v} とし，(v,j) E かつ j  S
であるような全ての枝 (v,j) に対して
d(j) > d(v) + avj ならば d(j) = d(v) + avj, p(j) := v
とする．ステップ (1) に戻る
p(i) は，s から i までの最短路において i の直前に
18
位置する節点を示すために用いられる
[初期化]
(0) S   , S  {1,2,3,4,5}
50
1
d(1)=0
d(2)=
2
20
80
d(4)=
4
15
30
10
3
d(3)=
d(5)=
5
15
19
[反復1]
(1) S  {1,2,3,4,5}
min d (i) | i  S   0 より v = 1
(2) S  {1}, S  {2,3,4,5}
d(2) =  > d(1) + a12 =50 より d(2) = 50, p(2) = 1
d(3) =  > d(1) + a13 =80 より d(3) = 80, p(3) = 1
50
1
d(1)=0
d(2)=50
2
20
d(4)=
4
15
30
10
5
80
3
d(3)=80
d(5)=
15
20
[反復2]
(1) S  {2,3,4,5}
min d (i) | i  S   50 より v = 2
(2) S  {1,2}, S  {3,4,5}
d(3) = 80 > d(2) + a23 =70 より d(3) = 70, p(3) = 2
d(4) =  > d(2) + a24 =65 より d(4) = 65, p(4) = 2
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=
15
21
[反復3]
(1) S  {3,4,5}
min d (i) | i  S   65 より v = 4
(2) S  {1,2,4}, S  {3,5}
d(5) =  > d(4) + a45 =95 より d(5) = 95, p(5) = 4
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=95
15
22
[反復4]
(1) S  {3,5}
min d (i) | i  S   70 より v = 3
(2) S  {1,2,3,4}, S  {5}
d(5) = 95 > d(3) + a35 =85 より d(5) = 85, p(5) = 3
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
23
[反復5]
(1) S  {5}
自動的に v = 5
(2) S  {1,2,3,4,5}, S  
[反復6]
(1) S = V なので終了
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
24
• アルゴリズムが終了したときの d(i) は，節点 1 から
i への最短路の長さを与えている
• 枝の集合 {(p(i),i)} が各節点への最短路を表す
これを最短路木と呼ぶ
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
25
アルゴリズムの正当性の証明
• ダイクストラ法で，S は出発点 s からの最短路の
長さがわかっている節点の集合であることを確認
• 以下のことを帰納法で示す
– 全ての i に対し, d(i) = [S に含まれる節点のみを経由
して s から i に至る最短路の長さ]
(3.3)
(S に含まれる節点のみを経由するのでは到達できな
い場合は d(i) = )
– i  S ならば，d(i) = [s から i への最短路の長さ]
26
• [反復1] 終了後 S = {s}, d(s) = 0
• S の点 s では，s から s への最短距離は 0 で，d(s)
と等しい
• Sの点から1本の枝で到達できる S の点(2 と 3)では
d(i) = [S に含まれる節点のみを経由して s から i
に至る最短路の長さ] が成り立つ
• それ以外の点では d(i) =  で，命題は成立
50
1
d(1)=0
d(2)=50
2
20
d(4)=
4
15
30
10
5
80
3
d(3)=80
d(5)=
15
27
• 帰納法の仮定：ある反復に入った時点で命題成立
• ステップ(1)で v  S が選ばれたときに，v に対し
d(v) = [S に含まれる節点のみを経由して s から v に至る
最短路の長さ]
= [s から v への最短路の長さ]
(3.4)
それ以外の点に対して (3.3) が成り立つことを示す
• (3.4) を背理法で示す．sから v への最短路をP*とし，
その長さが d(v) と異なるとする
• アルゴリズムの構成法より，各節点 i に対し，d(i)
は s から i へのある路の長さを表しているので，
上の仮定は d(v) > [路 P* の長さ] を意味する
28
• v  S なので，(3.3) より，s から v への真の最短路
P* は，途中で S の点を少なくとも1つ経由する
• P* において初めて現れる S の点を u とすると，P*
*
*
は P1 と P2 に分解できる
• 最適性の原理より， P1* は s から u への最短路
• P1* は S の点のみを経由しているので，(3.3) より
*
d(u) = [路 P1 の長さ] が言える
S
S
p(v)
v
P2*
s
u
P1*
29
• 各枝の長さは非負なので，
*
[路 P* の長さ]  [路 P1 の長さ]
• よって，d(v) > d(u)
• ところが，d (v)  min d (i) | i  S  と u  S より
d(v)  d(u) となり，矛盾
• よって，d(v)は s から v への最短路の長さに等しい
• (3.3) より，その路は S の節点のみを経由するので，
S
S
(3.4) が成り立つ
p(v)
v
P2*
s
u
P1*
30
•
•
•
反復が終了した時点で (3.3) が保たれていること
を示す
反復終了時の S を S   S  {v} と書く
アルゴリズムのステップ(2) を実行したとき
+ に含まれる節点のみを経由して
[S
j  S  d ( j) 
s から j に至る最短路の長さ]

•
を示す
S+ に含まれる節点のみを経由して s から j に至
る最短路は次の3つの場合が考えられる
(a) v を経由しない，つまり S の節点のみを経由
(b) j に到達する直前に v を経由
(c) v を経由し，その後さらに S の節点をいくつか通って
31
j に到達
• (c) はありえない．なぜなら，そのような路が最短路
の場合，j の直前の節点を k とすると，最適性の原
理より，その路の k までの部分は sから kの最短路
• k はそれ以前の反復で S に入っているので，S の
節点のみを経由する s から k への最短路が存在
するはず
• よって，s から j への最短路は(a) か (b) のどちらか
• ステップ(2)で，d(j) > d(v) + avj ならば d(j) を
d(v) + avj で置き換えるが，これは (a) よりも(b)の方
が路が短いときに最短路を置き換えることに対応
• 以上より
+ に含まれる節点のみを経由して

[S
j  S  d ( j) 
32
s から j に至る最短路の長さ]
• 次の反復に入ったときも命題が成り立つことが示さ
れた
• 各反復が終了するたびに， S のどれか1つの節点
が S に入るので，アルゴリズムの反復の回数は
節点数 n に等しい
• ステップ(1) の計算量は各反復で O(log n)，
全体で O(n log n)
• ステップ(2) では，ネットワークの各枝はアルゴリズ
ムを通して高々1回だけ処理されるのでステップ(2)
の計算量は全体で O(m log n) (m: 枝数)
• 以上より，ダイクストラ法の計算量は O(m log n)
33
• d の更新を挿入と削除ではなく，フィボナッチヒープ
のdecrease_keyで行うと，総計算量は
O(m + n log n)
34

Download Report