スライド 1

エージェントを管理するボスの苦悩
問題
n人のエージェントを部下に持つボスがいる．
エージェントは出張・帰還を頻繁に繰り返す．
手元に残っている部下の管理をどうする？
手元に残っている部下を配列に保存
0
1
2
3
4
5
6
7
8
9 10
Gi Je Bu
Gu Re
Za Gu
Gu
Do Za
Za
Ki Do
Do
Ve Ki
Ki
Na Ve
Ve
Ra Na
Na
Re Ra
Ra
Re 出張 Bu 帰還 Za 出張 Ve 出張 Gi 出張 Do 帰還
Bu 出張 Gu 出張 Je 出張 Ki 帰還 Na 出張 Ra 出張
Re 帰還 Gu 帰還 Ki 出張 Do 出張 Za 帰還 Gi 帰還
配列でエージェントを管理する利点・欠点
i番目のエージェントの発見
エージェントの発見 O(n)
O(1)
エージェントの削除 O(n)
エージェントの挿入 O(n)
手元に残っている部下を配列に保存
0
1
2
3
4
5
6
7
8
9 10
Gi Je Bu
Gu Re
Za Gu
Gu
Do Za
Za
Ki Do
Do
Ve Ki
Ki
Na Ve
Ve
Ra Na
Na
Re Ra
Ra
リンクリスト（Linked List）でエージェントを管理
0
配列で管理
1
2
3
4
5
6
7
8
9 10
Gi Je Bu
Gu Re
Za Gu
Gu
Do Za
Za
Ki Do
Do
Ve Ki
Ki
Na Ve
Ve
Ra Na
Na
Re Ra
Ra
Linked Listで管理
スタート
Re
Za
Bu
Gi
Re 出張
Bu 出張
Re 帰還
Je
Gu
Re
Do
Ve
Ki
Na
Ra
Linked Listでエージェントを管理する利点・欠点
エージェントの削除 O(1)
エージェントの発見 O(n)
エージェントの挿入 O(1)
i番目のエージェントの発見
O(n)
Linked Listで管理
スタート
Za
Bu
Gi
Je
Gu
Re
Do
Ve
Ki
Na
Ra
配列によるLinked Listの実装
配列による実装
name 配列
next 配列
スタート = 20
再利用 = -132
0
4
1
Bu 出張
Re 帰還
5
6
7
8
9 10
Gi Je Re
Gu Re
Bu
Za Gu
Gu
Do Za
Za
Ki Do
Do
Ve Ki
Ki
Na Ve
Ve
Ra Na
Na
Re Ra
Ra
1
42 Gu034 -1
Za4 Za
Gu
Do5 Do
Ki6 Ki
Ve7 Ve
Na8 Na
Ra9 10
Re -1
Ra
Za
Bu
Re
Re 出張
3
再利用
スタート
Gi
2
Je
Gu
Re
Linked Listのイメージ
Do
Ve
Ki
-1
Na
Ra
スパゲッティーソート
①スパゲッティをn本用意します．
②それぞれをxiの長さに切ります．
③テーブルの上にまとめて立てます．
④上から手を下ろし，
最初にさわったものを引き抜きます．
⑤それを繰り返します．
⑥最後に，逆に並べます．
手間：①O(n)，②O(n)，③O(1)，
④＋⑤O(n) ，⑥O(n)
Carpenter's algorithm（大工の方法）
エージェントを管理するボスの苦悩
Gi
100000
Re
70000
Je
60000
Bu
60000
Gu
30000
Za
23000
Do
22000
Ki
18000
Ve
18000
Na
5000
Ra
1500
漠然とした問題
n人のエージェントを部下に持つボスがいる．
エージェントは出張・帰還を頻繁に繰り返す．
手元に残っている部下の管理をどうする？
ただし，能力値の高いものを優先的に出張させたい．
対策: データを配列に保存し並べ替えを利用
データ初期化（並べ替え）→ O(n log n)
出張命令（最適発見・削除） → O(1)
帰還（順番を保ちつつ挿入）→ O(n)
もっとうまい手はないか？
並べ替えはやりすぎな気がする．
その時点での最優先要素がわかればよい
優先キュー（Priority Queue）という道具
Gi
100000
Re
70000
Je
60000
Bu
60000
Gu
30000
Za
23000
Do
22000
Ki
18000
Ve
18000
Na
5000
Ra
1500
対策: 高々n個のデータを配列に保存し並べ替
えを利用
データ初期化（並べ替え）→ O(n log n)
出張命令（最適発見・削除） → O(1)
帰還（順番を保ちつつ挿入）→ O(n)
対策: 高々n個のデータを優先キューに保存
データ構造初期化 → O(n log n)（→ O(n)）
出張命令（最適発見・削除） → O(log n)
帰還（優先キューの構造を保ちつつ挿入）→ O(log n)
ヒープ（Heap）による優先キューの実現: 定義
定義【（バイナリ）ヒープ】
・根付き木
・各頂点が要素に対応
・各頂点にはキー値が付属
・各頂点には高々2個の子要素
・親の優先順位は子以上
Gi
1000
Re
700
Bu
600
→ 根の優先順位が最高となる
Je
600
Gu
300
Ve
180
Za
230
Ki
180
Ra
15
Na
50
Do
220
根付き木が深くならないように
気をつける
→ 上左からつめて入れる
最大要素数nのとき
木の深さは高々log2n → O(log n)
ヒープによる優先キューの実現: 取り出し操作pop
Gi
1000
pop()
根にある要素を取り出す．
ヒープの再下右要素を根に移動する．
ShiftDown(根の要素)により木を整形する．
Re
700
Bu
600
Je
600
Gu
300
Ve
180
Za
230
Ki
180
Ra
15
popの計算量はO(log n)である．
Na
50
ShiftDown(x)
Do if xの優先度 > xの子の優先度:
優先度の高い子とxの位置を入れ替える
220
ShiftDown(x)
ヒープによる優先キューの実現: 要素の追加push
Re
700
push(x)
新しい要素xをヒープの最下右に追加する．
ShiftUp(x)によりヒープを整形する．
Bu
600
Do
220
pushの計算量はO(log n)である．
ShiftUp(x)
Je
600
Gu
300
Ve
180
Za
230
Ki
180
Ra
15
Na
50
Gi
1000
if xの優先度 > xの親の優先度:
xの親とxの位置を入れ替える．
ShiftUp(x)
要素数がn個のヒープの構築は
ヒープが空の状態から
要素を1つ1つpushすればよいので
O(n log n)で完了する．
バケット法（Bucket method）の一例
<- 120000
Gi 123383
Je
56264
Bu
52384
Re
59794
Za
23358
Do
22265
Ki
18159
Ve
18159
Na
5310
バケツ0番～バケツN番を用意
（Nは十分大きい数）
キー値がiの要素をバケツi番に入れる
バケツ
52383
バケツ
52385
バケツ
52384
バケツ
52383
バケツ
52383
<- 100000
<- 70000
<- 50000
<- 30000
<- 20000
<- 10000
<- 0
ハッシュ法（Hashing）の一例
Gi 123383 (1+2+3+3+8+3) mod 9 = 2
8
Je
56264 (5+6+2+6+4) mod 9 = 5
7
Bu
52384 (5+2+3+8+4) mod 9 = 4
6
Re
59794 (5+9+7+9+4) mod 9 = 7
5
Za
23358 (2+3+3+5+8) mod 9 = 3
4
Do
22265 (2+2+2+6+5) mod 9 = 8
Ki
18159 (1+8+1+5+9) mod 9 = 6
Ve
18159 (1+8+1+5+9) mod 9 = 6
Na
5310 (5+3+1+0) mod 9 = 0
各桁の数字を足して9で割った余りを計算
ハッシュ関数（Hash function）
3
2
1
0
ハッシュテーブル
(Hash table)

Download Report