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

(1)

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

第9週グラフ構造と最短路問題

2013年11月28日金岡晃

(2)

授業計画

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/10/31 アルゴリズムとデータ構造

(3)

中間試験：解答と解説

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

2 ^2013/10/31 アルゴリズムとデータ構造

(4)

3

＜問1＞

𝑎² + 𝑏² = 𝑐²を満たす自然数の組 𝑎, 𝑏, 𝑐 をピタゴラス数という。下記のアルゴリズムは与えらえた 2 つの自然数 𝑎, 𝑏 に対し、𝑎² + 𝑏² = 𝑐²を満たす𝑐を探すアルゴリズムである。

【アルゴリズム A】

1) 𝑥 = 𝑎² + 𝑏²を計算する

2) 𝑖 = 1, … , 𝑥に対し、以下を行う

(ア) 𝑖²が𝑥と等しいか確認する。等しい場合、𝑖を出力してアルゴリズムを終了する 3) 見つからなかった旨のメッセージを出力し、アルゴリズムを終了する

アルゴリズム Aに対し、以下を答えよ。

＜問1-1＞アルゴリズムA の計算量をオーダ記法で示せ

＜問 1-2＞アルゴリズム A より効率の良いアルゴリズムを示せ。その際、どの点がアルゴリズム A と比較して効率が良いかを書くこと。

＜問1-3＞問 1-2 で示したアルゴリズムの計算量をオーダ記法で示せ

問

1-1

：

：

𝑓 𝑛 = 𝑛 × 𝑓 𝑛 − 1

(6)

5

＜問 3＞

文字列照合のアルゴリズム KMP 法において、文字（アルファベット）が{A, B, C, D} である場合、パターン

ABCABCAB に対するfailを導出せよ。ただし、解答には求めた failだけではなく、導出過程も記載すること。

問

3

：

fail = {0,1,1,0,1,1,0,1}

(7)

6

＜問 4＞

12枚のコインがあり、そのうち 1枚だけが偽物である。偽物は外見は違わないが、重さが異なっているので区別できる。ただし、偽物が本物より重いのか軽いのか不明である。ここで、天秤を 3 回だけ用いて、どのコインが偽物でかつそれは本物より重いのか軽いのかを知るにはどうすれば良いか、答えよ。

ポイント

• アルゴリズム（手続き）を意識して書くと良い

• パターンすべてが網羅されているか確認すると良い

(8)

7

𝑎 + 𝑏 + 𝑐 + 𝑑: 𝑒 + 𝑓 + 𝑔 + ℎ

𝑎 + 𝑏 + 𝑒: 𝑐 + 𝑓 + 𝑥

𝑎 ∶ 𝑏 𝑔 ∶ ℎ 𝑐 ∶ 𝑥

𝑖 + 𝑗 ∶ 𝑘 + 𝑥

𝑖: 𝑗 𝑖: 𝑗

> = <

>

=

< > <

𝑎 + 𝑏 + 𝑒: 𝑐 + 𝑓 + 𝑥

𝑒 ∶ 𝑥 𝑔 ∶ ℎ 𝑎 ∶ 𝑏

>

= <

𝛼: 𝛽 _を左に_𝛼_、右に_𝛽を載せて天秤で量る動作を表すものとする。

𝛼 + 𝛽: 𝛾

𝑙: 𝑥

=

での𝛼 + 𝛽は、右に𝛼と𝛽を載せていることを表すものとする。

天秤で量った結果をそれぞれ“>”, “=”, “<”で表し、「左が重い」「釣り合う」「右が重い」

を示すものとする。

12枚のコインを𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗, 𝑘, 𝑙とそれぞれ呼ぶこととし、量った結果に従い次の天秤での計量を行うことを矢印で表すと、以下の図により3回の計量で偽物の判別と重い・軽いの判断が可能である。

Branch

）とも

•

グラフの図表現

–

集合表現

10

(12)

グラフの定義

11

グラフ（Graph）

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

𝐺 = 𝑉, 𝐸

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

グラフの図表現

：頂点

：辺

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝑐 𝑑

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

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

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

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

グラフ𝐺₁

有向グラフ𝐺₂

(13)

グラフの用語（１）

12

有向グラフ（Directed Graph）

無向グラフ（Undirected Graph）

辺が向きを持つグラフ（例：スライド11の𝐺₂）

辺が向きを持たないグラフ（例：スライド11の𝐺₁）隣接（Adjacent）

あるグラフ𝐺 = 𝑉, 𝐸 で𝑒 = 𝑢, 𝑣 で𝑒 ∈ 𝐸のとき、頂点𝑢と𝑣は互いに隣接している、と言う

有向グラフの場合、あるグラフ𝐺 = 𝑉, 𝐸 で𝑒 = 𝑢, 𝑣 で𝑒 ∈ 𝐸のとき、頂点𝑢は 𝑣に隣接すると言い、頂点𝑣は𝑢から隣接すると言う。

始点と終点

あるグラフ𝐺 = 𝑉, 𝐸 で𝑒 = 𝑢, 𝑣 で𝑒 ∈ 𝐸のとき、頂点𝑢を辺𝑒の始点、𝑣を辺𝑒 の終点と言う

(14)

グラフの用語（２）

13

次数（Degree）

無向グラフにおいて、ある頂点に接続している辺の個数

有向グラフの場合は、ある頂点について、それを始点とする辺の個数をその頂点の出次数（Out-degree）、それを終点とする辺の個数をその頂点の入次数（In-degree）という。

孤立（Isolated）

次数0の頂点を孤立しているという完全グラフ（Complete Graph）

どの2頂点をとってもそれらが隣接しているようなグラフ。

頂点の個数 𝑉 が𝑛の完全グラフを𝐾_𝑛と書く部分グラフ（Subgraph）

𝐺^′ = 𝑉^′, 𝐸^′ があって、 𝑉^′ ⊆ 𝑉かつ𝐸^′ ⊆ 𝐸のとき 𝐺′は𝐺の部分グラフという

(15)

グラフの用語（３）

14

誘導（生成）部分グラフ（Induced Subgraph）

グラフ𝐺 = 𝑉, 𝐸 に対して、 𝑉の部分集合𝑉′を考える。このとき、 𝐸^′ = 𝑢, 𝑣 ∈ 𝐸 | 𝑢, 𝑣 ∈ 𝑉′ を用いて作られる部分グラフ𝐺^′ = 𝑉^′, 𝐸^′ を、グラフ𝐺 の誘導（生成）部分グラフという

クリーク（Clique）

グラフ𝐺の部分グラフで、しかも完全グラフであるものと𝐺のクリークと言う。

𝐺のクリークのうち最も多くの頂点を含むものを最大クリークと言う。

(16)

グラフの用語（４）

15

道（Path、路）

頂点列𝑃 = 𝑣₀, 𝑣₁, ⋯ , 𝑣_𝑘で 𝑣_𝑖, 𝑣_𝑖+1 ∈ 𝐸 𝑖 = 0, ⋯ , 𝑘 − 1 がなりたつもの単純（Simple）

道𝑃に現れる頂点がすべて異なるとき、𝑃は単純であるという閉路（Cycle、Circuit）

𝑣₀ = 𝑣_𝑘のとき、𝑃を閉路というループ（Self-loop）

長さ1の閉路

到達可能（Reachable）

2頂点間を結ぶ道が存在するとき、到達可能であるという

(17)

グラフの用語（５）

16

最短路（Shortest Path）

到達可能な2頂点間を結ぶ長さ最小のものを最短路という距離（Distance）

到達可能な2頂点間の最短路の長さを距離という。

到達可能でない2頂点の距離は無限大∞と定義する。

有向路（Directed Path）

有向グラフのとき、 𝑣_𝑖, 𝑣_𝑖+1 ∈ 𝐸 𝑖 = 0, ⋯ , 𝑘 − 1 を満たすような頂点列 𝑃 = 𝑣₀, 𝑣₁, ⋯ , 𝑣_𝑘があるとき、𝑃を頂点𝑣₀から𝑣_𝑘へ至る有向路といい、𝑣_0から𝑣_𝑘へ到達可能という

(18)

演習

1

：グラフの描画

17

𝐾₆を描画せよ

(19)

演習

2

：部分グラフ

18

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

𝑎 𝑏

𝑐 𝑑

𝑒

𝑓

𝑔 ℎ

(20)

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

19

𝐴₁ =

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となっている行列。

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝑐 𝑑

無向グラフ𝐺₁

隣接行列

(21)

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

20

直交リスト

𝐴₂ =

0 1 1 0

0 0 0 1

1 1 0 1

0 0 0 0

𝑎 𝑏

𝑐 𝑑

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

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

(22)

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

21

隣接リスト

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝑐 𝑑

無向グラフ𝐺₁

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

(23)

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

22

重み付グラフ（Weighted Graph）

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

𝑆 𝐷

𝐴 𝐵

𝐻 𝐼

𝐸 𝐽

𝐶 𝐹 𝐾 𝐺

4

3

1

2

2 2

1 1

2

3

1 3

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

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

最短路問題

(24)

Dijkstra

のアルゴリズム

23

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

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

(25)

Dijkstra

アルゴリズムを用いた事例

24

𝑆 𝐷

𝐴 𝐵

𝐻 𝐼

𝐸 𝐽

𝐶 𝐹 𝐾 𝐺

4 3

1

1 2

2 2

1 1 2

3 1 3

𝑉 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻, 𝐼, 𝐽,𝐾,𝑆}

(26)

Floyd

のアルゴリズム

25

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

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

(27)

演習

3

26

下のグラフに対し、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の初期状態

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

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

授業計画

中間試験：解答と解説

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

問

：

または

問

： 省略

問

： 省略

問

：

問

：

第 9 週

グラフ構造と最短路問題

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

本日の到達目標と概要

到達目標

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

概要

グラフの基礎

グラフのデータ表現

最短路問題

のアルゴリズム

グラフの定義（１）

グラフ（

）

頂点（

）の有限集合

と辺（

）の有限集合

により定 義

節（

）、枝（

）とも

グラフの図表現

集合表現

グラフの定義

グラフの用語（１）

グラフの用語（２）

グラフの用語（３）

グラフの用語（４）

グラフの用語（５）

演習

：グラフの描画

演習

：部分グラフ

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

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

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

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

のアルゴリズム

アルゴリズムを用いた事例

のアルゴリズム

演習

本日の到達目標と概要

到達目標

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

概要

グラフの基礎

グラフのデータ表現

最短路問題

のアルゴリズム

：省略

：省略

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

により定義

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