アルゴリズム論

同義語:アルゴリズムの理論theory of algorithms

概要

アルゴリズム論(theory of algorithms)とは、問題を機械的な手順で解く方法を設計し、その手順が正しいことと、どれだけの手間で終わるかを数学的に示す分野である。分割統治・動的計画法・貪欲法・探索・乱択・近似が設計の型で、手間は入力の大きさ $n$ の関数として定数倍を除いて評価する。上界は手順を 1 つ作れば示せるが、下界はすべての手順についての主張である。たとえば相異なる $n$ 個の数の整列は、併合整列で $n\lceil\log_2n\rceil$ 回以下の比較で終わり、比較だけを使う手順はどれも最悪で $\lceil\log_2n!\rceil$ 回以上の比較を要する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ, Landau記号

アルゴリズム論(theory of algorithms)とは、問題を機械的な手順で解く方法を設計し、その手順が正しいことと、どれだけの手間で終わるかを数学的に示す分野である。中心の問いは、与えられた問題を解く手順をどう作るか、その手順の手間はいくらか、そして、どんな手順でもこれ以上は速くできないという限界はどこにあるか、である。
この記事は分野の地図である。設計の型と代表的な結果を表にして、それぞれの記事へ案内する。続いて、上界と下界が釣り合う典型として、整列に必要な比較の回数を完全に証明する。

定義

アルゴリズムの語は、9 世紀のペルシアの学者 al-Khwārizmī の名に由来する(Eri19 pp. 1–2)。数学の対象としては次のように定める。

アルゴリズムと計算時間

問題 とは、入力の集合 $I$ と、各入力 $x\in I$ に対して許される出力の集合 $S(x)$ の組である。アルゴリズム とは、定められた基本操作の列を曖昧さなく指定する手順で、どの入力 $x$ に対しても有限回の操作で止まり、$S(x)$ の元を出力するものである。各入力に大きさ $n$ を定めたとき、大きさ $n$ の入力全体にわたる基本操作の回数の上限 $T(n)$ を、そのアルゴリズムの 最悪時の計算時間 という。

何を基本操作として数えるかは問題に合わせて決める(Eri19 §0.6、pp. 14–17)。整列なら比較の回数、グラフの探索なら頂点と辺をたどる回数を数える。計算のモデルを Turing機械 に固定して問題そのものを分類するのが 計算量理論 で、アルゴリズム論はその上で個々の問題の手順を作って手間を評価する。
手間は定数倍を無視して比べる。$T(n)=O(g(n))$ は、ある $C>0$ について十分大きいすべての $n$ で $T(n)\le Cg(n)$ となることを表す(Landau記号)。逆向きの不等式 $T(n)\ge cg(n)$($c>0$)を $T(n)=\Omega(g(n))$ と書き、両方が成り立つことを $T(n)=\Theta(g(n))$ と書く。上界 は 1 つの手順を作れば示せるが、下界(どの手順もこれより速くない)はすべての手順についての主張であり、示し方が根本的に違う。

手間の見積もり方

分割統治の手間は漸化式で表される。問題を大きさ $n/b$ の問題 $a$ 個に分け、分割と結合に $f(n)$ の手間がかかるなら、$T(n)=aT(n/b)+f(n)$ である。再帰の木の各段の手間を足すと解が分かる(Eri19 §1.7、pp. 31–34)。$T(n)=2T(n/2)+O(n)$ では各段の手間がほぼ同じで段数が $\log_2n$ なので $T(n)=O(n\log n)$ である。$T(n)=3T(n/2)+O(n)$ では下の段ほど手間が増え、$T(n)=O(n^{\log_23})$ である。後者は $n$ 桁の整数の積を 4 回ではなく 3 回の半分の桁の積に帰着する Karatsuba の方法の手間で、筆算の $O(n^2)$ より速い(Eri19 §1.9、pp. 40–42)。
入力の大きさの多項式で抑えられる手間を 多項式時間 という。手間が $2^n$ の手順は、$n$ が 1 増えるごとに手間が 2 倍になるので、$n$ が少し大きくなると計算機の速さでは補えない。そこで、多項式時間の手順があるかどうかが、問題の解きやすさの最初の目安になる(計算量理論、P対NP問題)。整数を入力とするときは、大きさは値ではなく桁数で測る。

主な問題と結果の一覧

手順を作る

設計の型考え方代表的な結果入る記事
分割統治半分の大きさの問題に分けて解き、答えをつなぐ長さ $N=2^m$ の離散 Fourier 変換は乗法 $\frac N2\log_2N$ 回以下で計算できる高速Fourier変換
動的計画法部分問題の答えを表に記録して再利用する最適な決定の列の後半はそれ自身最適である動的計画法、動的計画法と最適制御
貪欲法そのつど最善に見えるものを選ぶ重みがどんな非負の値でも貪欲法が最適になるのは、制約がマトロイドをなすときに限る組合せ最適化、マトロイド、Rado–Edmondsの定理、最小全域木
探索頂点をたどり、訪問済みを記録する幅優先・深さ優先の探索は頂点数 $V$ と辺数 $E$ について $O(V+E)$ 時間で終わる(Eri19 §5.6、pp. 201–202)幅優先探索、深さ優先探索、位相的整列
乱択手順の中で乱数を使うMiller–Rabin の判定で、$k$ 個の独立な底を使えば合成数を素数と誤る確率は $4^{-k}$ 以下であるMiller-Rabin素数判定法
近似最適解をあきらめ、最適値の定数倍以内を保証する(WS11 §1.1 の Definition 1.1)費用が三角不等式を満たす巡回セールスマン問題に $3/2$-近似の手順がある巡回セールスマン問題

個々の問題の手順

問題代表的な結果入る記事
最大公約数$a$ を $b$ で割って始める互除法の割り算の回数は、$b$ の 10 進桁数の 5 倍を超えない(Lamé の定理)Euclidの互除法
最短路長さが $0$ 以上なら、二分ヒープを使う Dijkstra 法は頂点 $n$ 個・辺 $m$ 本で $O((n+m)\log n)$ 回の基本操作で終わるDijkstra法
最大流最短の増加道を選ぶと、増加の回数は頂点の個数と弧の本数の積以下であるEdmonds–Karp法、ネットワークフロー
マッチング孤立点のない一般のグラフの最大マッチングは、奇閉路を 1 点に縮める方法で $O(n^2m)$ 時間で求まるEdmondsの花アルゴリズム
割り当てハンガリー法は、費用が整数なら有限回で止まって最適な割り当てを与える割当問題
整列比較による整列の手間は $\Theta(n\log n)$ であるこの記事の thm-alg-merge と thm-alg-lower

正しさと限界を示す

問い代表的な結果入る記事
手順が正しいことをどう示すか正しさは、止まれば答えが合うこと(部分正当性)と止まること(停止性)に分かれるアルゴリズムの正しさ(部分正当性と停止性)
手順が存在しない問題はあるか自己停止集合は決定可能でない計算可能性理論
手順はあるが速くならない問題はあるか時間を十分に増やすと判定できる言語が増え、$\mathrm{P}\ne\mathrm{EXP}$ である計算量理論
難しさをどう比べるか論理式の充足可能性の問題は NP完全である(Cook–Levinの定理)NP完全

具体例:整列に必要な比較の回数

相異なる $n$ 個の実数 $a_1,\dots,a_n$ を小さい順に並べる 整列 の問題を考える。出力は、$a_{\sigma(1)}< \dots< a_{\sigma(n)}$ となる置換 $\sigma$ である。「$a_i< a_j$ か」という比較 1 回を基本操作とする。
併合整列(mergesort)は分割統治の手順である(Eri19 §1.4、pp. 26–29)。$n\ge2$ なら列を長さ $\lfloor n/2\rfloor$ と $\lceil n/2\rceil$ の 2 つに分け、それぞれを同じ手順で整列し、2 つの整列済みの列の先頭どうしを比べて小さい方を取り出すことをくり返して併合する。長さ $p$ と $q$ の列の併合は、比較 1 回ごとに 1 個が取り出され、片方が空になれば比較なしで終わるので、比較は $p+q-1$ 回以下である。

併合整列の上界

$n\ge1$ のとき、併合整列の比較の回数の最大値 $T(n)$ は $n\lceil\log_2n\rceil$ 以下である。

$n$ についての帰納法で示す。$T(1)=0$ である。$n\ge2$ とし、$k:=\lceil\log_2n\rceil\ge1$ とおくと $n\le2^k$ なので、分けた 2 つの列の長さはどちらも $\lceil n/2\rceil\le2^{k-1}$ 以下である。帰納法の仮定($T(m)\le m\lceil\log_2m\rceil\le m(k-1)$、$m\le2^{k-1}$)により
$$ T(n)\le T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+(n-1)\le n(k-1)+n-1< nk $$
である。$\square$

比較による整列の下界

$n\ge2$ とする。比較だけで入力の大小を調べ、乱数を使わない整列のアルゴリズムは、ある入力に対して少なくとも $\lceil\log_2n!\rceil$ 回の比較を行う。さらに $\log_2n!\ge\frac n2\log_2\frac n2$ である。

どの入力に対しても比較が $d$ 回以下で終わるとする。アルゴリズムの動きは、比較の結果の列だけで決まる。実際、1 回目に行う比較は入力によらず、$t$ 回目までの結果が同じ 2 つの入力に対しては次に行う比較も同じであり、止まるかどうかと出力も同じである。結果の列を長さ $d$ に伸ばす(止まったあとは「はい」を並べる)と、列の個数は $2^d$ 以下である。
一方、入力の大小の順序は $n!$ 通りあり($\{1,\dots,n\}$ の置換を入力とすればよい)、相異なる数の列を整列する置換 $\sigma$ は入力の順序ごとに 1 つに決まって異なるので、$n!$ 通りの入力はそれぞれ別の出力を要する。よって別々の結果の列を生じ、$n!\le2^d$ すなわち $d\ge\log_2n!$ である。$d$ は整数なので $d\ge\lceil\log_2n!\rceil$ である。
最後の不等式は、$n!$ の因数のうち大きい方の $\lceil n/2\rceil$ 個がどれも $n/2$ 以上であることから、$n!\ge(n/2)^{\lceil n/2\rceil}\ge(n/2)^{n/2}$($n\ge2$)となることによる。$\square$

2 つの定理から、比較による整列の最悪の比較回数の最小値は $\Theta(n\log n)$ である。

小さい場合

併合が $n-1$ 回の比較を要するのは最大の 2 個が別々の列にあるときで、これは 2 つの列それぞれの中の順序とは独立に選べる。よって比較の回数の最大値は漸化式 $T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+n-1$ で求まり、$T(2)=1$、$T(3)=3$、$T(4)=5$、$T(5)=8$ である。下界は $\lceil\log_224\rceil=5$、$\lceil\log_2120\rceil=7$ である。$n=4$ では併合整列が下界に達し、$n=5$ では 1 回の差が残る。

反例:条件を外すと成り立たないこと

thm-alg-lower は「比較だけを使う」手順についての主張であり、この条件は外せない。貪欲法も、いつでも使えるわけではない。

主張反例成り立たない理由
どの整列も $\Omega(n\log n)$ 回の操作を要する入力が $\{1,\dots,n\}$ の置換 $a$ なら、配列に $b[a_i]:=i$ と書くだけで $\sigma=b$ が $n$ 回の代入で求まる値を番地として使い、比較を使っていない
硬貨の枚数を最小にするには大きい額面から貪欲に取ればよい額面 $1,3,4$ で金額 $6$:貪欲法は $4+1+1$ の 3 枚、最適は $3+3$ の 2 枚最初の選択を変えると全体が良くなる。部分問題を全部調べる動的計画法なら正しい答えが出る

1 行目の手順は比較を 1 回も使わないので、thm-alg-lower に反しない。手順の良し悪しは、計算のモデルと入力の範囲を決めて初めて比べられる。

読み進め方

段階記事身につくこと
1. 記法と対象Landau記号、グラフ → アルゴリズムの正しさ(部分正当性と停止性)手間の書き方、正しさの示し方
2. 基本の手順Euclidの互除法、幅優先探索、深さ優先探索 → 位相的整列停止の議論、探索の型
3. グラフの最適化最小全域木、Dijkstra法 → ネットワークフロー → Edmondsの花アルゴリズム貪欲法の正しさ、増加道の考え方
4. 限界計算可能性理論 → 計算量理論 → NP完全 → P対NP問題解けない問題、難しい問題
5. 難しさとの付き合い方巡回セールスマン問題、整数計画法近似と場合分けの限定

段階 2 と段階 3 の記事は Turing 機械を使わないので、段階 4 より先に読める。

未解決問題

  • P 対 NP 問題:答えの証拠を多項式時間で確かめられる問題が、すべて多項式時間で解けるかは未解決である(P対NP問題)。thm-alg-lower は操作を比較に制限したモデルでの下界であり、一般の手順についての下界はこれと別の問題である。

関連項目

参考文献

[1]
Jeff Erickson, Algorithms, Independently published, 2019, §0.1(語源、pp. 1–2)、§0.6 Analyzing Algorithms(pp. 14–17)、§1.4 Mergesort(pp. 26–29)、§1.7 Recursion Trees(pp. 31–34)、§1.9 Fast Multiplication(pp. 40–42)、§5.6 Important Variants(pp. 201–202)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する