動的計画法(1)

 プログラムで再帰関数を利用することで、プログラムを簡略して書くことができます。特に漸化式で表されている数式をプログラミングする場合は、非常に簡単にプログラムができます。ここでは再帰関数が動的計画法で利用する場面を紹介します。プログラムの環境はGoogle Colabです。

(1) フィボナッチ数列をプログラムする ([1]参照)

フィボナッチ数列は前の2項(n-1とn-2)の和を現在の項(n)にするという数列です。これをプログラミングすると、下記になります。

これはフィボナッチ数列の第10項までを実行したものですので簡単に終わります。しかし、40項まで実行してみると、１分程度かかってしまいます。下記は3回の実行結果です。

40項 = 102334155 calclation_time:62.73430848121643[sec]

40項 = 102334155 calclation_time:62.58229374885559[sec]

40項 = 102334155 calclation_time:63.6257905960083[sec]

再帰計算を行うとき、同じ計算過程を何度も行う場合があり、計算上無駄が多くなっています。

(2) メモ化を利用する ([2参照])

メモ化は既に計算した値を確保しておき、必要になったときに利用していきます。既に計算されたものは値があるので、計算が驚くほど早くなります。下記は100000件を動かした結果です。

calclation_time:1.049574851989746[sec]

100000件でも1秒程度で計算できています。1,000,000件にするとメモリエラーになりました。

(3) 課題

メモ化でかなりの高速化ができるということがわかったが、メモリも消費する。MPIで並列計算を行い、メモリ分散ができるようにしてみたい。

[参考]

[1] 大和田 勇人, 金盛 克俊, Pythonで始めるプログラミング入門, コロナ社, (2015)

[2] Python言語によるプログラミングイントロダクション第2版 (著者省略), (2017)