メモ化を用いたダイクストラ法の実装について 多変数の最適化問題において、問題がより小さな部分問題に分割でき、部分問題の最適解が全体の最適解に 含まれているという関係が再帰的メモ化を用いたダイクストラ法の実装について 多変数の最適化問題において、問題がより小さな部分問題に分割でき、部分問題の最適解が全体の最適解に 含まれているという関係が再帰的に成り立っているならば、小さな部分問題から逐次的に解いていくことによっ て効率良く全体の最適解を求める動的計画法と呼ばれる手法が利用できる。動的計画法をコンピュータ上で実 装する際に、多くの場合は再帰的関数とメモ化を用いて直感的なプログラムとして容易に実装できる。 ただし、動的計画法の中でも、ダイクストラ法のように、一度求めた変数の値を逐次的に改良していくよう な手法は一般に破壊的代入を用いて記述されており、副作用を取り扱えないメモ化という手段で実装できるか どうか一見すると明らかでない。 しかし、少し考えれば、ある変数の値が改良によって最適値に近づくときに、それらの値の列全体から何ら かの評価関数で選択したものが求め
