アルゴリズムとデータ構造
第11週 データ整列：ヒープソート法
2013年12月12日 金岡 晃
授業計画
1
第1週 (9/26)
データ構造とアルゴリズムの基 礎
第2週 (10/3)
アルゴリズムの効率、線形構造 第3週
(10/10)
スタックと待ち行列 第4週
(10/17)
文字列照合（KMP法、BM法）
第5週 (10/24)
木構造、木の走査
→文字列照合（BM法）、木構 造
第6週 (10/31)
木の走査、二分木、決定木 第7週
(11/14)
中間試験
第8週 (11/21)
休講 第9週
(11/28)
グラフ構造と最短路問題 第10週
(12/5)
解の探索：Aアルゴリズム 第11週
(12/12)
データ整列：ヒープソート 法
第12週 (12/19)
データ整列：クイックソー ト法
第13週 (1/9)
データ探索：ハッシュ法 第14週
(1/16)
データ探索：木構造探索法 1/22-2/8 期末試験
2013/12/12 アルゴリズムとデータ構造
【復習】第 10 週
解の探索： A アルゴリズム
アルゴリズムとデータ構造
アルゴリズムとデータ構造
系統的探索
• 恣意的あるいは偶然に頼るような方法ではなく、一定の規則的な方 針に従って探索する方法
2013/12/12 アルゴリズムとデータ構造
3
スタート
ゴール
分かれ道の選択を適当に行う？
→分かれ道のランダムな選択
右手をずっと壁につけたまま移動 する
→規則的な行動
状態空間モデル
アルゴリズムとデータ構造
モデリング
• 解くべき問題を、コンピュータで形式的に扱えるように 等価表現すること
状態空間モデル
• 探索過程の途中状態を頂点で表し、その遷移を辺で表したモデル
状態空間（State Space）：探索空間、解空間などとも
• 4つ組 Σ, 𝑆, 𝐺𝑆𝐸𝑇, 𝜏 で定義される
• 状態空間の解探索は最適化問題 Σ：状態の全体集合
𝑆 ∈ Σ ：初期状態
𝐺𝑆𝐸𝑇：目的状態の集合 = 𝐺1, 𝐺2, ⋯
𝜏: Σ → 2Σ：状態遷移オペレータ。1対多の写像。
基本アルゴリズム 1
2013/12/12 アルゴリズムとデータ構造
5
状態空間は木構造
目的状態を
みつけるだけで良い
基本アルゴリズム 1 の流れ
アルゴリズムとデータ構造
𝑆
𝐺 𝐴
𝐵
𝐶 𝐹
𝐸
𝐷 𝐻
𝐼
𝐽
分岐、行き止まり、スタート、ゴール を「状態」とする
モデル化
図式表現
𝑆 𝐴
𝐺
𝐵 𝐶
𝐹 𝐸
𝐷
𝐻
𝐼 𝐽
基本アルゴリズム 2
2013/12/12 アルゴリズムとデータ構造
7
状態空間は一般のグ ラフ（閉路を持つ）
目的状態を
みつけるだけで良い
演習 1
アルゴリズムとデータ構造
下記の条件があるときのアルゴリズムを、
基本アルゴリズム2を改良して作成せよ。
状態空間は一般のグラフ
（閉路を持つ）
目的状態を
みつけるだけでなく、
目標状態への道も
求められるようにする
ヒューリスティック関数
2013/12/12 アルゴリズムとデータ構造
9
𝑆 … 𝑛 … 𝐺
𝑔(𝑛) ℎ(𝑛)
𝑆から𝑛までの
最短距離 𝑛から𝐺までの 最短距離
𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛)
𝑛を通る𝑆から𝐺までの 最短距離
現時点で見つかって いる最良の近似値
経験的知識による 近似値
𝑔′(𝑛) ℎ′(𝑛)
ヒューリスティックス
ヒューリスティック関数
A アルゴリズム
アルゴリズムとデータ構造
ヒューリスティックを 用いたアルゴリズム
初期状態からの最小 コストを随時更新
ヒューリスティック を用いてなるべく早
く目標に接近する
演習 2
2013/12/12 アルゴリズムとデータ構造
11
𝑆
𝐴 𝐵
𝐶 G
状態空間のモデル 10
6
5 0
3 3 8
2
6
1 4
8
下記の状態空間に対してAアルゴリズムを適用した場合に得られる道を示せ。
またその導出過程も記載せよ。
なお、初期状態は𝑆、目標状態は𝐺𝑆𝐸𝑇 = {𝐺}とする。
第 11 週
データ整列：ヒープソート法
アルゴリズムとデータ構造
アルゴリズムとデータ構造
本日の到達目標と概要
• 到達目標
– データ整列法の概要とその 1 つであるヒープソート法の習得
• 概要
– データ整列法の分類 – 単純選択法
– ヒープソート法
13 2013/12/12 アルゴリズムとデータ構造
データの整列
アルゴリズムとデータ構造
アルファベット順や大小順など、データを順番にならべる
ソーティング
（Sorting）
整列法の分類（１）
2013/12/12 アルゴリズムとデータ構造
15
選択による方法
単純選択法、ヒープ整列法 選択：複数のデータの中から最大あるいは 最小のものを選ぶ動作
挿入による方法
単純挿入法（シャトル整列 法）、シェル法
挿入：すでに整列している複数のデータの 並びの適切な位置に、あらたな1枚を追加 挿入する操作
交換による方法
単純交換法（バブルソート 法）、クイックソート法
交換：注目した2枚の順番が逆になってい たら入れ替える動作
整列法の分類（２）
アルゴリズムとデータ構造
併合による方法
併合整列法（マージソート 法）、多ウェイ併合法
併合：整列している2つのデータの並びを 統合して1つにする操作
分配による方法
バケット整列法 分配：データの先頭を見て、グループに大 まかに仕分ける操作
単純選択法
2013/12/12 アルゴリズムとデータ構造
17
選択による方法
単純選択法、ヒープ整列法 選択：複数のデータの中から最大あるいは 最小のものを選ぶ動作
整列する対象の𝑛個のデータを𝑎 1 , ⋯ , 𝑎[𝑛]とする 単純選択法
入力データを全部調べて、最小のデータ𝑎 𝑝 の位置𝑝を知る。そして先頭𝑎 1 と𝑎 𝑝 を入れ替える。
この操作を、今度は先頭を除いた配列𝑎 2 , ⋯ , 𝑎[𝑛]に対して行う。
これを残りの配列が𝑎[𝑛]だけになるまで繰り返す
ヒープ整列法
アルゴリズムとデータ構造
1次元配列データ𝑎 1 , ⋯ , 𝑎[𝑛]は、二分木の物理構造とみなすことができる。
𝑖
2𝑖 2𝑖 + 1
第𝑖要素𝑎 𝑖 の左の子と右の子を、それぞれ
𝑎 2𝑖 , 𝑎 2𝑖 + 1 と考えれば、1次元配列と二分木との 間を一意に対応づけることができる。
1次元配列を二分木と見なして整列する方法 ヒープ整列法（Heapsort）
ヒープ：親子関係にある任意の2つの節において、子節の値が親節の 値を超えないような準完全二分木
ヒープでは最大のデータは根に保持される特徴を利用する
ヒープ整列法のアルゴリズム
2013/12/12 アルゴリズムとデータ構造
19
ふるい操作（シフト操作）
アルゴリズムとデータ構造
ヒープ整列法による処理過程（１）
2013/12/12 アルゴリズムとデータ構造
21
ヒープ整列法による処理過程（２）
アルゴリズムとデータ構造
演習
2013/12/12 アルゴリズムとデータ構造
23
下記の1次元配列を二分木で表したデータをヒープ整列法で処理したときの、処 理の過程を図示せよ
30
40 80
10 60 55
1
2 3
4 5 6
