トップページ > コンテンツ > 数学・アルゴリズム関連メモ > 数学・情報工学的 > 動的計画法

フィボナッチ数列を計算する際などに利用される。

再帰的に関数を呼び出す代わりに、配列を用意して
計算済みのものはそれを利用することで計算するイメージ。
ナップザック問題(NP)に関する計算をする際にも使われたりする。

---

diffのアルゴリズムについて

diffのアルゴリズムを実装する際にも応用が可能だったりする。
ちなみに、diffのアルゴリズムは
http://constellation.hatenablog.com/entry/20091021/1256112978
が分かりやすい。

上記サイトは詳細まで書いてあって、
やや難しいので自分なりに解釈した結果は以下の通り。

• エディットグラフ：

　　2つの文字列を縦横に並べたもので、
　　比較元の文字列を縦、比較先の文字列を横にした場合は以下の通り。

　　縦の移動➡追加された文字につきコスト1
　　横の移動➡削除された文字につきコスト1
　　斜めの移動➡同じ文字なのでコスト0

　　全ての経路を計算する方法が一番単純だが、
　　計算コストが高いので、過去の計算結果を覚えておくという工夫が必要になる。

• NP法(全経路計算するとコストが高いため、このような方法がある)

　　y-xをkとして斜め線に番号kを付ける。　　
　　2つの文字数の差分をデルタとして定義し、デルタ線の幅分をエディットグラフに引く。

　　つまり、デルタ線に乗り続ける＝文字列の単純追加or削除で変更なし。
　　実際はそんなことは無いので、文字列の変更個数分だけ損失(p)が生じる。

　　損失が少ない順に計算を初め、到達点が大きい方だけ記録を付けて保存する。
　　そして、
　　デルタ線より下(-p<=k<delta)

        max(fp[k-1, p] + 1, fp[k+1, p-1])(※1)

　　デルタ線上(k=delta)

        max(fp[k-1, p] + 1, fp[k+1, p])

　　デルタ線より上(delta<k<delta+p)

        max(fp[k-1, p-1] + 1, fp[k+1, p])

　　となる。

(※1)今のk線より横(k-1)から横にずれた場合、デルタ線に近づくので損失に変化無し。
　　 今のk線より上(k+1)から縦にずれた場合、デルタ線から離れるので損失は1個大きくなるため