8. アルゴリズムを学ぶ¶

そろそろ、プログラミング入門は卒業し、本格的にプログラムで問題を解く方法を学んでいきます。

8.1. アルゴリズムとは？¶

アルゴリズムとは、問題を解くための手順のことです。もともと、9 世紀のバグダットの数学者アル・フワーリズミー (Al-Khwarizmi) 著の「インド数の計算法 (Algoritmi de numero Indorum)」が、12 世紀のヨーロッパに伝わり、長らくヨーロッパの大学の教科書となっていたことに由来しています。

現在では、数学、計算機科学、情報学の分野において、特にコンピュータを用いた問題解法の学問となっています。

8.1.1. 世界最古のアルゴリズム¶

アルゴリズムはたとえ名称が耳新しいとしても、全く未知なものではありません。

みなさんが、高校生のときに習ったユークリッドの互除法は、世界最古のアルゴリズムと呼ばれ、代表的なアルゴリズムとなっています。

ユークリッドの互除法

自然数 \(u, v\) の最大公約数は、次の手順で求められる。

\(u\)を\(v\)を割った商を\(q\)、余りを\(r\)とする
\(r = 0\) なら、\(v\) を結果として終了する
そうでなければ，\(r\) を新たに \(v\) として、元の \(v\) を新たに \(u\) として、最初から繰り返す

ユークリッドの互除法は、古代の数学者が発見し、古代ギリシア、アラビア、ルネッサンス・イタリアを通して、現在に伝わっています。このようにコンピュータが発明される以前からアルゴリズムは存在しています。

8.1.2. アルゴリズムとレシピ¶

アルゴリズムは、プログラミングにとってレシピに例えられます。もしくは、アルゴリズムとは情報のレシピと呼ぶ人もいます。

「カスタードクリームを作る」レシピを比較してみましょう。

8dfc52d5229c499c8dc8e3487a28efa4

カスタードクリームのレシピ

卵黄、砂糖、小麦粉を火にかける
スプーンを材料に浸す
スプーンを引き出し、スプーンの裏側を指でなぞる
もし跡がくっきりと残るなら、火を止めて冷やす
そうでなければ、2. から繰り返す

似ている部分 1. アルゴリズムも料理のレシピも、どちらも順番があります。順番を間違えると、大惨事になります。 2. ある条件を満たすまで「繰り返す(待つ)」ことがあります。

アルゴリズムも、料理のレシピも、どちらも自分でゼロから考えるのは大変です。先人や達人たちの知識を学ぶことで、プログラムや料理の腕があがります。

国立情報学研究所宇野先生の大変わかりやすいアルゴリズム解説も参考にしてみてください

8.1.3. アルゴリズムの解き方¶

実際に、ユークリッドの互除法を使って、問題を解いてみましょう。

例題（最大公約数）

6215 と 4746 の最大公約数を求めよ。

手計算¶

皆さんは、ユークリッドの互除法を用いて、手計算で最大公約数を求めることができます。

\[6215 = 4746 \times 1 + 1469\]

\[4746 = 1469 \times 3 + 339\]

\[1469 = 339 \times 4 + 113\]

\[339 = 113 \times 3 + 0\]

プログラミング¶

さらに、今まで習ってきたプログラミング言語 (Python) を用いて、アルゴリズムをプログラミングすることもできるはずです。

[1]:

def gcd(u, v):
    while True:
        q = u // v
        r=u % v
        if r == 0:
            return v
        u,v = v,r

gcd(6215, 4746)

[1]:

もしかしたら、math モジュールには gcd 関数が存在し、それをライブラリとして用いるだけで問題を解決することを知っているかもしれません。

[2]:

 import math
 math.gcd(6215,4746)

[2]:

さて、最大公約数は、ここで示したどの方法を用いても、同じ正解に至ります。

アルゴリズムの公平性

アルゴリズムは、誰が計算しても同じ正解が得られる

8.1.4. どう解くべきか？¶

アルゴリズムは、コンピュータが発明される以前は、人間が手計算で計算していました。それ以外方法がなかったからです。しかし、コンピュータが登場した現在では、人間の代わりにプログラミングして問題を解きます。人間が手計算で解くと、計算間違いなどをするため、手計算で解く必然性は全くありません。

IT化/DXの本質

コンピュータで処理できることはコンピュータで処理する

昔は、プログラミングという技法が低く見られることがありました。曰く：

プログラミングとは、(ユークリッドの互除法のような頭のよい人が考えた)アルゴリズムをコードに翻訳するだけの単純作業である
本当に付加価値の高い重要な仕事はアルゴリズムを考えることにある

この考え方は、半分あっています。確かに、アルゴリズムを考えることが重要です。しかし、プログラミングが必要でないわけではありません。

現代社会の中で活躍しているアルゴリズムの多くは、コンピュータの発明後、計算機科学者やエンジニアがプログラミングしながら考案したものです。プログラミングという技法を用いなければ生まれなかったでしょう。

プログラミング

アルゴリズムを考えるための思考の道具

プログラミング力とアルゴリズム力は、車輪の両輪です。アルゴリズムだけ暗記科目として覚える必要は全くありません。自分でアルゴリズムをプログラミングしてみないと理解できないこともあります。是非、アルゴリズムをプログラミングしながら、思考力を高めていきましょう。

8.2. アルゴリズムの特徴¶

アルゴリズムは、問題の解法です。最初にユークリッドの互除法を見てもらい、特別なものではないよと知ってもらいました。しかし、現代のアルゴリズムは、コンピュータの特性を活かして、考案されています。

8.2.1. 探索する（探す）¶

例題（４整数の和）

0より大きい整数\(a,b,c,d\)の組で次の満たす数を求めよ

\[a+b+c+d=n\]

例: \(n\) が 35 のとき、\((a,b,c,d)\) の組み合わせは \((8,9,9,9)\)、\((9,8,9,9)\)、\((9,9,8,9)\)、\((9,9,9,8)\) の \(4\)通り

コンピュータは、計算することは得意です。人間ではとてもできませんが、全ての組み合わせを列挙して、全部の組み合わせを計算してしまうこともできます。

[2]:

def solve(n):
    count = 0
    for a in range(0, 10):
        for b in range(0, 10):
            for c in range(0, 10):
                for d in range(0, 10):
                    if a+b+c+d == n:
                        count +=1
    return count
solve(35)

[2]:

全探索

全ての組み合わせを調べること

コンピュータ上のアルゴリズムは、コンピュータの性質や強みを活かして、問題の解決にいたるものが多いです。

8.2.2. 方程式の解法¶

もう少しよく慣れた解法を比較して、アルゴリズムの違いをみていきます。

例題（方程式の解）

次の解を求めよ。

\[f(x) = x^2 - 2x - 8 = 0\]

中学数学では、因数分解や解の公式による解法を習いました。

\[(x + 2)(x - 4) = 0 ~~~\mbox{もしくは}~~~ x = \frac{2 \pm \sqrt{2^2 + 4\cdot 8}}{2}\]

アルゴリズムでは、コンピュータの計算能力を活用する方法を考えます。方程式の場合は、\(f(x)\)は一瞬で計算できるので、\(f(x)=0\)となる\(x\)を探します。

[1]:

def f(x):
    return x**2 -2*x - 8

for i in range(-5, 6, 1):
    print('x =', i, f'f({i}) =', f(i))

x = -5 f(-5) = 27
x = -4 f(-4) = 16
x = -3 f(-3) = 7
x = -2 f(-2) = 0
x = -1 f(-1) = -5
x = 0 f(0) = -8
x = 1 f(1) = -9
x = 2 f(2) = -8
x = 3 f(3) = -5
x = 4 f(4) = 0
x = 5 f(5) = 7

もちろん、方程式の解が整数の場合ばかりではありません。実数の場合もあります。

Let’s try

\(\sqrt{2}\)(つまり、\(x^2 - 2 = 0\) の正の解)を求めてみよう。

1と2の間で、0.1にして刻み幅を小さく探してみます。

[3]:

def f(x):
    return x**2 - 2

for i in range(10, 20, 1):
    x = i / 10
    print('x =', x, f'f({x}) =', f(x))

x = 1.0 f(1.0) = -1.0
x = 1.1 f(1.1) = -0.7899999999999998
x = 1.2 f(1.2) = -0.56
x = 1.3 f(1.3) = -0.30999999999999983
x = 1.4 f(1.4) = -0.04000000000000026
x = 1.5 f(1.5) = 0.25
x = 1.6 f(1.6) = 0.5600000000000005
x = 1.7 f(1.7) = 0.8899999999999997
x = 1.8 f(1.8) = 1.2400000000000002
x = 1.9 f(1.9) = 1.6099999999999999

ぴったり\(f(x)=0\)となりませんが、0に近い\(x=1.4\)が得られました。このような解を近似解と言います。コンピュータで数値解を求めるとき、なかなか厳密な精密解にはなりません。そのため、精度も重要になってきます。

8.2.3. 中間値の定理と二分法¶

もう少し詳しく方程式の解法をみていきましょう。

あらかじめ、解のありそうな探索範囲がわかっていれば、刻み幅を小さくして精度の高い解を探すことができます。しかし、探索幅がわかっていないと、かなりの回数を探索することになります。そこで、探索幅を狭めながら、効率よく計算する方法が使えるときがあります。

連続関数は中間値の定理が成り立ちます。

\(x_a\)と\(x_b\)の中間点を計算することで、解が\(x_a\)側にあるか、\(x_b\)側にあるか判定し、探索範囲を狭めていきます。

[5]:

eps = 0.00001
xa = 0.0　#探索範囲の左側
xb = 2.0　#探索範囲の右側
for _ in range(100):
    xm = (xa + xb) / 2
    y = f(xm)
    print('x =', xm, f'f({xm}) =', y)
    if abs(y) < eps: # 精度以下なら終了
        break
    if y > 0 : # xa側
        xb = xm
    else: #解は xb側
        xa = xm

x = 1.0 f(1.0) = -1.0
x = 1.5 f(1.5) = 0.25
x = 1.25 f(1.25) = -0.4375
x = 1.375 f(1.375) = -0.109375
x = 1.4375 f(1.4375) = 0.06640625
x = 1.40625 f(1.40625) = -0.0224609375
x = 1.421875 f(1.421875) = 0.021728515625
x = 1.4140625 f(1.4140625) = -0.00042724609375
x = 1.41796875 f(1.41796875) = 0.0106353759765625
x = 1.416015625 f(1.416015625) = 0.005100250244140625
x = 1.4150390625 f(1.4150390625) = 0.0023355484008789062
x = 1.41455078125 f(1.41455078125) = 0.0009539127349853516
x = 1.414306640625 f(1.414306640625) = 0.0002632737159729004
x = 1.4141845703125 f(1.4141845703125) = -8.200109004974365e-05
x = 1.41424560546875 f(1.41424560546875) = 9.063258767127991e-05
x = 1.414215087890625 f(1.414215087890625) = 4.314817488193512e-06

コンピュータは計算が速いといっても、人間より速いだけで無制限に計算できるわけではありません。このように計算量を減らす工夫が重要になっていきます。

Newton-Raphson 法

方程式の求解アルゴリズムとしては， Newton-Raphson 法など，より収束効率が優れたものが存在します。興味があったら、調べて書いてみよう。

8.3. 漸近的計算量解析¶

計算量解析は、アルゴリズムの効率を見積もり、アルゴリズムを選択する助けとなります。計算量と複雑さの考え方を理解しておきましょう。

8.3.1. プログラムの効率¶

プログラムの効率プログラムの効率は、次の2つの側面から評価できます。

コードの効率

プログラミングの経験的な知見に基づく
アーキテクチャやコンパイラ最適化、プログラミング言語の知識に基づく

アルゴリズムの効率

アルゴリズムの効率は、より普遍的で理論的な考察に基づく
コンピュータの種類やプログラミング言語に依存しない

コードの効率:どちらが高速?

n * 4

n << 2

ヒント；計算機アーキテクチャで習ったALUの原理まで戻れば、どちらの計算が速いかわかる

8.3.2. コンピュータの性能測定¶

Python では、time モジュールを用いて、プログラムの処理時間を計測します。また、Colab上では、%%timeを先頭につけると、実行速度を表示してくれます。

フィボナッチ数を計算する関数を定義して試してみましょう。

[6]:

%%time

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n-1) + fibo(n-2)

fibo(30)

CPU times: user 198 ms, sys: 2.91 ms, total: 201 ms
Wall time: 202 ms

[6]:

コンピュータで計測される時刻は精度の限界があります。極端に短い時間(ミリ秒以下)はあまり信用できません。

nは35くらいまでに

理由はあとから説明しますが、\(n\)を大きくしすぎてはいけません。

8.3.3. 計算量（複雑さ）¶

プログラムの処理時間は、コンピュータの性能が変わると大きく変わります。

計算量（複雑さ）は、プログラムに対する入力データが増えると、どのように処理量が増えるかという視点で理論的に見積もります。

処理量は、時間(処理時間)と空間(使用メモリ量)で測ります。

時間計算量 (time complexity)

プログラムの実行に必要な時間の見積もり

空間計算量 (space complexity)

プログラムの実行に必要なメモリ使用量の見積もり

一般に、計算量といえば、時間計算量のことをさします。また、計算量という用語は紛らわしいため、複雑さ(complexity)を好む人も多いです。

8.3.4. O記法¶

コンピュータ科学では、計算量を表す記法として、O 記法(ランダウの記法、オーダー記法)を用います。

O記法

入力規模 \(n\) に対する計算量の増加程度を示す記法

影響力の大きい(次数の大きい)項以外は無視する
定数倍の差は無視する

例

ある入力サイズ\(n\)の問題を解く手順が\(T(n) = 4n^2 -2n + 2\)と見積もられるとき、 \(n\) を次第に大きくしていくと \(n^2\) の項ばかり効いて、他の項はほとんど無視できます。したがって、このアルゴリズムの計算量は、\(O(n^2)\)となります。

代表的なアルゴリズムと計算量

暗記ものではないが

アルゴリズムを覚えたら、必ず計算量も確認しておこう

8.3.5. 指数時間¶

データ量が増えてプログラムが動かなくなる様子は、「指数爆発した」と形容されます。どうして爆発と形容されるのでしょうか?

O(2n) のアルゴリズムがあったとします。

比較的小さな入力数 \(n = 100\) でも、
仮に、1 秒間に \(10^{10}\) 回計算できる高性能コンピュータを用いても
\(4 \times 10^{12}\) 年かかる

指数時間

簡単に宇宙の寿命を超えてしまう

宇宙の寿命と言われても実感がわかないと思います。

最初に試したフィボナッチ関数の計算を思い出してみましょう。

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n-1) + fibo(n-2)

この関数は、入力\(n\)に対する計算量は\(O(\left\{\frac{1+\sqrt{t}}{2}\right\}^n)\)と見積もられ、指数時間アルゴリズムです。こんなに簡単ですが..

\(n\)を大きくしていくと、途中から爆発的に計算時間がかかるようになります。

2dcb8f42de8d4c77917d5e2b2878efa4

フィボナッチ・ベンチマーク

フィボナッチの再帰関数は、簡単なプログラムで簡単に負荷がかけられるので、プログラミング言語の性能を測る簡単なベンチマークテストとして重宝されてきました。

なお、フィボナッチ数は、線形時間\(O(n)\)で解くアルゴリズムがあります。詳しくは、動的計画法の回で説明しますので、そちらをお楽しみにお待ちください。

8.4. NPと計算困難★¶

アルゴリズムの計算量(複雑さ)に関する研究が進むにつれてある種の問題は、多項式時間アルゴリズムが見つからないことが明らかになってきました。

NP 完全問題 (NP complete problem)

さらに、同じ難しさのクラスだとわかってきた.

多項式時間アルゴリズムが見つからない
多項式時間アルゴリズムが存在しないと証明されたわけではない

8.4.1. NP完全問題¶

巡回セールスマン問題

\(n\) 個の都市に対する距離の集合と上限 \(D\) が与えられる. \(d \le D\) となる巡回路 \(d\) は存在するか?

ハミルトン閉路問題

有向グラフ \(G\) が与えられたとき、ハミルトン閉路を存在するか?

部分集合和問題(∼ ナップサック問題の一般化)

整数 \(w_1, ..., w_n\) と目標値 W が与えられる. このとき、\(\{w_1, ..., w_n\}\) の部分集合で合計が W となるものは存在するか?

制約充足問題(3-SAT)

変数の集合 \(X = \{x_1, .., x_n\}\) 上の長さ 3 節の \(C_1, .., C_k\) が与えられる. このとき全てを充足する真偽値割り当ては存在するか?

クラス P を多項式時間で解ける問題クラスとすると、次の予想がされています。

\(P \ne NP\) 予想

\(P \ne NP\) と信じられているが、証明されていない

（数学の）有名な未解決問題
コンピュータ科学の本質的な問い

現代の暗号技術は、多項式時間アルゴリズムがないことを根拠ににsて、暗号解読ができないことになっています。したがって、\(P \ne NP\)予想が覆されると、情報社会の根幹となっているセキュリティとプライバシがひっくり返ります。

8.5. 演習問題¶

全探索や少し工夫の必要な問題を集めてみました。

課題リストより

81
ケーキとドーナッツ
コイン
三角形を作る
ゴルフ大好き: 全探索でどうぞ
部分文字列: ヒントも参考に
穏やかなペア: 組(タプル)を使いましょう
お年玉: 探索範囲を狭める工夫が必要
高橋君の情報: 難しめ
A x B + C
ゾロ目: 全探索
論理式
8の倍数

Python Programming 2021 ドキュメント