← 研修トップ
アルゴリズムの手法 — CLRS を読むための地図
速いアルゴリズムは、問題が持っている構造を1つ使っています。手法の名前を覚える前に、何を前提にしているかを読む。ループ不変式・分割統治・乱択・比較しない整列・ヒープ・動的計画法・貪欲法・Dijkstra・Bellman-Ford・最小全域木・最大フロー・文字列照合・NP 完全を、証明ではなく「前提」と「10行の Python で手で確かめる」で13本。原論文と、実物(CPython・Go・PostgreSQL・RFC・NumPy)の公式文書から積み上げます。『アルゴリズムイントロダクション』(CLRS)を開く前の地図として。
- 1約 9 分正しさは「毎周守られる約束」で言う — ループ不変式テストが全部通っても、分かるのは「試した入力では動いた」までです。ループが正しいと言うには、各周の始めに成り立つ約束(ループ不変式)を1つ決め、①最初に成り立つ ②1周回っても保たれる ③終わったときにそれが答えを意味する、の3つで言います。
- 2約 8 分分けて、解いて、合わせる — 仕事は段ごとに数える分割統治の計算量は「再帰の木を段ごとに見て、各段の仕事を足す」と読めます。段数は、半分ずつにするなら log₂ n です。
- 3約 9 分最悪の入力を、乱数の側へ移す — 乱択と期待値先頭を基準(pivot)にするクイックソートは、ソート済みの500件を渡されると 124,750 回比べます。最悪の入力が決まっていて、それを渡されたら遅いのです。
- 4約 9 分キーの形を知っていれば床をくぐれる — 比較しない整列比較ソートの(平均の)下限は「2つを比べる」以外の情報を使わない、という前提の上に立っています。キーが「狭い範囲の整数」や「桁に分けられる値」だと分かっていれば、比べずに置き場所を直接計算でき、床の外に出られます。
- 5約 9 分配列に詰めた木 — ヒープは添字で親子をたどるヒープは、隙間の無い二分木を上の段から左詰めで配列に並べた構造です。そうすると k 番の子は 2k+1 と 2k+2、親は (k-1)//2 と、添字の計算だけで決まります。ポインタも、節点を作り直す手間も要りません。
- 6約 9 分部分問題を定義し、依存の順に表を埋める — 動的計画法動的計画法の仕事は「部分問題を何と定義するか」でほぼ決まります。定義できれば、答えは小さい部分問題の答えから組み立てる式になり、あとは表を埋めるだけです。
- 7約 9 分1手目を入れ替えても損しないとき — 貪欲法と交換論法貪欲法は「いま一番良く見える手を取り続ける」だけの手法です。速く、書くのも簡単です。
- 8約 9 分最も近いものから確定する — Dijkstra 法は負の辺が無いことを使うDijkstra 法は「まだ確定していない頂点のうち、始点にいちばん近いものは、もうこれ以上近くならない」と言い切って、その頂点を1つずつ確定していきます。そう言い切れる根拠は、辺の重みが負でないことだけです。
- 9約 9 分確定できないなら、全部の辺を回数分ゆるめる — Bellman-Ford 法負の辺があると「いま一番近い頂点の距離はもう下がらない」と言えなくなり、近い順に確定していく手が使えません。代わりに、全部の辺を順にゆるめる周回を V−1 回繰り返します(V は頂点の数)。
- 10約 9 分カットを渡る最も軽い辺は使ってよい — 最小全域木頂点を2つの側に分ける切れ目(カット)を1つ決めると、そこを渡る辺のうち最も軽いものは、どれかの最小全域木に必ず入っています。
- 11約 9 分流せる量は一番細い切れ目で決まる — 最大フロー=最小カット源 s から先 t へ同時に流せる量は、頂点を s 側と t 側に分けたとき「s 側から t 側へ渡る辺の容量の和」(カットの容量)を超えられません。しかも最小のカットの容量にちょうど届きます。同じ関係を、Ford と Fulkerson は 1956 年の論文で(向きのない網と、辺の集まりとしてのカットで)minimal cut theorem として示しました。
- 12約 9 分一致した分を捨てない — 文字列照合と失敗関数素朴な文字列照合は、食い違うたびに本文を戻って読み直します。KMP 法はパターンの「頭と尻の重なり」を前もって表(失敗関数)にしておき、本文を一度も戻りません。
- 13約 9 分還元は難しさを運ぶ — NP 完全と「速く解けない」の意味「NP 完全」は「解けない」という意味ではありません。NP に属するどの問題もこれに言い換え(還元)られるので、これが速く解けたら全部が速く解ける、という位置づけです。