V - Researchmap

算法数理工学
第7回
定兼邦彦
1
スタックとキュー
• 動的集合，挿入と削除をサポートする
• スタック (stack) では，DELETEでは最後に挿
入された要素が取り除かれる
– 後入れ先出し (last-in, first-out; LIFO) という
• キュー (queue) では，最初に挿入された要素
が取り除かれる
– 先入れ先出し (first-in, first-out; FIFO) という
2
スタック (Stack)
• INSERT, DELETEの代わりにPUSH, POPと呼ぶ
– PUSH(S,x): 集合 S に要素 x を加える．
– POP(S): S から最後に PUSH された要素を削除し，
その要素を返す
PUSH(S,15)
POP(S) 15
692
9
2
6
15
3
配列によるスタックの実装
• 最大 MAX 要素を格納できるスタックを実装
• スタックを表す構造体
– top: 最後に挿入された要素の格納場所(= 要素数)
– S: 要素を格納するサイズMAXの配列(へのポインタ)
– MAX: 配列 S のサイズ
typedef int data;
• 要素は S[1..top] に格納される
– S[1]: スタックの底
– S[top]: スタックの最上部
– top  MAX
typedef struct {
int top;
int MAX;
data *S;
4
} stack;
実装例
• PUSH(S,x)
– topを1増やし，x を配
列に入れる
– topがMAXを超えたら
エラー
– O(1) 時間
void PUSH(stack *s,data x)
{
if (s->top == s->MAX) {
printf("オーバーフロー\n");
exit(1);
}
s->top = s->top + 1;
s->S[s->top] = x;
}
• POP(S)
– スタックが空ならエラー
– サイズを1減らし，最上部
の要素を返す
– O(1) 時間
data POP(stack *s)
{
if (STACK_EMPTY(s)) {
printf("アンダーフロー\n");
exit(1);
}
s->top = s->top - 1;
return s->S[s->top + 1];
5
}
その他の関数
• STACK_EMPTY(S)
– スタックが空なら1を返す
– O(1) 時間
int STACK_EMPTY(stack *S)
{
if (S->top == 0) return 1;
else return 0;
}
• MAKE_STACK(size)
– 最大サイズ size のスタッ
クを作成する
stack *MAKE_STACK(int size)
{
stack *s;
data *S;
s = malloc(sizeof(stack));
S = malloc((size+1)*sizeof(data));
s->top = 0;
s->MAX = size;
s->S = S;
return s;
}
6
キュー (Queue)
• INSERT, DELETEの代わりにENQUEUE,
DEQUEUEと呼ぶ
• 人の並んだ列と同じ
– ENQUEUEでは列の最後に追加
– DEQUEUEでは列の先頭を取り出す
DEQUEUE(Q)
Q
15
6
2
ENQUEUE(Q,x)
9
7
配列によるキューの実装
• 最大 MAX1 要素を格納できるキュー
typedef struct {
• キューを表す構造体
–
–
–
–
int head;
int tail;
int MAX;
data *Q;
} queue;
Q: 要素を格納する配列
MAX: 配列 Q のサイズ
head: キューの先頭の位置
tail: 次に追加される位置
1
2
3
4
5
6
7
8
15 6
head
9 10 11 12
9
8
4
tail
8
環状バッファ (Ring Buffer)
• 配列 Q の右端と左端はつながって輪になっている
と考える
• Q[MAX] の右は Q[1] だとみなす
• 要素は Q[head..MAX] Q[1..tail1] に格納される
• DEQUEUEの際に全要素を左にずらす必要がない
1
2
3
5
3
4
5
6
7
8
15 6
tail
head
9 10 11 12
9
8
4 17
9
空のキューの作成
• MAKE_QUEUE(size)
– size 個の要素を格納できる空のキューを作成
queue *MAKE_QUEUE(int size)
{
queue *q;
data *Q;
size = size+1;
q = (queue *)malloc(sizeof(queue));
Q = (data *)malloc((size+1)*sizeof(data));
q->head = 1;
q->tail = 1;
q->MAX = size;
q->Q = Q;
return q;
}
10
配列を用いたスタック，キューの問題点
• 最大要素数を初めに決める必要がある
• 任意の数を格納できるようにするには？
1. 配列がいっぱいになったら，より大きい配列を用意する
•
•
p = realloc(p, (新しいサイズ));
p のアドレスは変わることがあるので注意
2. 配列の代わりにリストを用いる
•
•
キューではリストの末尾に追加する
スタックではリストの先頭に追加する
深さ優先探索，幅優先探索
• 木やグラフの探索法
• 深さ優先探索 (depth-first search, DFS)
– 行き止まりになるまで先に進む
• 幅優先探索 (breadth-first search, BFS)
– 全体を同時に探索する
• DFSはスタック(再帰)，BFSはキューで実現でき
1
1
る
2
3
2
5
4
DFS
6
4
3
5
BFS
6
最短路問題とダイクストラ法
• 有向グラフ G = (V, E) を考える
– V: 節点集合, 節点数 n
– E: 枝集合, 枝数 m
• グラフ G の各枝 (i,j)  E は長さ aij を持つ
• ある節点 s  V から別の節点 t  V への路の中で，
最も長さの短いものを見つける問題を最短路問題という
15
2
50
4
30
20
10
1
5
80
3
15
13
• 下のネットワークで節点 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
14
重み無しグラフの場合
• 重み無し ⇔ 全ての枝の重みが 1
• 幅優先探索で求まる
– O(n+m) 時間
• s からの距離が d の点の集合を Vd とする (d  0)
– V0 = {s}
– Vd = (Vd 1の点から枝1本で行ける点の集合)
 (V0, V1, …, Vd 1 に入っている点の集合)
• Vd を求めるには， Vd1 の各点 v に対し，v の隣接
点でまだ訪れていない点を求めればいい
• Vd をキューで管理する
15
• 各頂点に色を付ける
– 白: 未発見
– 灰: 発見済みだが隣接リストの探索が未完了
– 黒:発見済みで隣接リストの探索も完了
• 初期状態: s 以外の全ての点 u に対し
– color[u] = 白
– d[u] =  (s からの距離)
– [u] = NIL (最短路木での親)
• 始点 s については
– color[s] = 灰
– d[s] = 0
– [s] = NIL (最短路木での根)
16
BFS(G, s)
1. Q   (空集合)
2. ENQUEUE(Q, s)
3. while Q  
4.
u  DEQUEUE(Q)
5.
for each v  Adj[u]
6.
if color[v] = 白
7.
color[v] = 灰
8.
d[v]  d[u] + 1
9.
[v]  u
10.
ENQUEUE(Q, v)
11.
color[u]  黒
17
計算時間の解析
• 初期化以外で色が白になる点は無い
• ある点がキューに入れられるとき，その色は白で，
キューに入ると灰になる
⇒各点は高々1回だけキューに挿入・削除される
• 各点 u の隣接リストが走査されるのは u がキュー
から削除されるときのみ
⇒各点の隣接リストは高々1回だけ走査される
⇒隣接リストの走査にかかる時間は全体で O(m)
• 初期化の時間は O(n)
• 全体で O(n+m)
18
正当性の証明
• 定義： s から v への最短路距離 (shortest-path
distance) (s, v) を，s から v へのパスの辺数の最
小値と定義する．パスが無ければ (s, v) = .
• 補題1：有向または無向グラフ G において，
任意の辺 (u, v)  E に対し，
(s, v)  (s, u) + 1
• 証明： u が s から到達可能ならば v へも到達可能
で，s から v へのパスは s から u への最短路に
(u, v) を追加したものか，それより短いものとなる．
u が s から到達不可能ならば (s, u) =  なので
不等式は成立する．
19
• 補題2：BFSが停止した時，各点 v  V に対し
d[v]  (s, v) が成立する．
• 証明： ENQUEUEの操作回数に関する帰納法で
証明する．最初の s だけが挿入された段階では
d[s] = 0 = (s, s), 全ての点 v  V{s} に対し
d[v] =   (s, v) なので成立．
• 点 u の隣接点 v を探索する場合を考える．
帰納法の仮定により d[u]  (s, u)．
d[v] を更新すると
d[v] = d[u] + 1
 (s, u) + 1
 (s, v) (補題1より)
20
となり，ENQUEUE後も成り立つ
• 補題3: BFSの実行中で，キュー Q が点 v1, v2, …,
vr を含むとする (v1が先頭， vrが末尾)．
このとき d[vr]  d[v1]+1 かつ
d[vi]  d[vi+1] (i=1,2,…,r1)
• 証明: キューの操作回数に関する帰納法を用いる.
初期段階はキューは s だけを含むので成り立つ．
• キューの先頭 v1 を削除すると v2 が新たな先頭に
なる．帰納法の仮定より d[v1]  d[v2].
このとき d[vr]  d[v1]+1  d[v2]+1 となり成立．
• キューに頂点 v を挿入するとき (vr+1 = v となる)
現在頂点 u の隣接リストを走査しているとする．
21
• d[vr+1] = d[v] = d[u]+1(アルゴリズムの動作)
• u を削除する前のキューはu = v1, v2, …, vrなので
帰納法の仮定から d[vr]  d[u]+1．
• 従って d[vr]  d[u]+1 = d[v] = d[vr+1]．
また， d[vr+1] = d[u]+1 = d[v1]+1．
• よって，u を削除後のキューでも d[vr+1]  d[v1]+1．
• 定理: アルゴリズムBFSは始点 s から到達可能な
全ての頂点 v  V を発見し，停止した時全ての v
に対して d[v] = (s, v) が成立する．さらに，s から
到達可能な全ての v  s に対し，s から v への最短
路の1つは，s から [v] への最短路の後に辺
([v], v) を連接したものである．
22
• 証明：背理法で示す．最短路長に等しくない d 値
を受け取る頂点が存在すると仮定する．v を，そ
のような頂点の中で (s, v) が最小の頂点とする．
• 補題2より d[v]  (s, v) なので， d[v] > (s, v)．
• v が s から到達不可能ならば (s, v) =  なので
d[v] は正しい値 ()．よって v は到達可能．
• u を s から v への最短路上の点で v の直前のも
のとすると (s, v) = (s, u) + 1 である．
• (s, u) < (s, v) であり，仮定より最短路長が
(s, v) より短い場合は d[u] = (s, u) なので
d[v] > (s, v) = (s, u) + 1 = d[u] + 1 …(1)
23
• キューから u を削除する場合を考える．
v の色は白，灰，黒のいずれかである．
• v が白の時
– d[v] = d[u] + 1 を実行するので式 (1) に矛盾．
• v が黒の時
– v は既にキューから削除されている
– d[v]  d[u] なので式 (1) に矛盾．
• v が灰の時
–
–
–
–
ある点 w を削除した時に v は灰に彩色された
d[v] = d[w]+1
w は u よりも先にキューから削除されたので d[w]d[u]
よって d[v]  d[u]+1 となり式 (1) に矛盾．
24
• 以上より，全ての点 v に対して d[v] = (s, v)．
• [v] = u ならば d[v] = d[u] + 1 が成り立つ．よって
辺 ([v], v) を連接すると最短路が求まる．
• グラフ G = (V, E) を次のように定義する
– V = {v  V | [v]  NIL}  {s}
– E = {([v], v)  E | v  V  {s}}
• V は s から到達可能な全頂点
• 全ての v  V に対し，s から v に至る唯一のパス
が G に存在し，これが G における s から v への
最短路になっている
• G は幅優先探索木(breadth-first tree)と呼ばれる
25
最適性の原理
• 節点 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 をつないだ路は P より短くなる
• このような性質を最適性の原理と呼ぶ
P1
P
r
2
s
P1’
t
26
• ある節点 s からネットワークの他の全節点への最
短路を求める問題を考える
• ダイクストラ法は，枝の長さに関する非負条件
aij  0 ((i,j)  E) の仮定の下で，節点 s から各節
点 i  V への最短路の長さの上限値 d(i) を更新し
ていく反復アルゴリズム
• 計算の途中では，d(i) の値が s から i への真の最
短路の長さに等しいことがわかっている節点が存
在する．そのような節点の集合を S で表す
• S は S の補集合 V  S を表す
27
ダイクストラ (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 の直前に
位置する節点を示すために用いられる
28
[初期化]
(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
29
[反復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
30
[反復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
31
[反復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
32
[反復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
33
[反復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
34
• アルゴリズムが終了したときの 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
35
アルゴリズムの正当性の証明
• ダイクストラ法で，S は出発点 s からの最短路の
長さがわかっている節点の集合であることを確認
• 以下のことを帰納法で示す
– 全ての i に対し, d(i) = [S に含まれる節点のみを経由
して s から i に至る最短路の長さ]
(3.3)
(S に含まれる節点のみを経由するのでは到達できな
い場合は d(i) = )
– i  S ならば，d(i) = [s から i への最短路の長さ]
36
• [反復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
37
• 帰納法の仮定：ある反復に入った時点で命題成立
• ステップ(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* の長さ] を意味する
38
• 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*
39
• 各枝の長さは非負なので，
*
[路 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*
40
•
•
•
反復が終了した時点で (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 の節点をいくつか通って
41
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) 
42
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)
43
• 注：上のアルゴリズムを実行するには，ヒープから
の削除を実現する必要がある．
– サイズ n の配列を用いて，v の格納されているヒープの
場所を管理する
• d の更新を挿入と削除ではなく，フィボナッチヒープ
のdecrease_keyで行うと，総計算量は
O(m + n log n)
44
選択問題 (selection problem)
• 入力: n 個の異なる数の集合 A, 整数 i (1  i  n)
• 出力: A 中のちょうど i 1 個の他の要素より大きい
要素 x  A
• 選択問題は O(n lg n) 時間で解ける
– A の要素をソートする
– 出力配列の i 番目の要素を返す
• 選択問題は O(n) 時間で解ける
45
最悪線形時間の
選択アルゴリズム
アルゴリズム SELECT: i 番目に小さい要素を返す
1. 入力配列の n 要素をグループに分割
–
–
5要素のグループ n/5 個
n mod 5 要素のグループ高々1個
2. n/5 個の各グループを(挿入ソート等で)ソートし
，それぞれの中央値を求める
3. SELECTを再帰的に用いてステップ2で求めた
n/5 個の値の中央値 x を求める
46
4. PARTITIONを修正したものを用い，入力配列を
x によって分割する．左側の要素数を k とする.
5. i  k ならば，左側で i 番目に小さい要素を再帰
的に見つける．
i  k ならば，右側で ik 番目に小さい要素を再帰
的に見つける．
47
SELECTの実行時間の解析
• 分割に用いた x より大きい要素数の下界を求める
• ステップ 2 で求めた中央値の少なくとも半分は x (
中央値の中央値) 以上
• 中央値が x 以上のグループには，x 以上の値が 3
個以上ある
• x 以上となる要素数は少なくとも
  1  n    3n
3      2  
6
  2  5    10
48
• 同様に，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のとき
49
• 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の最悪実行時間は線形
• これは比較しか用いていない
50

Download Report