動的計画法(1)

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

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

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

	def fib(n):
	if n < 3:
	return 1
	return fib(n-1) + fib(n-2)
	for i in range(1, 11):#10項まで表示
	print('{0}項 = {1}'.format(i, fib(i)))

view raw fib関数 hosted with ❤ by GitHub

これはフィボナッチ数列の第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件を動かした結果です。

	#フィボナッチ数列でメモ化を利用(界標準MIT教科書 Python言語によるプログラミングイントロダクション第2版)
	def fastFib(n, memo = {}):
	if n < 3:
	return 1
	try:
	return memo[n]
	except KeyError:
	result = fastFib(n-1, memo) + fastFib(n-2, memo)
	memo[n] = result
	return result

view raw fastFib関数 hosted with ❤ by GitHub

calclation_time:1.049574851989746[sec]

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

(3) 課題

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

[参考]

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

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