すのふら

すのふら

日々の備忘録

『Pythonで体験してわかるアルゴリズムとデータ構造』メモその6/分割統治法と動的計画法を知る

Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。

Pythonで体験してわかるアルゴリズムとデータ構造

Pythonで体験してわかるアルゴリズムとデータ構造



第6章 アルゴリズムを設計する方法

この章のゴールは 複雑な問題を解く際にアルゴリズムをどのような方針で設計したらよいか、説明できるようになる

書籍中ではフィボナッチ数列を例にとって説明している。

フィボナッチ数列について

フィボナッチ数列」とは,「前の2つの数を加えると次の数になる」という数列です。  ただし,1番目と2番目の数は両方とも1です。
フィボナッチ数列と中学入試問題 - すぐる学習会

どういうことかというと、

0, 1, 1, 2, 3, 5, 8, 12, 21, 34 …

上のような何かのルールにのっとっている数字の列をフィボナッチ数列という。 *1
そのルールが上の「前の2つの数を加えると次の数になる」。

基本的に0番目は0、1番目は1出ることがこの数列のルールになる。

3番目の結果は、0番目+1番目=1。
4番目の結果は、2番目+3番目=2。

というようにルールに合わせると結果が求められる。

フィボナッチ数列は、自然界にあふれていて枝の数や、ひまわりの種の数、カタツムリの殻の形などはフィボナッチ数列でできている。



上の話を漸化式で考えると

fib_{0} = 0

fib_{1} = 1

fibn = fib_{n-1} + fib_{n-2}  (n>=2)

じゃあこれをどのように実装するのかというところで、アルゴリズムを考えていく上での解き方を考える。



分割統治法

そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。
分割統治法 - Wikipedia

与えられた課題大きな回答を出すときに、力づくで解くのではなく、ある程度小さく区切って処理をしてしまおうという考え方。

小さく区切る=再帰呼び出しを行って、自身を何度も呼び出すことで小さい処理を行っていく。

ただし、再起呼び出しするので、同じ処理を何度も繰り返すために、無駄な処理を繰り返しメモリ領域をひっ迫する可能性がある。



実装

6という大きな数字を分割し続けて、回答を出していく

def fib(n):
    print("{}の処理".format(n))
    if n < 2:       
        return n
    else:
        print("{}のa処理へ".format(n-1))
        print()
        a = fib(n-1)
        print()
        print("{}のb処理へ".format(n-2))
        b = fib(n-2)
        c=a+b
        print("{}={}+{}".format(c,a,b))
        return c

ans = fib(6)
print()
print("結果", ans)
6の処理
5のa処理へ

5の処理
4のa処理へ

4の処理
3のa処理へ

3の処理
2のa処理へ

2の処理
1のa処理へ

1の処理

0のb処理へ
0の処理
1=1+0

1のb処理へ
1の処理
2=1+1

2のb処理へ
2の処理
1のa処理へ

1の処理

0のb処理へ
0の処理
1=1+0
3=2+1

3のb処理へ
3の処理
2のa処理へ

2の処理
1のa処理へ

1の処理

0のb処理へ
0の処理
1=1+0

1のb処理へ
1の処理
2=1+1
5=3+2

4のb処理へ
4の処理
3のa処理へ

3の処理
2のa処理へ

2の処理
1のa処理へ

1の処理

0のb処理へ
0の処理
1=1+0

1のb処理へ
1の処理
2=1+1

2のb処理へ
2の処理
1のa処理へ

1の処理

0のb処理へ
0の処理
1=1+0
3=2+1
8=5+3

結果 8

やっぱり再帰的定義で実装するといまいちよくわからなくなるよなあ。



動的計画法

分割統治法の計算は無駄なので、計算結果を保存しておいて再利用していけば無駄なメモリを使わなくてよいのでは?というのが動的計画法

フィボナッチ数列で考えるのであれば、配列の0番目から順番に計算することで、配列にすでに突っ込んだデータを流用できるよねという考え方。

人間が純粋にイメージするような計算手法。

欠点は小問題が多い場合、使用頻度の低いデータがメモリに残りっぱなしになること。

フィボナッチ数列だと、要素6番目まではいいけど1000番目のときに、0番目の要素って全然使ってないから無駄にメモリ食ってない?ってこと。



実装

def fib(n):
    A = [None] * (n+1)
    print(A)
    A[0] = 0
    A[1] = 1
    print(A)

    for i in range(2, n+1):
        A[i] = A[i-1] + A[i-2]
        print(A)
    return A[n]

ans = fib(6)
print()
print("結果", ans)
[None, None, None, None, None, None, None]
[0, 1, None, None, None, None, None]
[0, 1, 1, None, None, None, None]
[0, 1, 1, 2, None, None, None]
[0, 1, 1, 2, 3, None, None]
[0, 1, 1, 2, 3, 5, None]
[0, 1, 1, 2, 3, 5, 8]



その他参考

www.cs.gunma-u.ac.jp

sevendays-study.com

*1:数列なので、先頭の0は1番目ではなく0番目