分割統治法と動的計算法

個人用メモです。

分割統治法

分割統治法とは？

大きく難しい問題を細かく区切り、個々の解を求めたあとで、全体の答えを求める方法。

英語だと、divide-and-conquer method。

プログラミングでは再帰法を用いた処理が分割統治法にあたる。

自身の関数を処理の中に使うことで、処理を小分け(divide)し、それらを足し合わせるなどして答えを求め（conquer）ている。

▼n!を求める処理
1 * 2 * 3 * 4 *,,,,

.py

def factorial(n):
  if n==1:
    return 1
  return n*factorial(n-1)

問題をnとf(n-1)に分割し、個々の答えを求めたあとで全体の答えを求めている。

▼フィボナッチ数列を求める処理
1, 1, 2, 3, 5, 8, 13, 21, 34, 55,,,

.py

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

問題をf(n-1)とf(n-2)に分割している。個々の答えを求めたあとで全体の答えを求めている。

処理の確認

n=40
for i in range(1, n):
  print(fib(i))

これを実行すると比較的時間がかかる。
これは、fib(n-1)とfib(n-2)の中でそれぞれ同じ計算を個別に計算しているためである。

fib(n-2)の方が一足先に計算をしてるのだから、その解をfib(n-1)にも応用すれば、計算時間をグッと減らすことができる。

この画期的な方法を動的計画法という。

動的計画法

動的計画法とは？

一度計算した結果をメモリに保存し再利用することで計算時間を短縮する手法。

分割統治法は個々の問題を上から順に計算していく。トップダウン型。

これに対し、動的計算方は端々の計算結果を先に求め、その結果を用いて計算していく。ボトムアップ型。

関連用語
・dynamic programming：　英語名
・メモ化：　計算処理をメモリに保存すること。

実際の方法

・計算結果メモリ保存用の配列を用意する。
　　┗ 初期値は必要な要素数だけ空（None）要素を持った状態にする
　　┗ グローバル変数にならないよう、関数内に入れる
・指定した要素がNoneなら、計算して代入。

#変数のみだとmemoがグローバル変数になるため、defで囲みローカル変数にする
def fib_memo(n):
  #関数処理が終わっても値が残るようfib(n)の外に出す
  memo = [None]*(n+1)  #n+1個の空要素が入った配列を用意

  def _fib(n):
    if n==0 or n==1:
      return 1
    if memo[n] != None:  #指定した値の要素がNone以外なら、その値を利用（※初期値は全てNone）
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2) #Noneの場合は足し合わせた数値を代入
    return memo[n]

  return _fib(n)

確認

n=40
for i in range(0, n):
  print(fib_memo(i))

・None：空であることを明示（noneオブジェクト）
・_関数名: ローカルでのみ使用する関数を示唆

計算処理はかなり早くなる。

動的計画法（再帰法を使わない）

再帰法を使わずに、メモリ保存用の配列を使って求めることも可能。

def fib_dp(n):
  memo = [None]*n
  memo[0] = 1
  memo[1] = 1
  for i in range(2, n):
    memo[i] = memo[i-1] + memo[i-2]
  return memo

分割統治法と動的計画法まとめ

<分割統治法>

divide-and-conquer
大きな問題を小さく小分けする
トップダウンで処理する
同じ処理を個別に実行する可能性がある（×）

＜動的計画法＞

dynamic-programming
計算結果をメモリ記憶用の配列に保存する
ボトムアップの処理
同じ処理が複数回生じる場合に、大幅な効率化ができる