アルゴリズムとデータ構造

アルゴリズムとデータ構造

第10週 解の探索：Aアルゴリズム

2013年11月28日 金岡 晃

授業計画

第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 期末試験

【復習】第 9 週

グラフ構造と最短路問題

アルゴリズムとデータ構造

本日の到達目標と概要

•

到達目標

–

グラフの基礎とそのデータ表現、また代表的な問題である最短 路問題を知る

•

概要

–

グラフの基礎

–

グラフのデータ表現

最短路問題

– Dijkstra

のアルゴリズム

グラフの定義

グラフ（Graph）

頂点（Vertex）の有限集合𝑉と辺（Edge, Arc）の有限集合𝐸によって定義され る。

𝐺 = 𝑉, 𝐸

頂点、辺はそれぞれ節（Node）、枝（Branch）とも呼ばれる。

グラフの図表現

：頂点

：辺

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝐺₁ = 𝑉₁, 𝐸₁ 𝑉₁ = 𝑎, 𝑏, 𝑐, 𝑑

𝐸₁ = 𝑎, 𝑏 , 𝑎, 𝑐 , 𝑏, 𝑐 , 𝑏, 𝑑 , 𝑐, 𝑑

𝐺₂ = 𝑉₂, 𝐸₂ 𝑉 = 𝑎, 𝑏, 𝑐, 𝑑 無向

グラフ𝐺₁

有向

演習

：グラフの描画

𝐾₆を描画せよ

演習

：部分グラフ

下のグラフに対し、 𝑉^′ = 𝑎, 𝑏, 𝑒 をつかった誘導グラフ を図示と集合の双方で示せ

𝑎 𝑏

𝑐 𝑑

𝑒

𝑓

𝑔 ℎ 𝑎 𝑏

𝑒 𝐺^′ = 𝑉^′, 𝐸^′ 𝑉^′ = 𝑎, 𝑏, 𝑒

𝐸^′ = 𝑎, 𝑏 , 𝑒, 𝑒

グラフの物理表現：順配置表現

𝐴₁ =

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

𝐴₂ =

0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 隣接行列（Adjacency Matrix）

行列𝐴の各行と各列を頂点に対応させ、行列の要素𝐴 𝑖, 𝑗 が、

無向グラフの場合 𝑖, 𝑗 ∈ 𝐸あるいは 𝑗, 𝑖 ∈ 𝐸ならば1、そうでないなら0と なっている行列。

有向グラフの場合 𝑖, 𝑗 ∈ 𝐸ならば1、そうでないなら0となっている行列。

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝑐 𝑑

無向 グラフ𝐺₁

有向 グラフ𝐺₂

隣接行列

隣接行列

グラフの物理表現：リンク配置表現（１）

直交リスト

𝐴₂ =

0 1 1 0

0 0 0 1

1 1 0 1

0 0 0 0

𝑎 𝑏

𝑐 𝑑

有向 グラフ𝐺₂

• 最も左の1列と最も上の1行 はそれぞれ始点、終点とし ての頂点を表したレコード

• それ以外のレコードは辺を 表す

グラフの物理表現：リンク配置表現（２）

隣接リスト

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝑐 𝑑

無向 グラフ𝐺₁

有向 グラフ𝐺₂

• 最も左のレコード群が頂点を表 し、その頂点が隣接する頂点を リストとして持っている

グラフのアルゴリズム：最短路問題

重み付グラフ（Weighted Graph）

辺に距離などのコストが付いたグラフ

𝑆 𝐷

𝐴 𝐵

𝐻 𝐼

𝐸 𝐽

𝐶 𝐹 𝐾 𝐺

4

3

1

1

2

2 2

1 1

2

3

1 3

𝑆 からスタートして 𝐺 に至る道で、

コストの総和が最小になる道を見 つけるにはどうしたらよいか

最短路問題

Dijkstra

のアルゴリズム

• 開始点からの集積コス トの増加が最も少ない 頂点を最優先する、と いう原則に従い、新た な頂点を1つずつ取り 込んでいく手法。

• グラフと始点とが与え られると、他の頂点ま での最短経路とコスト が求められる

Floyd

のアルゴリズム

• グラフが与えられると、

2頂点間の最短経路と コストが求められる

演習

下のグラフに対し、Floydのアルゴリズムを適用した場合、

最終的に出力される配列costの情報を示せ

𝑆 𝐷

𝐴 𝐵 𝐸

𝐶

4 3

1

1 2 2

𝑉 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝑆}

S A B C D E

S 0 3 ∞ ∞ 4 ∞

A 3 0 1 1 ∞ ∞

B ∞ 1 0 ∞ ∞ 2

C ∞ 1 ∞ 0 ∞ ∞

D 4 ∞ ∞ ∞ 0 2

E ∞ ∞ 2 ∞ 2 0

配列costの初期状態

演習

：解答

S A B C D E

S 0 3 4 4 4 6

A 3 0 1 1 5 3

B 4 1 0 2 4 2

C 4 1 2 0 6 4

D 4 5 4 6 0 2

E 6 3 2 4 2 0

配列costの最終状態

第 10 週

解の探索： A アルゴリズム

アルゴリズムとデータ構造

本日の到達目標と概要

•

到達目標

–

系統的探索と、その実現方法としての

アルゴリズムの理解

•

概要

–

系統的探索

–

状態空間のモデル化

基本アルゴリズム

–

ヒューリスティック関数

アルゴリズム

系統的探索

•

恣意的あるいは偶然に頼るような方法ではなく、一定の規則的な方 針に従って探索する方法

スタート

ゴール

分かれ道の選択を適当に行う？

→分かれ道のランダムな選択

右手をずっと壁につけたまま移動 する

→規則的な行動

状態空間モデル

モデリング

• 解くべき問題を、コンピュータで形式的に扱えるように 等価表現すること

状態空間モデル

• 探索過程の途中状態を頂点で表し、その遷移を辺で表したモデル

状態空間（State Space）：探索空間、解空間などとも

• 4つ組 Σ, 𝑆, 𝐺_𝑆𝐸𝑇, 𝜏 で定義される Σ：状態の全体集合

𝑆 ∈ Σ ：初期状態

𝐺_𝑆𝐸𝑇：目的状態の集合 = 𝐺₁, 𝐺₂, ⋯

状態空間モデルによる解の探索：分類

状態空間が木構造か、一般のグラフか

目標状態を見つければ十分か、目標状態への道も必要か 求めたいのは1つの解か、すべての解か

最適解か、準最適解か、それとも解であればなんでも良いか

基本アルゴリズム

状態空間は木構造

目的状態を

みつけるだけで良い

基本アルゴリズム

の流れ

𝑆

𝐺 𝐴

𝐵

𝐶 𝐹

𝐸

𝐷 𝐻

𝐼

𝐽

分岐、行き止まり、スタート、ゴール を「状態」とする

モデル化

図式表現

𝑆 𝐴

𝐵 𝐶 𝐸

𝐷

𝐻

基本アルゴリズム

の実現：スタック

S

A

D D

B C D

C

D D

E H

F G H

G

H H

基本アルゴリズム

の実現：キュー

S

A D

D B C

B C E H

C E H

E H

H F G

F G I J

G I J

I J

基本アルゴリズム

状態空間は一般のグ ラフ（閉路を持つ）

目的状態を

みつけるだけで良い

演習

下記の条件があるときのアルゴリズムを、

基本アルゴリズム2を改良して作成せよ。

状態空間は一般のグラフ

（閉路を持つ）

目的状態を

みつけるだけでなく、

目標状態への道も

求められるようにする

重み付き状態空間の探索

重みの付いたグラフでの最小コストの道を求める 最適化問題

最小コストの道

𝑆 … 𝑛 … 𝐺

𝑔(𝑛) ℎ(𝑛)

𝑆から𝑛までの

最短距離 𝑛から𝐺までの 最短距離

𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛)

𝑛を通る𝑆から𝐺までの 最短距離

ヒューリスティック関数

𝑆 … 𝑛 … 𝐺

𝑔(𝑛) ℎ(𝑛)

𝑆から𝑛までの

最短距離 𝑛から𝐺までの 最短距離

𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛)

𝑛を通る𝑆から𝐺までの 最短距離

現時点で見つかって いる最良の近似値

経験的知識による 近似値

𝑔′(𝑛) ℎ′(𝑛)

ヒューリスティックス

ヒューリスティック関数

A

アルゴリズム

ヒューリスティックを 用いたアルゴリズム

初期状態からの最小 コストを随時更新

ヒューリスティック を用いてなるべく早

く目標に接近する

A

アルゴリズムの流れ

𝑆

𝐴 𝐵

𝐶 G

状態空間のモデル 10

6

5 0

3 3 8

2

6

1 4

8

演習

𝑆

𝐴 𝐵

状態空間のモデル 10

6 3

3 8

2

6

1 4

下記の状態空間に対してAアルゴリズムを適用した場合に得られる道を示せ。

またその導出過程も記載せよ。

なお、初期状態は𝑆、目標状態は𝐺_𝑆𝐸𝑇 = {𝐺}とする。

本日の到達目標と概要

•

到達目標

–

系統的探索と、その実現方法としての

アルゴリズムの理解

•

概要

–

系統的探索

–

状態空間のモデル化

基本アルゴリズム

–

ヒューリスティック関数

アルゴリズム