データ構造とアルゴリズムⅠ 予定 (II) データ構造集合を扱うデータ構造

予定 (II)
12/3: 小テスト
12/10: 第8回：線形時間ソーティング
12/17:第9回：基本データ構造
12/24:第10回：ハッシュ表
1/7:小テスト
1/14: 金曜日の講義日
1/21:第11回：2分探索木
1/28: 補講日
2/4: 定期試験
データ構造と
アルゴリズムⅠ
第9回
338
集合を扱うデータ構造
データ構造
• データをどのような形式で格納し，どのように
利用するかを与える
• 現実のプログラミングでは，アルゴリズムの
選択よりもデータ構造の選択が重要であるこ
とが多い
•
•
•
•
集合：数学，計算機科学において基本的
動的集合：要素が追加/削除/変更される
集合に対して行う操作によってデータ構造を変える
行いたい操作によって最適なデータ構造が決まる
⇒ データ構造が決まれば用いるべきアルゴリズム
も決まる
339
行う操作
データ構造
挿入，削除，
存在判定
挿入
最小要素の取出し
辞書
プライオリティー
キュー
340
動的集合に関する操作
動的集合の基本
1. 集合に関する情報を返す質問 (query)
•
• 各要素はオブジェクトとして表現される
• オブジェクトはキーと付属データからなる
• 集合の操作で扱うフィールドがあってもよい
•
– 他のオブジェクトへのポインタなど
•
• キーは全順序を持つとする場合もある
•
•
341
SEARCH(k): key[x] = k である S の要素 x へのポイ
ンタを返す．存在しなければ NIL．
MINIMUM(): 全順序集合 T において，最小のキーを
持つ要素を返す
MAXIMUM(): 全順序集合 T において，最大のキーを
持つ要素を返す
SUCCESSOR(x):全順序集合 T においてキーが x
のキーの次に大きな要素を返す．x が最大なら NIL.
PREDECESSOR(x): キーが x のキーの次に小さな
342
要素を返す．x が最小なら NIL.
1
動的集合に関する操作
10.1 スタックとキュー
2. 集合を変える修正操作 (modifying operation)
•
•
•
•
INSERT(x): 集合 S に要素 x を加える．
DELETE(x): x へのポインタが与えられたとき，S
から x を取り除く．
SUCCESSOR，PREDECESSORは同じキー
が複数ある集合にも拡張される
集合操作を実行するのにかかる時間は集合の
サイズで測る
• 動的集合，挿入と削除をサポートする
• スタック (stack) では，DELETEでは最後に
挿入された要素が取り除かれる
– 後入れ先出し (last-in, first-out; LIFO) という
• キュー (queue) では，最初に挿入された要素
が取り除かれる
– 先入れ先出し (first-in, first-out; FIFO) という
343
配列によるスタックの実装
スタック (Stack)
• INSERT, DELETEの代わりにPUSH, POPと
呼ぶ
– PUSH(x): スタックに要素 x を加える．
– POP(): スタックから最後に PUSH された要素を
削除し，その要素を返す
PUSH(6)
PUSH(9)
PUSH(15)
PUSH(2)
POP()
15
692
– top: 最後に挿入された要素の格納場所(= 要素数)
– S: 要素を格納するサイズMAXの配列(へのポインタ)
• 要素は S[1..top] に格納される class STACK {
void PUSH(data x)
{
if (top == MAX) {
cout << "オーバーフロー";
exit(1);
}
top = top + 1;
S[top] = x;
}
public:
int top;
int MAX
data *S;
};
345
実装例
– topを1増やし，x を配
列に入れる
– topがMAXを超えたら
エラー
– O(1) 時間
• 最大 MAX 要素を格納できるスタックを実装
• スタックを表すオブジェクト
– S[1]: スタックの底
– S[top]: スタックの最上部
– top  MAX
9
2
6
15
• PUSH(x)
344
• POP()
– スタックが空ならエラー
– サイズを1減らし，最上部
の要素を返す
– O(1) 時間
data POP()
{
if (STACK_EMPTY()) {
cout << "アンダーフロー";
exit(1);
}
top = top - 1;
return S[top + 1];
347
}
346
その他の関数
• STACK_EMPTY()
– スタックが空なら1を返す
– O(1) 時間
int STACK_EMPTY()
{
if (top == 0) return 1;
else return 0;
}
• 初期化
stack (int size) {
TOP=0;
MAX=size;
S = new data[size];}
348
2
課題
答え
• n要素の配列A[1,…,n]を用いて，二本のス
タックを実装したい
• 二つのスタックの要素の合計がnを超えない
限り，どちらもオーバフローしないようにする
にはどうしたらよいか?
• 一つのスタックは最初から詰めて，もう一つ
のスタックは後ろから逆に詰める
• topが同じになったらオーバーフロー
349
配列によるキューの実装
キュー (Queue)
• INSERT, DELETEの代わりにENQUEUE,
DEQUEUEと呼ぶ
• 人の並んだ列と同じ
– ENQUEUEでは列の最後に追加
– DEQUEUEでは列の先頭を取り出す
DEQUEUE()
Q
15
6
ENQUEUE(x)
2
350
• 最大 MAX1 要素を格納できるキュー
class QUEUE
• キューを表すオブジェクト
1
2
3
4
5
6
3
4
5
6
7
8
15 6
tail
head
9 10 11 12
9
8
9
8
4
tail
352
実装例
• 配列 Q の右端と左端はつながって輪になっている
と考える
• Q[MAX] の右は Q[1] だとみなす
• 要素は Q[head..MAX] Q[1..tail1] に格納される
• DEQUEUEの際に全要素を左にずらす必要がな
い
2
9 10 11 12
head
環状バッファ (Ring Buffer)
3
8
15 6
9
351
1
7
{
public:
int head;
int tail;
data *Q;
};
– Q: 要素を格納する配列
– head: キューの先頭の位置
– tail: 次に追加される位置
4 17
353
• ENQUEUE(x)
– x をQ[tail]に入れる
– tailを1増やす
– O(1) 時間
• DEQUEUE()
– Q[head]を取り出す
– headを1増やす
– O(1) 時間
void ENQUEUE(data x)
{
Q[tail] = x;
if (tail == MAX)
tail = 1;
else tail = tail + 1;
}
data DEQUEUE()
{
data x;
x = Q[head];
if (head == MAX)
head = 1;
else head = head + 1;
注: オーバーフロー, アンダーフロー return x;
}
処理は省略してある
354
3
10.4 根付き木の表現
2分木
• （二分）根付き木をオブジェクトを用いて表現する
• 各節点はフィールド p, left, right, keyを持つ
– p: 親へのポインタ，NILなら根
– left: 左の子へのポインタ，NILなら子を持たない
– right: 右の子へのポインタ，NILなら子を持たない
root(T)
• root(T): T の根を指す．NILなら木は空
p
root(T)
left right
355
356
左-子, 右-兄弟表現
k分木
(Left-Child Right-Sibling Representation)
• 子供を最大 k 個持つ木の表現
– left, rightの代わりに child1, child2,..., childk とする
– 子供の数が一定でないと記憶領域を無駄にする
– p(x): 親へのポインタ
– left-child(x): x の子で最も左にあるものへのポインタ
– right-sibling(x): x の右の兄弟へのポインタ
…
child1
child2
• k 分木を2分木で表現する方法
• 任意の n 節点の根付き木を O(n) 領域で表現可
能
childk
357
• x が子を持たないとき left-child(x) = NIL
• x がその親の右端の子のときright-sibling(x) =
358
NIL
セント・ペテルスブルグの逆説
root(T)
359
• 以下のようなクジを考える．
– コインを投げる．
– 表が出たら終わり．2円もらえる．
– 裏が出たらならもう一回コインを投げる．
– 表が出たら終わり，4円もらえる．
– 裏が出たならもう一回コインを投げる．
– 表が出たら終わり，8円もらえる．
– 以下繰り返し，k回目に初めて表が出たら 2k円
もらえる
• このクジに参加するのに，いくらまでなら払っても
360
良いか?
4
二分木で表すと?
セント・ペテルスブルグのパラドックス
1/2
1/4
2円
1/8
4円
…
8円 1/16
16円
1/2k
k
2円
• なぜ期待値が無限大のクジに，10円払うのも
いやなのか?
– リスクに対する態度：人間はリスクを避けたいと
思う --- 期待値が小さくても，確実な方を好む
• 一億円確実にもらえるのと，コインを投げて表なら二
億円，裏なら0円のクジの価値は同じ?
…
361
リスクに対する態度
– 金額が倍になっても，うれしさは倍にならない：二
万円は一万円の倍うれしいが，二兆円は一兆円
の倍ほどはうれしくない
– このクジは現実には成立し得ない（地球全体の
富の総額を超える賞金を約束している）
362
木探索アルゴリズム
• 自動車保険
– 保険に入らない場合：ほとんどの場合にコスト0, 非
常に低い確率pで，事故を起こして1億円払うという
クジを引く
– 保険に入る場合：確実に5万円損をする代わりに，
上のクジを引かなくてよい
– p×一億円 < 5万円
– 期待値だけを考えるなら，保険に入らない方が良い
– 通常，人はリスク回避的，しかし，保険に入る人が
宝くじを買うこともある (100円払って，期待利得が
50円未満のものを買う)
363
• ルート（根）ノードから，ある条件を満たすノー
ドへの経路を見つける
• 例：迷路の探索，宣教師と人喰い人種，8puzzle, カーナビの経路探索, VLSIのレイア
ウト, 移動ロボットの経路プランニング
3
2
1 8 4
7 6 5
1 2 3
4 5 6
7 8
364
幅優先探索
一般的な木探索アルゴリズム
• ルートノードがまず展開され，つぎにルートノードに
よって生成されたすべてのノードが展開され，そして
それらの後続ノードが展開される，というように続く．
• 一般に，探索木における深さdのすべてのノードが，
深さd+1のノードの前に展開される．
• 一般アルゴリズムで，OPENをキューを用いて実装
し，展開した子ノードをキューの最後に加える
OPENをルートノードのみからなるリストに設定
loop do
if OPEN が空のリスト
then return no-solution
else OPEN中の最初のノード n をOPENから取り除く
if nがゴールノード
then return ルートからnへの経路
else n を展開して，子ノードをすべて，
適当な基準でOPENに加える
end if
end if
end do
365
366
5
幅優先探索の性質
深さ優先探索
– 幅優先探索で得られる解は最適
• 木が無限でも，有限の距離の解があるなら完全
– どの状態もb個の新しい状態に展開されるものとする（分岐
度=b）．この問題に対する解が，経路長dを持つと仮定する．
– 最悪の場合，レベルdの最後のノードが解
– 展開されるノード数は， 1+b+b2+b3+…+bd=O(bd)
– b＝10，
1000ノード/秒
100バイト/ノード
とする．
8 10^8 31 時間
10 10^10 128 日
12 10^12 35 年
14 10^14 3500 年
11 ギガバイト
1 テラバイト
111 テラバイト
11,111 テラバイト
• 木の最も深いレベルのノードの一つをいつも
展開する．
• 探索が行き止まりになる（子ノードがない）と
きに限り，探索は後戻りし，より浅いレベルの
ノードを展開する．
• 一般アルゴリズムで，OPENをスタックを用い
て実装し，子ノードをスタックの先頭に加える
367
深さ優先探索
368
深さ優先探索の性質
• メモリの使用量が少ない
– ある部分木に関する探索が終了して初めて，
異なる部分木の探索を行う
• 最適解を得ることは保証できない
• 木が無限の場合，探索が終了しないことが
ある
• 木の深さが限定される場合に相性が良い
369
370
最良優先探索（近視眼的）
最良優先探索（A*探索）
• OPENを常にソートして，最良のものを優先し
て展開する
• 目的までの距離の推定値が最小のものを優先
• 推定値の求め方（迷路の場合）：障害物が存在
しないと仮定した場合の距離を求める
• この推定値は，必ず楽観的な値になっており，
真の値より小さい（か等しい）
• 最適解（最短距離のルート）を求めることは保
証できない
• OPENを常にソートして，最良のものを優先し
て展開する
• 最良のもの＝最短経路の候補となる可能性
が高いもの
• ルートからの距離＋目的までの距離の推定
値が小さいものを優先
• 推定値が楽観的な場合，最適解を得ることが
保証される
371
372
6
リストの種類
10. 2 連結リスト
リストの利点：
• 何個の要素が入るかあらかじめ予想できな
い場合でも使える
• 最悪の場合を予想して，大きめに領域を取っ
ておく必要がない
• 再帰的な構造をしているので，再帰的なプロ
グラムと相性が良い
• 一方向 (singly linked) と双方向 (doubly linked)
– 一方向のとき，各要素は prev を持たない
• 既ソート (sorted) と未ソート
– 既ソート: リストの線形順序はキーの線形順序に対応
– 未ソート: 任意の順序
• 循環 (circular list) と非循環
– 循環: リストの先頭要素の prev はリストの末尾を指し，
末尾の next はリストの先頭を指す
• 以下では未ソート双方向循環リストを扱う
373
連結リスト (Linked Lists)
• オブジェクトをある線形順序に並べて格納するデータ構造
• 連結リストでの線形順序は，オブジェクトが含むポインタで決定さ
れる
• 双方向連結リスト (doubly linked list) L の要素
– キーフィールド key
– ポインタフィールド prev, next
– (付属データ)
• リストの最初の要素はキーを持たない特別なオブジェクト（nil_obj）
NIL
374
双方向リストはnil_objを含めた循環リストで表現される
リストL は NIL というメンバ変数を持つ
NILはnil_objを指す
先頭要素は HEAD = NEXT(NIL)
next(x): リスト中の x の直後の要素のポインタ
– next(x) = nil_obj のとき，x は最後の要素
• prev(x): x の直前の要素のポインタ
– prev(x) = nil_obj のとき，x はリストの最初の要素
•
•
•
•
•
NIL
9
16
4
9
375
nil_obj
双方向リストの構造体
16
4
376
nil_obj
省略記法
• リストの要素
class lobj {
public
lobj *prev;
// 前の要素へのポインタ
lobj *next;
// 後の要素へのポインタ
data key; }; // キー
#define KEY(x) (x->key)
#define NEXT(x) (x->next)
#define PREV(x) (x->prev)
• 双方向リスト
class dlist {
public
lobj *NIL;
};
// nil_objへのポインタ
377
378
7
空リスト
連結リストからの削除
void LIST_DELETE(lobj *x)
{NEXT(PREV(x)) = NEXT(x);
PREV(NEXT(x)) = PREV(x);}
• 以下で表現される
NIL
NIL
nil_obj
9
16
4
nil_obj
379
連結リストの探索 (再帰バージョン)
連結リストへの挿入
• LIST_INSERT(x): x をリストの先頭に挿入
– x のキーは既にセットされているとする
void LIST_INSERT(lobj *x)
• O(1) 時間
{NEXT(x) = HEAD;
PREV(HEAD) = x;
x
HEAD = x;
PREV(x) = NIL;}
9
NIL
9
380
16
4
16
4
• R_LIST_SEARCH(k, i): リストに属する，要素i以
降でキー k を持つ最初の要素のポインタを返す
• R_LIST_SEARCH(k, HEAD) とすれば最初から
探索
NIL
381
lobj *R_LIST_SEARCH(data k, lobj* i)
{
if (i != NIL && KEY(i) != k)
return R_LIST_SEARCH(k, NEXT);
else return i;
}
9
16
4
382
最小値の探索 (再帰バージョン)
• R_MINIMUM(i): リストに属する，要素i以降の最小
値を返す
• R_MINIMUM(HEAD) とすれば全体の最小値を返
す
NIL
data R_MINIMUM(lobj* i)
{
if (NEXT(i) != NIL)
return KEY(i)とR_MINIMUM(NEXT(i))の最小値;
else return KEY(i);
}
9
16
4
383
8

Download Report