【アルゴリズム】 シンプレックス法 / 動的計画法 / メモ化再帰 / 分割統治法

■ 用語

シンプレックス法 / 単体法 (simplex method)

 * 線形計画問題（LP:Linear Programming）を解くためのアルゴリズム

解説動画

動的計画法(Dynamic Programming, DP)

 * メモ化 + 分割統治法

分割統治法(Divide-and-Conquer method, conquer = 征服する)

 * 問題を小さい問題に分割し、部分問題の解を利用して、問題全体の解を得る手法

メモ化（Memoization）

 * 途中の計算結果を記憶しておき、うまく再利用することで計算効率を上げる手法
 => 一度行った処理はメモリ上に記憶しておき、再度同じ処理が呼ばれたらそのメモリ上の結果を利用する

■ 動的計画法で解決できる代表的な問題

[1] フィボナッチ数列(Fibonacci)

http://blogs.yahoo.co.jp/dk521123/34536896.html

[2] ナップザック問題
[3] 最短経路（Shortest Paths）/ Lattice paths
[4] 最長共通部分列(Longest Common Subsequence; LCS）
[5] 最長増加部分列(Longest Increasing Subsequence; LIS)

などなど

参考文献

http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html
http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html
ナップサック問題
http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html
http://dai1741.github.io/maximum-algo-2012/docs/dynamic-programming/
https://www.ibm.com/developerworks/jp/java/library/j-seqalign/
丁寧に書かれた資料
http://www.slideshare.net/nitoyon/ss-1086077

関連記事

動的計画法 ～ フィボナッチ数列 を例にして～

http://blogs.yahoo.co.jp/dk521123/34536896.html

ナップサック問題 [1] ～ 貪欲法 ～

http://blogs.yahoo.co.jp/dk521123/35392669.html