アルゴリズムとは？ -What Is Algorithm?

まずは, アルゴリズムの定義を述べよう.

Definition 1.1. アルゴリズム(algorithm)

与えられたデータから目的の情報を見つけ出したり, 作り出したりするための手続きをアルゴリズム (algorithm) という.

百聞は一見に如かず. 具体的なアルゴリズムを以下に示そう(このように記述されたものを疑似コード(pseudocode)という).

Algorithm ${\rm MAX}(x_1, x_2, \cdots, x_n)$ (p.3より)

入力: 正の実数 $n, n$ 個の実数 $x_1, x_2, \cdots, x_n$ .
出力: $x_1, x_2, \cdots, x_n$ の最大値.
手続き:
1. $y$ ← $x_1$ ;
　(注: $y$ は「それまでに見た数の中の最大値」を表す. )
2. for $i$ ← $2$ until $n$ do
　　if $x_i > y$ then $y$ ← $x_i$ ;
3. return $y$ . $\fbox{}$

次に, 上記の例を用いて, アルゴリズムに関する用語をいくつか紹介する.

用語	説明	例
入力 (input)	アルゴリズムに与えられるデータ	正の実数 $n, n$ 個の実数 $x_1, x_2, \cdots, x_n$
出力 (output)	アルゴリズムによって作り出したい(求めたい)情報	$x_1, x_2, \cdots, x_n$ の最大値
ステップ (step)	アルゴリズム内の一つ一つの手続き	1. $y$ ← $x_1$ ;
コメント (comment)	手続きを理解しやすくするための説明	(注: $y$ は「それまでに見た数の中の最大値」を表す.)

Note 1.2. アルゴリズムを記述する方法 -How to describe algorithms

英語やプログラミングの文法と異なり, アルゴリズムの記述に明確な文法は存在しない. そのため, それぞれの場面や伝えたい相手の知識などに応じて, 曖昧性のない厳密さと, 必要以上の細部は省略する簡潔さとのバランスを考えなければならない.

計算量とは？ -What Is Complexity?

ある目的を達成するためのアルゴリズムは, 当然, 複数存在する. そこで, 「どのアルゴリズムがより優れているか」を判断する指標のようなもの(定量的に求めるための基準)が欲しくなるだろう. 欲を言えば, プログラムに翻訳する前に(つまり, 疑似コードのまま)どちらが優れているかを判断できると, 尚のこと嬉しい.

では, アルゴリズムの優劣を比較する指標となる概念, 「オーダ」について述べよう.

Definition 2.1. オーダ(order)

$n$ を $0$ 以上の整数, $f(n), p(n)$ を自然数上で定義された関数とする. 任意の $n$ に対して

$\frac{f(n)}{p(n)} < C$

を満たすという性質を持った $n$ に依らない定数 $C$ が存在するとき,

$f(n) = {\rm O}(p(n))$

と書いて, 「 $f(n)$ は, $p(n)$ のオーダ(order)である」という.

以降, 具体的なアルゴリズムに関して議論するとき,

$n$ : 入力の大きさ(input size), または問題の大きさ(problem size)
$f(n)$ : 大きさ $n$ の入力に対して, アルゴリズムが結果を出すまでに要する処理時間

として考える.

Note 2.2. アルゴリズムにおけるオーダ -Orders in algorithms

1.については問題ないだろう. 先の例(Algorithm ${\rm MAX}(x_1, x_2, \cdots, x_n)$ )であれば, 入力する変数 $x_1, x_2, \cdots, x_n$ の個数 $n$ がそれに当たる. 2.について, 実は $f(n)$ という関数の具体的な形は分かるわけではない. と言うのも, あるアルゴリズムを

どのようなプログラミング言語で翻訳して,
どのような計算機で実行するのか

によって, 計算時間は変わってしまう. ここでは, 計算環境が定まれば $f(n)$ という関数も定まるだろうと思ってもらえば十分だ.

Definition 2.3. 時間複雑度(time complexity)

アルゴリズム $A$ について, $f(n) = {\rm O}(p(n))$ が成り立つとき, $A$ の時間複雑度(time complexity)は ${\rm O}(p(n))$ であるという.

これは, 最も時間がかかる場合でも, $p(n)$ に比例する計算時間で $A$ は処理を終了する, ということを意味する.

ここで, 代表的な時間複雑度に対する「常識的な評価(pp. 8-9より改変)」をまとめておく.

オーダ	説明
${\rm O}(1)$	理想的に速い. 定数時間で処理が終了することを意味する. オーダの意味ではこれより速いものは望めない
${\rm O}(log\ n)$	非常に速い
${\rm O}(n)$	速い
${\rm O}(n\ log\ n)$	速いと言ってよい. $n$ が小さいとき, ${\rm O}(n)$ とあまり大きな差は見られない
${\rm O}(n^2)$	許されないほどではないが, かなり遅い. アルゴリズムを設計するときは, できるだけこれ以下のオーダで済むように努力をすべきである
${\rm O}(n^3)$	多くの場面で許される限界である. これよりオーダの大きなアルゴリズムは特殊な場合を除いて非実用的である
${\rm O}(c^n)$ ( $c(>1)$ は定数)	指数オーダ(exponential order)と呼ばれる. アルゴリズムと呼ぶのが恥ずかしいくらい遅い

また, 時間と同様に, アルゴリズムの中で使われる記憶領域の大きさもオーダで測ることができる.

Definition 2.4. 空間複雑度(space complexity)

アルゴリズム $A$ が, 大きさ $n$ の入力に対して大きさ $g(n)$ ビットの記憶領域を必要とし, $g(n) = {\rm O}(q(n))$ を満たすとする. このとき, $A$ の空間複雑度(space complexity)は ${\rm O}(q(n))$ であるという.

また, 時間複雑度と空間複雑度を合わせて, 複雑度(complexity)または計算量という.

問題の難しさの測り方 -How to Measure Problems' Hardness

ここまでは問題を解く個別のアルゴリズムの効率に着目してきたが, 以降は問題自身の難しさを測る方法について考える.

Definition 3.1. 判定問題(decision problem), クラスP(class P)

ある問題が, 「イエス」または「ノー」で答える問題であるとき, その問題は判定問題(decision problem)という.
問題の大きさ $n$ の多項式オーダ(polynomial order)のアルゴリズムが存在する判定問題の全体をクラスP(class P)¹という.

Example 3.2. クラスPに属す問題 -Problems belonging to class P

具体的な判定問題としては,

Hamilton閉路問題(Hamilton cycle problem)
クリーク問題(clique problem)
頂点被覆問題(vertex cover problem)
集合被覆問題(set cover problerm)

などが挙げられる. 紙面の都合上, 各問題の詳細について, ここでは言及しない.

例えばHamilton閉路問題は, 現在, 多項式オーダのアルゴリズムは見つかっていない. しかし, そのようなアルゴリズムが存在しないことが証明されているわけでもない. そのため, この問題がクラスPに属するかは, 今のところ不明である.

Definition 3.3. 非決定的計算機(nondeterministic computer), クラスNP(class NP)

処理の分岐に達したとき, 可能な分岐をどの順に処理するかは指定されておらず, 好みの順序で実行できるような(架空の)計算機を非決定的計算機(nondeterministic computer)という.
答が「イエス」のとき, 非決定的計算機によって問題の大きさの多項式時間で答を出すことができるような判定問題の全体をクラスNP(class NP)²という.

Remark 3.4. for Definition 3.3.

(厳密性を欠くことを覚悟の上で言い換えると, )非決定的計算機とは, プロセッサが必要なだけいくらでも使える理想的な並列計算機だと解釈できる.
クラスNPを感覚的に説明すると, 正しい答が与えられたときに, 「その答は正しい」と判定するのにかかる時間が問題の大きさの多項式時間で表せるということである.

Example 3.5. クラスNPに属す問題 -Problems belonging to class NP

Hamilton閉路問題はクラスNPである. 実際, この問題の答が「イエス」の場合, グラフの頂点をある順序で訪問する閉路が存在するから, その閉路の順序に沿って, グラフが辺を持つかを調べれば ${\rm O}(n)$ の時間で処理が終わる.

定義から明らかなように, クラスPはクラスNPに含まれる. また, ミレニアム懸賞問題の1つであるP $\neq$ NP予想(P is not NP)は「NPに属すがPには属さない問題が存在する」という予想である.

Definition 3.6. クラスNP完全(class NP-complete)

判定問題 $Q$ が次の条件1., 2.を満たすとき, $Q$ はクラスNP完全(class NP-complete)に属すという.

$Q$ はクラスNPに属す,
もし $Q$ がクラスPに属せば, クラスNPに属す全ての問題がクラスPに属す.

条件2.は, $Q$ がクラスNPに属す問題の中で最も難しい問題であることを表している. つまり, 問題の難易度に対して, $Q$ が上限のような役割を果たしていると言える.

Definition 3.7. クラスNP困難(class NP-hard)

(判定問題とは限らない)一般の問題 $Q$ に対して, その問題が, クラスNP完全に属す問題 $Q'$ を部分問題として含むとき, $Q$ はクラスNP困難(class NP-hard)に属すという.

Example 3.8. クラスNP困難に属す問題

グラフ $G = (V, E)$ の辺 $e = {v_i, v_j} \in E$ にコストと呼ばれる非負実数 $c(v_i, v_j)$ が指定されているとき, $G$ のHamilton閉路の中でコストの和が最小のものを求めるとする. この問題は行商人問題または巡回セールスマン問題(TSP: traveling salesman problem)と呼ばれ, クラスNP困難に属す.

更に深く学ぶために -To Aim for the Stars

言わずと知れたアルゴリズムの名著. 出版社名からも分かるように, 世界的に有名なマサチューセッツ工科大学(MIT: Massachusetts Institute of Technology)の標準的な教科書である. 余談だが, 情報電気工学科2年次で開講されている「アルゴリズム論Ⅰ」の指定教科書は, 邦訳版の第1巻である(2020年度現在).

T. H. Cormen, C. E. Leiserson and R. L. Rivert: Introduction to Algorithms. The MIT Press, Cambridge, 1990.

次の3冊は, この分野の中心的話題を徹底的に掘り下げたもので, この分野のバイブル的存在である. 何度か改訂されているが, 残念ながら, 邦訳は最近のものではない. (p. 198より)

D. Knuth: The Art of Computer Programming, Vol. 1-Fundamental Algorithms (3rd Edition). Addision-Wesley, Reading, 1997.
D. Knuth: The Art of Computer Programming, Vol. 2-Seminumerical Algorithms (3rd Edition). Addision-Wesley, Reading, 1998.
D. Knuth: The Art of Computer Programming, Vol. 1-Sorting and Searching (2nd Edition). Addision-Wesley, Reading, 1998.

次の本は, NP完全に属す問題を分類して整理したもので, 基本的なNP完全問題の辞書のような役割を果たしている. (p. 198より)

M. R. Garey and D. S. Johnson: Computers and Intractability-A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.

参考文献 -References

杉原厚吉:『データ構造とアルゴリズム』. 共立出版, 東京, 2001.

クラスPの "P" は "Polynomial(多項式の)" の略である. ↩
クラスNPの "NP" は "Nondeterministic Polynomial(それぞれ, 非決定的, 多項式の)" の略である. ↩

アルゴリズムと計算量