アルゴリズム入門(1) (アルゴリズムの基礎) 宮崎修一 京都大学 学術情報メディアセンター アルゴリズムとは? 問題を解く手順、算法(あとで具体例) 問題とは? 入力と、それに対する出力がきっちり決まっているもの。 (与えられた入力に対して、正しい出力を計算することを 要求する。) 2 例1:最大公約数を求める問題 入力:正の整数 x と y 出力:x と y の最大公約数 入力 (10, 8) → 出力 2 入力 ( 3, 8) → 出力 1 入力 ( 5,10) → 出力 5 例2:ソーティング(並べ替え) 入力:n個の正の整数 出力:小さい順に並べ替えたもの 入力 10,9,2,6,4,1,8,3 ↓ 出力 1,2,3,4,6,8,9,10 3 もっと身近(実用的)な例 ・文字列検索 入力:文章と検索文字列 出力:文章中で文字列が含まれる位置 4 ・メールソフトの並べ替え 入力:たくさんのメール 出力:指定された順序に従った並べ替え 5 ・WEBページ検索 入力:キーワード 出力:キーワードに関係の深いWEBページ 6 アルゴリズムの例(最大公約数を求める問題) ユークリッドの互除法 (世界最古のアルゴリズム) 入力 x, y (x>y) ステップ 1: x を y で割って、余りを r とする。 ステップ 2: r = 0 ならば、y を出力して終了。 r ≠ 0 ならば、ステップ3へ。 ステップ 3: x ← y (y を x に代入) y ← r (r を y に代入) ステップ1へ。 7 ユークリッドの互除法の動作例 入力 (10, 8) x ステップ 1: ステップ 2: ステップ 3: ステップ 1: ステップ 2: 10÷8=1 余り2。 r=2。0でないのでステップ3へ。 x=8、y=2。ステップ1へ。 8÷2=4 余り0。 r=0なので終了。 このとき、y =2なので、2を出力。 y r (10, 8) 2 (8, 2) 0 8 ユークリッドの互除法の動作例 入力 (8, 3) x ステップ 1: ステップ 2: ステップ 3: ステップ 1: ステップ 2: ステップ 3: ステップ 1: ステップ 2: 8÷3=2 余り2。 r=2。0でないのでステップ3へ。 x=3、y=2。ステップ1へ。 3÷2=1 余り1。 r=1。0でないのでステップ3へ。 x=2、y=1。ステップ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 ステップ 1: 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。 ステップ3では、y と r を新しい x と y にして、ステップ1に戻る。 → y と r の最大公約数を求めに行っている。 要約すると: r =0 ならば y が答で、それをステップ2で出力する。 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 アルゴリズムは、正しい答を出力するか、または、答を保存する ことは分かった。 ↓ つまり、出力したときは、それが正しい答であることは保証される。 ↓ しかし、これだけでは、常に答を出力することの保証にはなって いない。(無限に答を保存し続ける可能性がある) 停止性の証明: ステップ 1: x を y で割って、余りを r とする。 なので、r < y ステップ3で、x ← y, y ← r のときに、yの値は必ず小さくなる。 しかし、絶対に負にはならないので、どこかの時点で必ず0になる。 ↓ アルゴリズムは必ず終了する。 14 アルゴリズムとプログラム アルゴリズムは、計算の手順を書いたもの。(たとえば、日本語、 英語など。) プログラムは、それが計算機上で実行できるように 具体的なプログラミング言語(例えばC、JAVAなど)で書いたもの。 アルゴリズム プログラム ステップ 1: x を y で割って、余りを r とする。 ステップ 2: r = 0 ならば、y を出力して終了。 r ≠ 0 ならば、ステップ3へ。 ステップ 3: x ← y (y を x に代入) y ← r (r を y に代入) ステップ1へ。 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 別の例 安定結婚問題 お見合いパーティー 参加者 男子: 1, 2, 3, 4, 5 女子: a, b, c, d, e パーティー終了後に、5組のカップルを作りたい。 これを、「マッチング」と言う。 各参加者に、希望を出してもらう。 17 安定結婚問題 男子: 1, 2, 3, 4, 5 女子: 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秒間に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つ) 問題に対して、できるだけ早いアルゴリズムを構築する。 1.5 3 2 →n →n →n → … n n 2 → 1.8 → 1.7n → 1.4n → … n5 ・・・ 1.618n [Monien, Speckenmeyer,79] 1つの例: 3SAT 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 | と書く。 操作の単位: 1ステップでどういう操作ができるか。 例えば安定結婚問題では、 ・男性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 に対して、Aが前ページで規定した操作を134回行ったら、 この入力に対するAの計算量は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 に比べて無視できる。 ※「増加の割合」に興味があるので、定数倍は無視する。 厳密な定義は省略。 「最大次の項だけ残して、その項の係数を1にする。」 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
© Copyright 2025 ExpyDoc