離散数学

アルゴリズム設計
Algorithm Design
落合 秀也

著書 Algorithm Design を読み解く

2

章構成 (1/2)
1. Introduction: Some Representative Problems
2. Basics of Algorithm Analysis
3. Graphs
4. Greedy Algorithm
5. Divide and Conquer
6. Dynamic Programming
7. Network Flow
8. NP and Computational Intractability
3

章構成 (2/2)
9. PSPACE: A Class of Problems beyond NP
10. Extending the Limits of Tractability
11. Approximation Algorithm
12. Local Search
13. Randomized Algorithms
Epilogue: Algorithms That Run Forever4

本日の進め方
１．これまでの講義で扱ってきた部分をピックアップ
そして、
どのような位置づけになっているか
どのような記述になっているかを確かめる
２．関連する重要キーワードをピックアップ
そして、その意味について、考える
5

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
6講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
73.1 Basic Definitions and Applications

グラフ(Graph)を数学的に捉える• グラフGは、二つの集合で構成されている• 頂点(vertex)の集合V• 点(point)、節点(node)とも言う• 辺(edge)の集合E

D

e8

e4

• G (V, E) と書く

e6

A

e7

e2

• V={A, B, C, D, E, F}• E={ e1, e2, …, e10 }• e1={A,B}, e2={A,C}, …

e1

e10
C

e9

e3
辺

B

E

F
e5

頂点
8

3.1 Basic Definitions and Applications

有向グラフ(directed graph, digraph)• 有向グラフDは、二つの集合で構成されている• 頂点(vertex)の集合V• 点(point)、節点(node)とも言う• 弧(arc): 頂点の順序対の集合A

D

e8

e4

• D (V, A) と書く

e6

A

e7

e2

• V={A, B, C, D, E, F}• A={ e1, e2, …, e10 }• e1=<B,A>, e2=<C,A>, …

e1

e10
C

e9

e3
弧

E

B

F
e5

頂点

向きの無いグラフを、無向グラフと呼ぶこともある

9

3.1 Basic Definitions and Applications

グラフによる実世界のモデル化• 交通網• 分子構造• コンピュータ・ネットワーク• 依存関係• WWW• Social Network• 頂点： 都市や駅
• 辺 ： 道路や路線• 頂点： 端末やスイッチ• 辺 ： ケーブル
• 頂点： ページ
• 辺 ： リンク• 頂点： 原子• 辺 ： 結合• 頂点： 事象
• 辺 ： 原因、結果の関係• 頂点： 人間，
• 辺 ： 関係（知人，etc.）• ディジタル回路• 頂点： 論理素子
• 辺 ： 配線

10

3.1 Basic Definitions and Applications

道 (path)• 頂点-辺-頂点-辺-頂点-…-頂点 (ただし、同じ頂点を通らないもの) を、道(パス: path)と呼ぶ• モデル上の道を考察する上で重要な概念• 道は「辺の列」または「頂点の列」
A
で表現可能

D

e8

e4
e6

e7

e2

e10

e1

C

(例) 右図の場合：
e4, e8, e10 または A, D, E, F

e3
B

E

e9
F
e5
11

3.1 Basic Definitions and Applications

連結 (connectivity)• グラフGにおいて、任意の2頂点間に道が存在す
れば、グラフGは連結である、という。
D

e8

e4
e6

A

e1

e7

F

F
e5

連結なグラフ

E

C

e9

e3
B

e6

A
e10

C

e8

E

e7

e2
e1

D

B

e5

連結でないグラフ 12

3.1 Basic Definitions and Applications

無閉路(acyclic, cycle-free)グラフ• 閉路のないグラフ
F

A

H

E
B

G

H

E

B

D
C

F

A

D
C

退化木

G

連結グラフ

連結でないグラフ

木 (tree)森 (forest)133.1 Basic Definitions and Applications

木の構造• 根(root)• 枝(branch)• 葉(leaf)• 親(parent)• 子(child)• 先祖(ancestor)• 子孫(descendant)• 深さ(depth, level)
14

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
153.2 Graph Connectivity and Graph Traversal

連結性の判定問題を考える• グラフG(V,E)が与えられたとき、Gが連結かどうか、を判定したい。
• 小さいグラフなら、紙に書いてみればよい• 一般には簡単ではない• 大きいグラフの場合• コンピュータに判断させる場合

グラフG

16

3.2 Graph Connectivity and Graph Traversal

幅優先探索(Breadth-First Search)• 基本的な考え方• 頂点sから開始 ・・・ L0とする

s L0 L1 L2
L3• L0から、外向きに辺をつたい、接続する頂点を取り込む ・・・ L1とする• L1から、外向きに辺をつたい、接続する頂点を取り込む ・・・ L2とする• L2から、外向きに辺をつたい、接続する頂点を取り込む ・・・ L3とする
・・・

頂点sから湧き出す水によって引き起こされる洪水（Flood）が到達可能な頂点すべてに伝搬するイメージ17

3.2 Graph Connectivity and Graph Traversal

深さ優先探索 (Depth-First Search)• 基本的な考え方

s
c

a
d

b

g

e

k

f

h
i

j

• 開始点sから、辺をたどって行きつく
ところ（=dead end）まで行ってみる（ただし同じ頂点は取らない）• 行き止まり(=dead end)に当たれば、1つ戻って、別の辺をたどってみる• 1つ戻ってもダメなら、2つ戻ってみる• 2つ戻ってもダメなら、3つ戻ってみる
・・・

頂点sから歩き始めた人が、すべての行き止まりにあたるまで、
隈なく歩いていくイメージ18

3.2 Graph Connectivity and Graph Traversal

深さ優先探索によって作られる木• 出来るだけ深いところまで一気に作る• 戻りながら、別に行ける頂点があれば、そちらの枝を作る

s

s
a

d

b

c
b

f

g

e

k

f

h
i

j

i
j h
e
g
d
c k a
19
深さ優先探索木と呼ばれる

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
203.3 Implementing Graph Traversal Using Queues and Stacks

グラフを隣接リストで表現する• 隣接リスト(adjacency list)
1. ある頂点vの、近隣の頂点をリストで表現したもの: Adj[v]2. 全頂点に対して、同様のリストを作る: Adj – 配列
近隣の頂点

1
2

3

5

着目する頂点

1

2

3

2

1

4

3

1

5

O(n+m)

4

1

2

n: 頂点の数
m: 辺の数

5

3

4

4
Adj
Adjの大きさは4

5
21

3.3 Implementing Graph Traversal Using Queues and Stacks

キュー(Queue)の働きと使い方• 先入れ先出し装置： Fast In Fast Out (FIFO)

Enqueue(キューに入れる)キュー

Dequeue(キューから出す)• 入れた順番に取り出せるメモリ：• 3, 1, 2, 8, 6, 5, 4 の順に投入すれば、
3, 1, 2, 8, 6, 5, 4 の順に出てくる

22

3.3 Implementing Graph Traversal Using Queues and Stacks

深さ優先探索を実現する

スタック(Stack)を利用する• 後入れ先出し装置： Last In Fast Out (LIFO)
Push(スタックに入れる)Pop(スタックから出す)

スタック• 入れた順番の逆に取り出せるメモリ：(1) 3, 1, 2を投入
(2) 2個取り出す(3) 8, 6 を投入(4) 3個取り出す(5) 5, 4 を投入(6) 2個取り出す

取り出される列は2, 1, 6, 8, 3, 4, 5となる
23

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm243.6 Directed Acyclic Graph and Topological Ordering

有向非巡回グラフ
Directed Acyclic Graph (DAG)• 閉路の無い有向グラフ• 半順序性を持つ

D

A

E

B
C

F

G

• トポロジカルソートにより、頂点を一列に並べることができる(全順序に対応付けできる)• 上図の場合: A, D, B, E, C, F, G など
• ジョブのスケジューリング等で使われる
25

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
26

4.4 Shortest Paths in a Graph

最短経路問題を考える• ラベル付(重み付)グラフ G=(V,E)が与えられたとき、頂点sから頂点tへの最短経路 s-t を求めたい• 辺のラベルの意味：• 地点間の道のり• 地点間の移動時間• 地点間の移動に要する燃料の量• 状態の遷移で失う資金

s

8

2

2

2

2

9

4

5
3

5
4

4

7
1

3

8

6

1

=17

t

=18
8 8

1

5

4

=23

(*) 実際はコスト16の道が存在する• 最小コストでの移動経路を発見したい

27

4.4 Shortest Paths in a Graph

ダイクストラ法(Dijkstra’s Algorithm)
1959年： Edsger Dijkstraによって考案された
a

2 3

2
1

s

b
e

H

2
3

1
f

1

10
3

• 開始点 s∈Vから各頂点への最短経路を求める問題

g

4

2

2

66

7

5

0 1
c

1

d

• 考え方 -- G(V,E)に対して

7
4

8
5

7 5
i

赤字: 判明しているsからの最短距離h• いま、すでに部分Hに関して、最短経路が導出されているとする• sからの距離が判明している• Hと接する v ∈ V-H に対し、sからの距離を考える• その距離の最小値を与える
vを、Hに追加する
28

4.4 Shortest Paths in a Graph

ダイクストラ法(もう少し正確な定義)• 用語の定義：• グラフG(V,E)において、 u, v ∈V, e=(u,v) ∈ Eとする。
• 辺e=(u,v)の長さをleあるいはl(u,v)で表すとする。
• 開始点をsとする。d(u)で、sからuまでの最短距離を表すとする。
• prev(v)で、sからvへの最短経路におけるvの直前の頂点を表す。

• 挙動の定義： Vの部分集合 H を以下のように作成する。
• 初期状態： H = {s}, d(s)=0, d(v)=∞ (v≠s), prev(v)=null (v∈V) とする。
• u∈ H で辺e=(u, v)でつながっている v (∈ V-H) を考え、

d’(v) = min e=(u,v):u∈H { d(u) + le }を計算する。
• v ∈ V-Hにおいて、上記をさらに最小化するvを選定し、そのvをHに追加し、その距離をd(v)とおき、その時のuを用いて、prev(v)=uとす
る。
d(u1)

d(u2)
H

l(u1,v1)d’(v1) = min {d(u)+le}l(u2,v2)d’(v2) = min {d(u)+le}

d(v1)
または
d(v2)
のどちらか片方
29を決定する

4.4 Shortest Paths in a Graph

While Q is not empty
u := Q.extractMin()
Foreach v in Adj[u]If d[v] > d[u] + length(u, v) Then,d[v] := d[u] + length(u, v)• While文の内部は n回実行される。
prev[v]=u• Foreach文の内部は nm回実行される。
( Q.changeKey() ) 実装によっては O(nm) となりえる。 EndIf
EndForEndWhile• Q に リストや配列を使う場合

ダイクストラ法:
計算量の考察• Q.extractMin()に O(n) の時間を要する• Q.extractMin()は n回 呼び出される O(n2)• Q に 2分ヒープを使う場合• Q.extractMin()に O(log n)の時間を要する• Q.extractMin()の呼び出しはn回ある  O(n log n)• d[v]の更新に伴うヒープの組換え処理に、O(log n)の時間を要する• d[v]の更新は、m回発生する  O(m log n)
 O( (n+m) log n )30

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm31

4.5 The Minimum Spanning Tree Problem

最小全域木を考える
Minimum Spanning Tree Problem• ラベル付(重み付) グラフ G(V, E)が与えられたとき、ラベルの和が最小となる全域木を作りたい• 全域木 G(V, T)
5• Vのすべての頂点で構成される木• 最小全域木∑ e∈T Ceを最小にする T で作られる G(V,T)(Ceは辺eのラベル)

8

2
2

2

2

4

5
3

9

1
6

例：ラベルを地点間の配線コストとする
このとき、全地点がつながるネットワークを
最小コストで配線したい

4

1

4

7

1

3

8 8

4

8

32

5

4.5 The Minimum Spanning Tree Problem

プリム法: 計算量の考察• While文の内部は n回実行される。

• Foreach文の内部は nm回実行される。

 実装によっては O(nm) となりえる。

• Q に リストや配列を使う場合• Q.extractMin()に O(n) の時間を要する• Q.extractMin()は n回 呼び出される O(n2)• Q に 2分ヒープを使う場合

While Q is not empty
u := Q.extractMin()
Foreach v in Adj[u]If c[v] > length(u, v) Then,c[v] := length(u, v)
prev[v] := u
( Q.changeKey() )EndIf
EndForEndWhile• Q.extractMin()に O(log n)の時間を要する• Q.extractMin()の呼び出しはn回ある  O(n log n)• c[v]の更新に伴うヒープの組換え処理に、O(log n)の時間を要する• c[v]の更新は、m回発生する  O(m log n)
 O( (n+m) log n )33

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
34

6.8 Shortest Paths in a Graph

最短経路問題の解法• ダイクストラ法• すべての辺の重みが非負の場合に適用可能• 貪欲法(Greedy Algorithm)の一種• ベルマン・フォード法• 辺の重みに負があっても良いケースがある（有向グラフ
で、有向閉路の和が負でない場合）• 動的計画法(Dynamic Programming)の一種
9

4

-5

s

5

t

-2
7

コストが、資金の支出の場合、マイナスは、収入を意味する 35

6.8 Shortest Paths in a Graph

ベルマン・フォード法• i回目から、i+1回目への計算(漸化式)を考える• ここで、iは、拡散量(sから伝搬した辺の数)に相当する• i回目(i個の辺の伝搬を考えたとき)における、頂点sから頂点vまでの最短距離をOPT(i,v)とする。このとき、以下が言える。

OPT(i+1, v) = minu∈nbr(v) {OPT(i,u)+Cuv}(*) ここでnbr(v)は、vの近隣頂点(自分自身も含む)の集合とする
またCuvは辺(u,v)のコストとし、便宜上Cvv=0 とする。

• 初期条件 (i=0のとき)• OPT(0,s)=0, OPT(0,v)=∞ (v∈V, v≠s)

36

6.8 Shortest Paths in a Graph

OPT(i+1, v) = minu∈nbr(v) {OPT(i,u)+Cuv}の意味
OPT(i,c)
OPT(i,b)

b

c
Cbv

Cav

a
OPT(i,a)Ccv

v

OPT(i,v)

Cvv (=0)

OPT(i,v)
OPT(i,a)+Cav
OPT(i,b)+Cbv
OPT(i,c)+Ccv
OPT(i+1,v)は、上記で最小のものとする
37

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm38

6.9 Shortest Paths and Distance Vector Protocols

ベルマンフォード法の分散化• グラフ G(V,E)において、各頂点は、辺で接続する
もう片方の頂点と通信を行うものとする。
OPT(u) + Cuv• このとき、uv• 各頂点uから、頂点v (∈nbr(u))に向けて、OPT(u)+Cuv
を発信する• 受信側の頂点vでは、受信した値の中(他者からのものも含む)で、最小のものをOPT(v)として選ぶ• 開始点sのOPT(s)は 0 に固定するという処理を行うと、ベルマンフォード法を分散的に実装できる39

6.9 Shortest Paths and Distance Vector Protocols

ベルマンフォード法の分散化：
各頂点の動作OPT(u) + Cuv3

v2

u
OPT(u)

v3

頂点uからの送信(定期的に行う)

u1

u2

OPT(u3) + Cu3v

v1v
If OPT(v) > 受信結果
OPT(v) :=受信結果
EndIf

u3
頂点vでの受信と処理
40

講義で扱った内容はどこで触れられているか
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.6 Directed Acyclic Graphs and Topological Ordering

4 Greedy Algorithm
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem

6 Dynamic Programming
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols

7 Network Flow
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm417.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

最大流問題 Maximum Flow Problem• ラベル付(重み付) グラフ G(V, E)が与えられたとき、流入点
sから流出点tまでの総流量を最大化したい• 辺のラベルの意味： 流量の容量(最大量) 855• 運べる荷物の量• 流せる水の量• 送れるパケット数

22

22

10

• このとき、

s

5

2

4
9
4
2
1
3
4
5
7
1
5 1 1
1
8 8
3
4 1
4
3
8
6

3
1

1
4

4

5
5

t
10

sに流れ込む流量 = tから流れ出る流量 (グラフの外から見た場合)
sから流れ出す流量 = tに流れ込む流量 (グラフの中で見た場合)である。
42
この量の最大値(とそのときのフロー)をどう求めればよいか？

7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

フローの定式化• 辺を流れるフロー
f(u,v)uC(u,v)C(v,u)v

f(u, v) ≦ C(u, v)
f(v, u) = - f (u, v)∴ -C(v, u) ≦ f(u, v) ≦ C(u, v)
ただし C(u, v) = C(v, u)とは限らない• 頂点への流入量と流出量v

流入量: fin(v) = ∑ u∈V, f(u,v)>0 f(u,v)
流出量: fout (v) = ∑ w∈V, f(v,w)>0 f(v,w)
v≠s,t であれば fin(v) = fout(v)
総流量: total(f)= fout(s) = fin(t) 43

7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

フォード・ファルカーソン法
Ford-Fulkerson Algorithm
※ 考え方

u
20
20
30

s

10
10

• s-t間の何らかの道を考え、その流量の上限
10
を算出する
10
• そのフローfを容量Cから引いた値（残余容30量）を計算し、グラフから差し引く ・・・そのグ
20
ラフをGfとする
20 • Gfに対して、同様のことをする（つまり、s-t
20間の何らかの道を考え、その流量の上限を算出し、総フローを算出し、容量から差し引
フローに沿っていて・・・）-20• s-t間の道が無くなれば、終了

t

v

u

u

0

10
10

s

40
50

10
10

10
0

0

10

0
20

t

40
40

s

0

40 フローに沿って（さらに）

v

-10

20

v

20
0

s-t間の道がなくなった(容量>0の弧についてのみ考える)t40 このとき差し引いている
総フローが求める最大流44

7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

フォード・ファルカーソンのアルゴリズムMax-Flow(G(V,E), s, t)∀e∈E, f(e)=0
While any paths from s to t exist in residual graph Gf
道の発見にはP := simple-path(s,t) in Gf「幅優先探索」「深さ優先探索」などが用いられる
f’ := augment(f, P)
フロー f に道Pを流れるフローの上限分をUpdate f to be f’
追加し、それを f’ に代入する処理
Update Gf to be Gf’
EndWhile※ このアルゴリズムの停止性について
Return f
考察してみよ45

本日の進め方
１．これまでの講義で扱ってきた部分をピックアップ
そして、
どのような位置づけになっているか
どのような記述になっているかを確かめる
２．関連する重要キーワードをピックアップ
そして、その意味について、考える46

キーワード• Greedy Algorithm (貪欲アルゴリズム)• Divide and Conquer (分割統治法)• Dynamic Programming (動的計画法)• NP and Computational Intractability• Approximation Algorithms• Local Search• Randomized Algorithms
47

Greedy Algorithm (貪欲アルゴリズム)• 「小さなステップで、より良い方向に進んでいくと、最終的に、最適解に到達できる」 アルゴリズムのファミリー• 「ローカルな問題を解決し、積み上げていくと（それ自体は正しいのかどうか自明ではないが）、最終的に全体の問題を解決できる」アルゴリズムのファミリー• 例）• ダイクストラ法• プリム法• Interval Scheduling 問題• Optimal Caching 問題• Huffman Codes and Data Compression
48

Divide and Conquer (分割統治法)• 「一つの問題を、複数の部分問題に分割し、それぞれの部分問題について、同様の方法で解き、それらの解を処理することで、問題の解に到達する」アルゴリズムのファミリー• 「問題の分割・統合を再帰的に行うことによって問題を解く」アルゴリズムのファミリー• 例）• Mergesort• Finding the Closest Pair of Points• Convolutions and the Fast Fourier Transform49

Dynamic Programming (動的計画法)• 「貪欲アルゴリズム や 分割統治法よりも強力に問題を解決する」アルゴリズム• 「貪欲アルゴリズム や 分割統治法よりも適用範囲の広い」アルゴリズム• 「広い解の空間を作り出し、個別に最適解を計算し、注
意深くそれを伝搬させることで全体的な最適解に到達する」アルゴリズム• 「漸化式を走らせることで、力学的にそこにたどり着く（収束する）」アルゴリズム• 「分割統治法的な考えの潜んでいる」アルゴリズム• 「貪欲アルゴリズムの反対の方向から攻める」アルゴリ
ズム• 例） ベルマンフォードのアルゴリズム
50

計算不可能な問題への実用的アルゴリズム• NP and Computational Intractability• 「計算複雑性」が理由で解けない問題が存在する。

• Approximation Algorithms• 最適解が得られなくても近似解を得られるものがある• （実用上十分であれば、良い、という考え方）• Local Search• いま考えられるよりも、より良い解にたどり着く（ただし、それが全体の最適解となっているかは不明）• （実用上十分であれば、良い、という考え方）• Randomized Algorithms• 対象の期待値を問題にすることもある（入力データを確率的に与えられている等）• 動作を乱数にゆだねるものもある

51

「離散数学」 講義の内容（まとめ）4月8日 集合
4月15日 関係 と 関数
4月22日 順序集合 と 束
5月6日 命題計算
5月16日 ブール代数
5月20日 グラフの構造と種類
5月27日 グラフ探索アルゴリズム
6月3日 最短経路問題
6月10日 演習（レポート提出）
6月17日 最小全域木、最大流問題
6月24日 平面グラフ
7月1日 スキップグラフ
7月8日 アルゴリズム設計

52