アルゴリズムの基礎 - IWAMA Lab.

アルゴリズム入門（1）
（アルゴリズムの基礎）
宮崎修一
京都大学学術情報メディアセンター
アルゴリズムとは？
問題を解く手順、算法（あとで具体例）
問題とは？
入力と、それに対する出力がきっちり決まっているもの。
（与えられた入力に対して、正しい出力を計算することを
要求する。）
2
例１：最大公約数を求める問題
入力：正の整数 x と y
出力：x と y の最大公約数
入力（１０，８） → 出力２
入力（３，８） → 出力１
入力（５，１０） → 出力５
例２：ソーティング（並べ替え）
入力：n個の正の整数
出力：小さい順に並べ替えたもの
入力１０，９，２，６，４，１，８，３
↓
出力１，２，３，４，６，８，９，１０
3
もっと身近（実用的）な例
・文字列検索
入力：文章と検索文字列
出力：文章中で文字列が含まれる位置
4
・メールソフトの並べ替え
入力：たくさんのメール
出力：指定された順序に従った並べ替え
5
・ＷＥＢページ検索
入力：キーワード
出力：キーワードに関係の深いＷＥＢページ
6
アルゴリズムの例（最大公約数を求める問題）
ユークリッドの互除法（世界最古のアルゴリズム）
入力 x, y (x>y)
ステップ１： x を y で割って、余りを r とする。
ステップ２： r = 0 ならば、y を出力して終了。
r ≠ 0 ならば、ステップ３へ。
ステップ３： x ← y （y を x に代入）
y ← r （r を y に代入）
ステップ１へ。
7
ユークリッドの互除法の動作例
入力 (10, 8)
x
ステップ１：
ステップ２：
ステップ３：
ステップ１：
ステップ２：
10÷8=1 余り2。
r=2。0でないのでステップ３へ。
x=8、y=2。ステップ１へ。
8÷2=4 余り0。
r=0なので終了。
このとき、y =2なので、2を出力。
y
r
(10, 8) 2
(8, 2) 0
8
ユークリッドの互除法の動作例
入力 (8, 3)
x
ステップ１：
ステップ２：
ステップ３：
ステップ１：
ステップ２：
ステップ３：
ステップ１：
ステップ２：
8÷3=2 余り2。
r=2。0でないのでステップ３へ。
x=3、y=2。ステップ１へ。
3÷2=1 余り1。
r=1。0でないのでステップ３へ。
x=2、y=1。ステップ１へ。
2÷1=2 余り0。
r=0なので終了。
このとき、y =1なので、1を出力。
y
r
(8, 3) 2
(3, 2) 1
(2, 1) 0
9
ユークリッドの互除法は、入力(10, 8)や(8, 3)に対しては
正しく動作することが分かった。
しかし、アルゴリズムは、どんな入力に対しても正しく動作
しなければならない。
どんな入力に対しても正しく動作することの証明
入力 x, yに対して、正しい答を d とする。
（つまり、x = ds, y = dt で、sとtは互いに素）
10
ステップ１： x を y で割って、余りを r とする。
まず、r =0ならば、yが最大公約数なのは簡単に分かる。
なので、r ≠0の場合を考える。
x = uy + r （uは商）
ds = udt + r
r = ds - udt
= d (s- ut)
x = ds, y = dt で、sとtは互いに素
y = dt, r = d (s- ut) である。
tとs- utは互いに素であることを言う。
もし、共通素因数を持ったら。。。それを a として、
t= ap, s- ut = aq と書ける。
s= aq + ut = aq + uap = a(q+up)
となり、sとtが素因数 a を持つので、sとtが互いに素である
ことに反する。
11
y = dt, r = d (s- ut) である。
tとs- utは互いに素である。
y と r の最大公約数も d。
ステップ３では、y と r を新しい x と y にして、ステップ１に戻る。
→ y と r の最大公約数を求めに行っている。
要約すると：
r =0 ならば y が答で、それをステップ２で出力する。
r ≠0 ならば、x と y の最大公約数は y と r の最大公約数なので、
次のラウンドで y と r の最大公約数を求めに行く。
（答を保存している。）
12
例えば(10, 8)のケース
(10, 8) の最大公約数
↓
(8, 2) の最大公約数
↓
2
例えば(8, 3)のケース
(8, 3) の最大公約数
↓
(3, 2) の最大公約数
↓
(2, 1) の最大公約数
↓
1
x
y
r
(10, 8) 2
(8, 2) 0
x
y
r
(8, 3) 2
(3, 2) 1
(2, 1) 0
13
アルゴリズムは、正しい答を出力するか、または、答を保存する
ことは分かった。
↓
つまり、出力したときは、それが正しい答であることは保証される。
↓
しかし、これだけでは、常に答を出力することの保証にはなって
いない。（無限に答を保存し続ける可能性がある）
停止性の証明：
ステップ１： x を y で割って、余りを r とする。
なので、r < y
ステップ３で、x ← y, y ← r のときに、yの値は必ず小さくなる。
しかし、絶対に負にはならないので、どこかの時点で必ず0になる。
↓
アルゴリズムは必ず終了する。
14
アルゴリズムとプログラム
アルゴリズムは、計算の手順を書いたもの。（たとえば、日本語、
英語など。）プログラムは、それが計算機上で実行できるように
具体的なプログラミング言語（例えばC、JAVAなど）で書いたもの。
アルゴリズム
プログラム
ステップ１： x を y で割って、余りを r とする。
ステップ２： r = 0 ならば、y を出力して終了。
r ≠ 0 ならば、ステップ３へ。
ステップ３： x ← y （y を x に代入）
y ← r （r を y に代入）
ステップ１へ。
while(r!=0)
{r:=x;
for (r>=y) {r:=r-y;}.
x:=y; y:=r;}
print(y);
15
問題 : ユークリッドの互除法を使って、
次の2数の最大公約数を求めよ。
(a) 1470と63。
(b) 89と55。
16
別の例
安定結婚問題
お見合いパーティー
参加者
男子：１, ２, ３, ４, ５
女子： a, b, c, d, e
パーティー終了後に、5組のカップルを作りたい。
これを、「マッチング」と言う。
各参加者に、希望を出してもらう。
17
安定結婚問題
男子：１, ２, ３, ４, ５
女子： a, b, c, d, e
1:
2:
3:
4:
5:
c
a
a
b
d
e
b
d
e
a
a
c
c
d
e
d
d
e
a
b
b
e
b
c
c
a:
b:
c:
d:
e:
4
5
2
3
3
1
1
3
4
1
3
2
1
2
5
2
3
5
5
2
5
4
4
1
4
それぞれの人は、左から右に向かって、好きな
相手を順番に書いている。
18
例
1:
2:
3:
4:
5:
c
a
a
b
d
e
b
d
e
a
a
c
c
d
e
d
d
e
a
b
b
e
b
c
c
a:
b:
c:
d:
e:
4
5
2
3
3
1
1
3
4
1
3
2
1
2
5
2
3
5
5
2
5
4
4
1
4
これは、なかなか良い。全員が第3位以内とペアになっている。
全員が第2位以内とペアになるマッチングは存在しない。
問題：なぜ？
19
例
1:
2:
3:
4:
5:
c
a
a
b
d
e
b
d
e
a
a
c
c
d
e
d
d
e
a
b
b
e
b
c
c
a:
b:
c:
d:
e:
4
5
2
3
3
1
1
3
4
1
3
2
1
2
5
2
3
5
5
2
5
4
4
1
4
ところが、このマッチングには欠点がある。問題：何が欠点？
(1, e)は、今の相手よりお互いが好き。今のマッチングに
逆らって、「駆け落ち」する可能性がある。
こういうペアを「ブロッキングペア」と呼ぶ。
ブロッキングペアがあるとマッチングが壊れる → 不安定
ブロッキングペアのないマッチング：安定マッチング
20
1:
2:
3:
4:
5:
c
a
a
b
d
e
b
d
e
a
a
c
c
d
e
d
d
e
a
b
b
e
b
c
c
a:
b:
c:
d:
e:
4
5
2
3
3
1
1
3
4
1
3
2
1
2
5
2
3
5
5
2
5
4
4
1
4
問題：この例に対する安定マッチングを求めよ。
21
安定マッチングはどういうところで使われているの？
例：大学での研究室配属
研究室A（定員3名）
アルゴリズム
aさん
a: A D B C
bさん
b: E A B D
cさん
dさん
研究室B（定員4名）
c: F Bこれらの希望リストを使って
C A
インターネット
安定マッチングを求める
B: d b c a f e g …
d: B A C F
eさん
研究室C（定員3名）
画像処理
e: C B F C
A: g f c b a e …
。。。
。。。
C: b e d c f e a …
どの研究室に行きたいかの
希望リストを書く
どの学生に来て欲しいかの
希望リストを書く
22
例：日本の研修医マッチング（JRMP) https://www.jrmp.jp/
医学部を卒業して医師国家試験に合格した医師は、2年間
どこかの病院で研修を行う。どの病院に行くかの配属を決めるもの。
2004年にスタート（アメリカでは1950年代から）
8,500人の研修医を1,000病院の10,000～11,000ポストに配属
23
24
例：腎臓交換移植
Aさんが腎臓病の息子aの
ために腎臓を提供したいが、
型が合わない。
Bさんが腎臓病の弟bの
ために腎臓を提供したいが、
型が合わない。
A
B
×
×
a
b
ところが、Aさんがbさんに、Bさんがaさんにだったら
型が合う。
このとき、A-a と B-b で腎臓を交換して移植すると、
どちらもハッピー。
25
例：腎臓交換移植
移植したいけど型が合わない（不幸な）ペア
B
D
F
C
E
A
× × × × × ×
a
b
c
d
e
Y
…
f
Z
× ×
y
z
ペア同士のペア（マッチング）を作って交換する。
これまで助からなかった者が助かる。
B
D
C
Y
F
Z
×
×
×
×
×
×
b
d
c
y
f
z
26
2012年ノーベル経済学賞
安定配分の理論とマーケットデザインの実践
・安定マッチングの理論研究
・その結果を世の中のマッチングに応用
（研修医配属、学校配属、腎臓交換移植など）
Lloyd S. Shapley
Alvin E. Roth
27
素朴な疑問
さっきの例には「たまたま」
安定マッチングがあったが、
どんな場合でも安定
マッチングはあるの？
1:
2:
3:
4:
5:
c
a
a
b
d
e
b
d
e
a
a
c
c
d
e
d
d
e
a
b
b
e
b
c
c
a:
b:
c:
d:
e:
4
5
2
3
3
1
1
3
4
1
3
2
1
2
5
2
3
5
5
2
・誰かの希望リストが今のと違っていたら？
・今の例は5人対5人だったが、10人対10人では？
100人対100人では？
安定マッチングは必ずある。人数がどれだけ増えても、
どんな希望リストであっても、必ずある。
28
5
4
4
1
4
安定マッチングを求めるには、どうしたらいいか？
単純なアルゴリズム：
マッチングを全て求めて、それぞれが安定かどうかを
1個ずつチェックする。
1-a
2-b
3-c
4-d
5-e
1-a
2-b
3-c
4-e
5-d
1-a
2-b
3-d
4-c
5-e
1-a
2-b
3-d
4-e
5-c
1-a
2-b
3-e
4-d
5-c
…
安定なマッチングが見つかった所で、それを出力する。
全部のマッチングを調べているので、必ず答は求まる。
29
計算時間は、どれぐらい掛かるだろうか？
問題：男性5人、女性5人の場合、マッチングは何通りある？
30
n!ってどれぐらい？
n
1
2
n!
1
2
…
5
…
120
10
…
3,628,800
50
50!
40
50! > 10
1秒間に1億(=108 )個のマッチングを生成し、
32
その安定性をチェックできたとしても、10 秒以上かかる。
1時間＝ 3,600秒
1日＝ 86,400秒
1年＝ 31,536,000秒＜ 10 8 秒
32
24
10 秒 > 10 年
11
宇宙の年齢≒138億年＜ 10 年
宇宙の年齢の10,000,000,000,000回分待っても答えが出ない。
31
もっと速く求めることはできないか？
安定マッチングを求める Gale-Shapley アルゴリズム
1: c
2: ×
a
3: a
4: ×
b
5: d
e
b
d
e
a
a
c
c
d
e
d
d
e
a
b
b
e
b
c
c
a:
b:
c:
d:
e:
4
5
2
3
3
1
1
3
4
1
3
2
1
2
5
×
2 5
3 ×
4
5 4
5 1
2 4
n 2 ステップで終わる
問題：どうしてこのアルゴリズムで安定マッチングが求まる？
32
(安定性の証明)
求まったマッチングが安定でないとすると、
ブロッキングペアが存在する。
×
2: ・・・ e ・・・
e: ・・・ 2 ・・・
男性2は女性eにプロポーズしたが断られた。
（男性はリストの前から順番にプロポーズするので）
その時点では、女性eは男性2よりも良い人と婚約していた。
×
e: ・・・ 2 ・・・
それ以後、女性が相手を変える場合は、より良い相手にしか
変えない。
最終的に男性2より下の人とペアになっているのは矛盾。
(証明終わり) 33
1秒間に１億ステップ計算できるなら、
0.000025秒で終わる
n
1
2
…
5
…
10
…
50
n2
1
4
25
100
2,500
n!
1
2
120
3,628,800
> 10
40
1秒間に1億個のマッチングを生成し、その安定性をチェック
32
24
できたとしても、10 秒＞ 10 年かかる
11
宇宙の年齢≒138億年＜ 10 年
34
アルゴリズムの時間計算量
できるだけ速く答を求めるアルゴリズム＝良いアルゴリズム。
効率の良い
アルゴリズム
n
2
<
n
2
<
n! (≈
)
超指数時間アルゴリズム
指数時間アルゴリズム（ c n の形のもの）
多項式時間アルゴリズム（ n c の形のもの）
35
計算時間の爆発、アルゴリズムの効率を題材にした動画
「フカシギの数え方」
JST ERATO
湊離散構造処理系プロジェクト
「アルゴリズムが世界を変える」
JST ERATO
河原林巨大グラフプロジェクト
36
アルゴリズム研究（の１つ）
問題に対して、できるだけ早いアルゴリズムを構築する。
1.5
3
2
→n →n →n
→ …
n
n
2 → 1.8 → 1.7n → 1.4n
→ …
n5
・・・
1.618n [Monien, Speckenmeyer,79]
１つの例：
３ＳＡＴ
1.362 n [Paturi et al.,98]
1.334 n [Schoening,99]
1.3302n [Hofmeister et al.,02]
1.3290n [Baumer, Schuler,03]
1.3280n [Rolf,03]
1.3238n (1.3227 n )[Iwama, Tamaki,04]
1.32216n [Rolf,05]
1.32113 n [Iwama, Takai, Seto, Tamaki,10]
1.32065n [Hertli, Moser, Scheder , 10]
1.30704n [Hertli,11]
37
計算量のより厳密な話
入力の「サイズ」：
入力の長さ。
例えば安定結婚問題では、希望リストの長さの総和。
入力xの長さを | x | と書く。
操作の単位：
１ステップでどういう操作ができるか。
例えば安定結婚問題では、
・男性mの第i希望がどの女性であるか調べる
・男性mと女性wをペアにする
・ペア(m, w)を解消する
など。
※もっと厳密にやると、チューリング機械を使う。
38
入力xに対する、アルゴリズムAの計算量： f A (x)
Aがxを処理し終えるまでにかかるステップ数。
例
入力 x：
1:
2:
3:
4:
5:
c
a
a
b
d
e
b
d
e
a
a
c
c
d
e
d
d
e
a
b
b
e
b
c
c
a:
b:
c:
d:
e:
4
5
2
3
3
1
1
3
4
1
3
2
1
2
5
2
3
5
5
2
5
4
4
1
4
に対して、Ａが前ページで規定した操作を134回行ったら、
この入力に対するＡの計算量は134。
入力長nに対する、アルゴリズムAの計算量： f A (n)
長さがnである入力全てに対するAの計算量の中の最大値。
f A (n) = max f A (x)
| x| = n
長さnのどんな入力に対しても、Aは f A (n) ステップで終わる。
39
f A (n)
入力長
一般に、 n 2 や 5n などのように、きれいな関数には
ならない。
40
f A (n)
きれいな関数で近似する
（有限個を除いて、全て曲線の下）
入力長
41
漸近的評価
例えば、近似した後、
f A (n) = 2n 3 + 5n + 1.8 log 2 n
だったとしよう。
nの増加に対する計算時間の増加の度合いに着目して、
f A ( n) = O ( n 3 )
と書く。
※nが大きくなると、5n や 1.8 log 2 n は 2n 3 に比べて無視できる。
※「増加の割合」に興味があるので、定数倍は無視する。
厳密な定義は省略。
「最大次の項だけ残して、その項の係数を１にする。」
42
O記法の厳密な定義
2つの関数 f (n), g (n)
f (n) = O( g (n))であるとは、∃c（定数）、∃n（定数）が存在し、
0
∀n(≥ n0 )に対して、f (n) ≤ c ⋅ g (n)であること。
問題：以下のうち正しいものはどれか？正しいものについては、
上記の定義に乗っ取って、厳密に証明せよ。正しくないものに
ついては、正しくないことを証明せよ。
3
(1) 5n 3 + 3n − 10 = O(n 3 ) (2) n − 5 = O(n)
20
(3)0.1n 4 = O(n 2 ) (4) 2n 2 + 2n = O ( n 3 )
43
44
45

Download Report