アルゴリズム入門（1）

宮崎修一

京都大学 学術情報メディアセンター

アルゴリズム入門（ 1 ）

（アルゴリズムの基礎）

アルゴリズムとは？

問題を解く手順、算法（あとで具体例）

問題とは？

入力と、それに対する出力がきっちり決まっているもの。

（与えられた入力に対して、正しい出力を計算することを 要求する。）

3

例１：最大公約数を求める問題 入力：正の整数 x と y

出力：x と y の最大公約数

入力 （１０， ８） → 出力 ２ 入力 （ ３， ８） → 出力 １ 入力 （ ５，１０） → 出力 ５ 例２：ソーティング（並べ替え）

入力：n個の正の整数

出力：小さい順に並べ替えたもの

入力 １０，９，２，６，４，１，８，３

↓

出力 １，２，３，４，６，８，９，１０

もっと身近（実用的）な例

・文字列検索

入力：文章と検索文字列

出力：文章中で文字列が含まれる位置

5

・メールソフトの並べ替え 入力：たくさんのメール

出力：指定された順序に従った並べ替え

・ＷＥＢページ検索 入力：キーワード

出力：キーワードに関係の深いＷＥＢページ

7

アルゴリズムの例（最大公約数を求める問題）

ユークリッドの互除法 （世界最古のアルゴリズム）

入力 x, y (x>y)

ステップ １： x を y で割って、余りを r とする。

ステップ ２： r = 0 ならば、y を出力して終了。

r ≠ 0 ならば、ステップ３へ。

ステップ ３： x ← y （y を x に代入）

y ← r （r を y に代入）

ステップ１へ。

ユークリッドの互除法の動作例 入力 (10, 8)

ステップ １： 10÷8=1 余り2。

ステップ ２： r=2。0でないのでステップ３へ。

ステップ ３： x=8、y=2。ステップ１へ。

ステップ １： 8÷2=4 余り0。 ステップ ２： r=0なので終了。

このとき、y =2なので、2を出力。

x y r (10, 8) 2

(8, 2) 0

9

ユークリッドの互除法の動作例 入力 (8, 3)

ステップ １： 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を出力。

x y r

(8, 3) 2 (3, 2) 1 (2, 1) 0

ユークリッドの互除法は、入力(10, 8)や(8, 3)に対しては 正しく動作することが分かった。

しかし、アルゴリズムは、どんな入力に対しても正しく動作 しなければならない。

どんな入力に対しても正しく動作することの証明 入力 x, yに対して、正しい答を d とする。

（つまり、x = ds, y = dt で、sとtは互いに素）

11

ステップ １： 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が互いに素である ことに反する。

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 の最大公約数を求めに行く。

（答を保存している。）

13

例えば(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

アルゴリズムは、正しい答を出力するか、または、答を保存する ことは分かった。

↓

つまり、出力したときは、それが正しい答であることは保証される。

↓

しかし、これだけでは、常に答を出力することの保証にはなって いない。（無限に答を保存し続ける可能性がある）

停止性の証明：

ステップ １： x を y で割って、余りを r とする。

なので、r < y

ステップ３で、x ← y, y ← r のときに、yの値は必ず小さくなる。

しかし、絶対に負にはならないので、どこかの時点で必ず0になる。

↓

アルゴリズムは必ず終了する。

15

ステップ １： x を y で割って、余りを r とする。

ステップ ２： r = 0 ならば、y を出力して終了。

r ≠ 0 ならば、ステップ３へ。

ステップ ３： x ← y （y を x に代入）

y ← r （r を y に代入）

ステップ１へ。

アルゴリズムとプログラム

アルゴリズムは、計算の手順を書いたもの。（たとえば、日本語、

英語など。） プログラムは、それが計算機上で実行できるように 具体的なプログラミング言語（例えばC、JAVAなど）で書いたもの。

while(r!=0) {r:=x;

for (r>=y) {r:=r-y;}.

x:=y; y:=r;}

print(y);

アルゴリズム プログラム

問題

:

次の

2

(a) 1470

63

(b) 89

55

17

安定マッチング問題 就職斡旋会

参加者

学生：

１ , ２ , ３ , ４ , ５

a, b, c, d, e

イベント終了後に、

5

これを、「マッチング」と言う。

各参加者に、希望を出してもらう。

別の例

1: c e a d b a: 4 1 3 2 5 2: a b c d e b: 5 1 2 3 4 3: a d c e b c: 2 3 1 5 4 4: b e d a c d: 3 4 2 5 1 5: d a e b c e: 3 1 5 2 4

安定マッチング問題 学生：

１ , ２ , ３ , ４ , ５

a, b, c, d, e

それぞれの人は、左から右に向かって、好きな 相手を順番に書いている。

19

例

1: c e a d b a: 4 1 3 2 5 2: a b c d e b: 5 1 2 3 4 3: a d c e b c: 2 3 1 5 4 4: b e d a c d: 3 4 2 5 1 5: d a e b c e: 3 1 5 2 4

これは、なかなか良い。全員が第3位以内とペアになっている。

全員が第2位以内とペアになるマッチングは存在しない。

問題：なぜ？

例

1: c e a d b a: 4 1 3 2 5 2: a b c d e b: 5 1 2 3 4 3: a d c e b c: 2 3 1 5 4 4: b e d a c d: 3 4 2 5 1 5: d a e b c e: 3 1 5 2 4

ところが、このマッチングには欠点がある。

(1, e)は、今の相手よりお互いが好き。今のマッチングに

逆らって、「駆け落ち」する可能性がある。

こういうペアを「ブロッキングペア」と呼ぶ。

ブロッキングペアがあるとマッチングが壊れる → 不安定 問題：何が欠点？

ブロッキングペアのないマッチング：安定マッチング

21

1: c e a d b a: 4 1 3 2 5 2: a b c d e b: 5 1 2 3 4 3: a d c e b c: 2 3 1 5 4 4: b e d a c d: 3 4 2 5 1 5: d a e b c e: 3 1 5 2 4

問題： この例に対する安定マッチングを求めよ。

22

安定マッチングはどういうところで使われているの？

例：大学での研究室配属

研究室A（定員3名）

アルゴリズム

研究室B（定員4名）

インターネット

研究室C（定員3名）

画像処理

。。。

aさん bさん cさん

eさん dさん

。。。

a: A D B C b: E A B D c: F B C A d: B A C F e: C B F C

A: g f c b a e …

B: d b c a f e g …

C: b e d c f e a …

どの研究室に行きたいかの

希望リストを書く どの学生に来て欲しいかの 希望リストを書く

これらの希望リストを使って 安定マッチングを求める

23

例：日本の研修医マッチング（JRMP) https://www.jrmp.jp/

2004年にスタート（アメリカでは1950年代から）

8,500人の研修医を1,000病院の10,000～11,000ポストに配属 医学部を卒業して医師国家試験に合格した医師は、2年間

どこかの病院で研修を行う。どの病院に行くかの配属を決めるもの。

25

例：腎臓交換移植

Aさんが腎臓病の息子aの ために腎臓を提供したいが、

型が合わない。

Bさんが腎臓病の弟bの

ために腎臓を提供したいが、

型が合わない。

A

a

B

b

× ×

ところが、Aさんがbさんに、Bさんがaさんにだったら 型が合う。

このとき、A-a と B-b で腎臓を交換して移植すると、

どちらもハッピー。

例：腎臓交換移植 A

a

B

b

× ×

C

c

D

d

× ×

E

e

F

f

× ×

Y

y

×

Z

z

×

B

b

×

D

d

×

移植したいけど型が合わない（不幸な）ペア

C

c

×

Y

y

×

F

f

×

Z

z

×

ペア同士のペア（マッチング）を作って交換する。

これまで助からなかった者が助かる。

27

2012

Lloyd S. Shapley

安定配分の理論とマーケットデザインの実践

・安定マッチングの理論研究

・その結果を世の中のマッチングに応用

（研修医配属、学校配属、腎臓交換移植など）

Alvin E. Roth

素朴な疑問

さっきの例には「たまたま」

安定マッチングがあったが、

どんな場合でも安定 マッチングはあるの？

・誰かの希望リストが今のと違っていたら？

・今の例は5人対5人だったが、10人対10人では？

100人対100人では？

安定マッチングは必ずある。人数がどれだけ増えても、

どんな希望リストであっても、必ずある。

1: c e a d b a: 4 1 3 2 5 2: a b c d e b: 5 1 2 3 4 3: a d c e b c: 2 3 1 5 4 4: b e d a c d: 3 4 2 5 1 5: d a e b c e: 3 1 5 2 4

29

単純なアルゴリズム：

マッチングを全て求めて、それぞれが安定かどうかを 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

…

安定なマッチングが見つかった所で、それを出力する。

安定マッチングを求めるには、どうしたらいいか？

全部のマッチングを調べているので、必ず答は求まる。

計算時間は、どれぐらい掛かるだろうか？

問題：学生5人、採用担当5人の場合、マッチングは何通りある？

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

…

ここの異なる順列に、異なるマッチングが 1対1に対応するので、全部で5!(=120)通り。

学生n人、会社n個だと n! 通り。

31

宇宙の年齢≒138億年 ＜ 10¹¹年 1時間 ＝ 3,600秒

1日 ＝ 86,400秒

1年 ＝ 31,536,000秒 ＜ 10⁸ 秒

1秒間に1億(=10 )個のマッチングを生成し、

その安定性をチェックできたとしても、10³²秒以上かかる。

8

10³²秒 > 10²⁴年 n!ってどれぐらい？

n 1 2 … 5 … 10 … 50

n! 1 2 120

50! > 1040

宇宙の年齢の10,000,000,000,000回分待っても答えが出ない。

3,628,800 50!

1: c e a d b a: 4 1 3 2 5 2: a b c d e b: 5 1 2 3 4 3: a d c e b c: 2 3 1 5 4 4: b e d a c d: 3 4 2 5 1 5: d a e b c e: 3 1 5 2 4

32

安定マッチングを求める Gale-Shapley アルゴリズム

×

× ×

×

問題：どうしてこのアルゴリズムで安定マッチングが求まる？

もっと速く求めることはできないか？

n ² ステップで終わる

33

求まったマッチングが安定でないとすると、

ブロッキングペアが存在する。

2: ・ ・ ・ e ・ ・ ・ e: ・ ・ ・ 2 ・ ・ ・ 学生2は会社eに申請したが断られた。

（学生はリストの前から順番に申請するので）

e: ・ ・ ・

×

その時点では、会社eは学生2よりも良い人を得ていた。

それ以後、会社が相手を変える場合は、

より良い相手にしか変えない。

最終的に学生2より下の会社とペアになっているのは矛盾。

(証明終わり)

×

(安定性の証明)

n 1 2 … 5 … 10 … 50

n 1 4 25 100 2,500

n! 1 2 120 3,628,800 > 10

2

1秒間に1億個のマッチングを生成し、その安定性をチェック できたとしても、10³²秒＞ 10 ²⁴年かかる

宇宙の年齢≒138億年 ＜ 10¹¹年

1秒間に１億ステップ計算できるなら、

0.000025秒で終わる

40

35

アルゴリズムの時間計算量

できるだけ速く答を求めるアルゴリズム＝良いアルゴリズム。

n ² < 2ⁿ < n! (≈ )

多項式時間アルゴリズム（n ^c の形のもの）

指数時間アルゴリズム（c ⁿ の形のもの）

超指数時間アルゴリズム 効率の良い

アルゴリズム

「フカシギの数え方」

計算時間の爆発、アルゴリズムの効率を題材にした動画

JST ERATO

湊離散構造処理系プロジェクト

「アルゴリズムが世界を変える」

JST ERATO

河原林巨大グラフプロジェクト

37

アルゴリズム研究（の１つ）

問題に対して、できるだけ早いアルゴリズムを構築する。

[Rolf,05]

32216 .

1

Tamaki,04]

[Iwama, )

3227 .

1 ( 3238 .

1

[Rolf,03]

3280 .

1

] Schuler,03 [Baumer,

3290 .

1

al.,02]

et r [Hofmeiste 3302

. 1

,99]

[Schoening 334

. 1

al.,98]

et [Paturi 362

. 1

er,79]

Speckenmey [Monien,

618 . 1

n

n n

n n n n n n

・・・

n⁵ → n³ → n² → n^1.5 → …

2 → 1.8 → 1.7 → 1.4 → …^{n n n n}

１つの例：

３ＳＡＴ

[Iwama, Takai, Seto, Tamaki,10]

32113 .

1 ⁿ

[Hertli, Moser, Scheder , 10]

32065 .

1 ⁿ

[Hertli,11]

30704 .

1 ⁿ

38

計算量のより厳密な話

入力の「サイズ」：

入力の長さ。

例えば安定マッチング問題では、希望リストの長さの総和。

入力xの長さを | x | と書く。

操作の単位：

１ステップでどういう操作ができるか。

例えば安定マッチング問題では、

・学生mの第i希望がどの会社であるか調べる

・学生mと会社wをペアにする

・ペア(m, w)を解消する など。

※もっと厳密にやると、チューリング機械を使う。

39

入力xに対する、アルゴリズムAの計算量：

Aがxを処理し終えるまでにかかるステップ数。

例

入力 x：

に対して、Ａが前ページで規定した操作を134回行ったら、

この入力に対するＡの計算量は134。 入力長nに対する、アルゴリズムAの計算量：

長さがnである入力全てに対するAの計算量の中の最大値。

) (x f_A

) (n f_A

max

f

( x )

= ) (n f

長さnのどんな入力に対しても、Aは f_A(n)ステップで終わる。

1: c e a d b a: 4 1 3 2 5 2: a b c d e b: 5 1 2 3 4 3: a d c e b c: 2 3 1 5 4 4: b e d a c d: 3 4 2 5 1 5: d a e b c e: 3 1 5 2 4

40

入力長

) (n f_A

一般に、 や などのように、きれいな関数には ならない。

n2 5n

41

入力長

) (n f_A きれいな関数で近似する

（有限個を除いて、全て曲線の下）

漸近的評価

n n

n n

f_A( ) = 2 ³ +5 +1.8log₂ 例えば、近似した後、

だったとしよう。

nの増加に対する計算時間の増加の度合いに着目して、

と書く。

) ( )

(n O n³ f_A =

※nが大きくなると、 や は に比べて無視できる。

※「増加の割合」に興味があるので、定数倍は無視する。

2n3 2 n

log 8 . n 1

5

厳密な定義は省略。

「最大次の項だけ残して、その項の係数を１にする。」

43

O記法の厳密な定義

) ( ),

(n g n 2つの関数 f

であること。

に対して、

（定数）が存在し、

（定数）、

であるとは、

) ( )

( )

(

)) ( ( )

(

0

0

n g c n

f n

n

n c

n g O n

f













=

問題：以下のうち正しいものはどれか？ 正しいものについては、

上記の定義に乗っ取って、厳密に証明せよ。正しくないものに ついては、正しくないことを証明せよ。

) ( 2

2 ) 4 ( )

( 1

. 0 ) 3 (

) ( 20 5

) 3 2 ( )

( 10

3 5

) 1 (

3 2

2 4

3 3

n O n

n n

O n

n O n

n O n

n

= +

=

=

−

=

− +

45