大きな問題1に直面した時、みなさんはどのようにその問題を解決しますか？
「大きな問題を解決するために小さい問題から解決していく」という考え方、いいですよね。
プログラム上で何かを処理したいときにも、この考え方が有効な場合があります。
この記事では、小問題の答えをもって大きな問題を解決するアルゴリズムである分割統治法と動的計画法について概要を紹介し、「配列内の最小値を求める」というシンプルな問題に適用することで、その実例と違いを明らかにしていきます。
きっとこの記事を読んだ人は、問題を分割して統治したくなったり、動的に計画したくなるはずです。
##分割統治法と動的計画法の概要紹介
分割統治法と動的計画法の概要の紹介です。平たく言えば、Wikipediaを読みます。
分割統治法とは
Wikipedia先生によると
分割統治法（ぶんかつとうちほう、英: divide-and-conquer method）は、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。
“分割統治法”. ウィキペディア日本語版. https://ja.wikipedia.org/w/index.php?title=%E5%88%86%E5%89%B2%E7%B5%B1%E6%B2%BB%E6%B3%95&oldid=82378205, (参照 2021-03-30).
だそうです。
ふむふむなるほど、「手分けしてやっつける」ということですね。
確かに、「全身の筋肉を一度に鍛える」ための夢のようなトレーニングはないですが、「部位ごとを鍛える」という小さな課題に分割すれば解決し、結果的には全身の筋肉を鍛えられます。筋トレは分割統治法
動的計画法とは
またもWikipedia先生の力をお借りします。
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
「計算機科学の分野において」という記述が目を引きます。あまり日常の事象で例えないほうが理解しやすいかもしれません。
どうやら分割統治法と説明が似ていますが、何が違うのでしょうか。続けてWikipediaの記述を見ていきます。
細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。
帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。
“動的計画法”. ウィキペディア日本語版. https://ja.wikipedia.org/w/index.php?title=%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95&oldid=82262891, (参照 2021-03-30).
帰納的な関係の利用・計算結果の記録という二つのキーワードが出てきました。
今は「分割統治法と似ているな」ということと、この二つのキーワードだけ覚えておいてください。
次の節では、このキーワードをもとに実例を交えて解説します。
「配列内の最小値を求める」を考える
分割統治法と動的計画法という言葉を認識した次のステップとして、実際にそれらの問題解決手法に従って実装することで意味を理解します。
我々が挑戦する大きな問題とは、「配列内の最小値を求める」というものです。
配列の最小値を求めると聞いて、プログラミングを勉強した方は「何をそんな難しそうに書いているのか？」と考えると思いますが、一旦先入観を捨ててこの問題に向き合ってみましょう。
以降、便宜上「配列を引数にとり、配列内の最小値を返す」働きの関数を 「min関数」 と呼ぶことにします。
その辺は雰囲気で理解してください。
min関数の実装①：数学的定義の書き下し
配列内の最小値を求めるにあたって、またもWikipediaから2「最大と最小」の記事を確認することにします。
厳密な定義
正式には次のように定義される。(P, ≦) を 1 つの半順序集合とし、S を P の 1 つの部分集合とする。そのとき、次の条件
S の任意の元 s に対して、s ≦ g
を満たす S の元 g を S の最大元という。また、次の条件
S の任意の元 s に対して、g ≦ s
を満たす S の元 g を S の最小元という。
“最大と最小”. ウィキペディア日本語版. https://ja.wikipedia.org/w/index.php?title=%E6%9C%80%E5%A4%A7%E3%81%A8%E6%9C%80%E5%B0%8F&oldid=81913189, (参照 2021-03-30).
雰囲気でプログラミングの文脈に置き換えると、
配列内の任意の数 y に対して x ≦ y を満たす配列の要素 x を配列の最小値という
ということですね。
これをプログラムに書き下してみましょう！条件を少し言い換えています。
今回はPythonを用います。
# 配列内のある数 x について
# 配列内の任意の数 y を考えたとき
# 一つでも x > y が成り立つなら x は最小ではない
# 逆に、一つも x > y が成り立たないなら x は最小
def min_naive(array):
for x in array:
x_is_min = True
for y in array:
if x > y:
x_is_min = False
if x_is_min:
min_element = x
return min_element
単純に定義をそのまま(言い換えて)実装しました。
センスのいい方は「ひどく非効率な処理だ」と考えると思います。その通りです。
様々な工夫ができると思いますが、今回はこれを分割統治法的アプローチと動的計画法的アプローチで改善を図ります。
min関数の実装②：分割統治法の考え方を用いる
小さな問題に分割し解決していくという考え方を、min関数の実装に適用してみましょう。
こんな問題を考えます。「日本で最も安いカレーは？」3
日本で最も安いカレーを決めるとき、効率の良いやり方として、
東日本で最も安いカレー VS 西日本で最も安いカレー
の構図にすることが考えられます。テレビの企画みたいですね。
それでは、東日本で最も安いカレーはどう決めるのが効率が良いでしょうか
同様に、
北海道・東北で最も安いカレー VS 関東・中部で最も安いカレー
で決めるということが考えられます。
北海道・東北で最も安いカレーも同じように、
北海道で最も安いカレー VS 東北で最も安いカレー
で決めると良いですね。
この計画では、対象の領域を二分し、それぞれで最も安いカレーを選抜した後、それらを競わせるという方針です。
二分した領域それぞれに対しても、再帰的に最も安いカレーを求めるのはとても効率的です。
この考え方を、min関数の実装に適用してみましょう！
# 二つの数のうち小さいほうを返す
def smaller(x, y):
return x if x < y else y
# 配列を中央から左右に二分し、それぞれの配列の最小値を求める
# 左右の配列それぞれの最小値を比較し小さいほうが、元の配列の最小値
# これを再帰的に行う
def min_divide(array):
if len(array) == 1:
return array[0]
mid = len(array) // 2
min_left = min_divide(array[:mid])
min_right = min_divide(array[mid:])
return smaller(min_left, min_right)
少しpython特有の記法が出てきましたが、雰囲気で理解してください（大切なのは考え方です）。
再帰処理が入って複雑なように思えるかもしれませんが、コメントにある通りの処理を行っています。
分割して、小さい範囲で問題解決し、大きい問題を解決する、という流れを完全に理解できたと思います。
min関数の実装③：動的計画法の考え方を用いる
動的計画法は、問題の性質をよく観察し、大きい問題を小さい問題の解を使って表現できないか考えるところから始まります。
これには決まったやり方はないですが、求めたい解に対し、問題をスケーリングできるような「状態」を媒介変数的に付与することが多いです。
抽象的な説明が難しいため具体例を示すと、今回の場合
(配列の長さをNとすると)
配列の最小値 → 配列のN番目までの最小値
と問題を言い換えます。
次に、この時に変数表示した部分に対して、その近傍が分かっていれば簡単に計算することができないか？と考えます。
すると、
配列のi番目までの最小値 = 配列のi-1番目までの最小値 と 配列のi番目 の 小さいほう
というように、簡単に計算できそうなことがわかりました。
これをなんちゃって数式的に書き直すと、
{\rm ans}_i = {\rm smaller}({\rm ans}_{i-1} ,\,\, {\rm array}_i)
と表現できます。ここで、 ${\rm array}_i$ の値は与えられている配列なのですぐにわかります。
答えが出ていない数は ${\rm ans}_i$ になりますが、ある $i$ について ${\rm ans}_i$ が求まれば、$i$ 以上の場合の解が逐次的にわかることは式から読み取ることができます。
ここで ${\rm ans}_1$ とは何でしょうか。
配列の1番目までの最小値なので、明らかに配列の1番目がそのまま入ります。
すると、${\rm ans}_{\rm N}$ までの解が逐次的に求められることがわかり、問題を解決できました。
実際にプログラムに書き起こしたものがこちらです。実装の都合上、0-indexedになっています。
# ans[i] = 配列のi番目までの最小値という定義を考える
# ans[i] = smaller(ans[i - 1], array[i]) という遷移式が立つ
# ans[0]が初期値として確定し、逐次的にans[i]を求める
def min_dynamic(array):
length = len(array)
ans = [None for i in range(length)]
ans[0] = array[0]
for i in range(1, length):
ans[i] = smaller(ans[i - 1], array[i])
return ans[length - 1]
ここで注目すべきは、ans[i] という形4で小問題の解を記録し、帰納的な関係を利用して解を導出しています。
動的計画法の説明で行った二つのキーワード「帰納的な関係の利用・計算結果の記録」が理解できたと思います。
min関数の実装④：本当にあった怖い話
min関数を作りなさいと言われたら、普通はこんな形になりますよね
def min_normal(array):
length = len(array)
min_elem = array[0]
for i in range(length):
min_elem = smaller(min_elem, array[i])
return min_elem
この形は一つ前の動的計画法の実装に、「隣り合うans同士しか計算結果に影響しないため、計算結果の記録は一つ前の遷移分のみを保持しておくだけでよい」、という特性があったことを利用した改善結果です。
そうです、min関数の実装と聞いてなんとなくこんな形が思いうかんだそこのアナタ。
実は知らず知らずのうちに動的計画法をやっていたのです…！5
分割統治法と動的計画法の違いについて
さて、min関数を例に実際に実装することで、分割統治法と動的計画法についてすこし理解が深まったかと思います。
一方で、「動的計画法も"小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決"してるじゃん」と思う方もいると思います。
ここからは自分の考えになりますが、動的計画法は分割統治法の考え方を内包しているという認識です。
使い分けのためには、「動的計画法といえない分割統治法」を理解するほうが話が早いです。
min関数の実装②で説明したケースは「動的計画法といえない分割統治法」の一つの例だと思います。
分割した小問題それぞれが、本当に別の問題として並列に考えられるとき、それは分割統治法と言えると考えています。
小問題それぞれを解く過程に、ほかの小問題との重複がない場合は計算結果のメモが不要なため、動的計画法の定義に当てはまらないからです。
とはいえ、どちらも問題を解くための手段で、問題を解けていればそれでよいです。使用するために名前はこだわらなくてよいと思います。
まとめ
分割統治法と動的計画法についてやんわりと理解したうえで、配列内の最小値を求めるという簡単な問題に対して分割統治法と動的計画法の考え方で取り組みました。
これらはあくまで問題解決のためのいち方針であり、すべての問題に適用できるわけではありません。
目の前に一筋縄ではいかない問題が現れたときに、この考え方はどうか？というアプローチの引き出しとして持っていただければよいと思っています。
詳しい紹介は省きますが、競技プログラミングのコンテストサイト「AtCoder」さんに、動的計画法の方針を使える問題だけで構成された
Educational DP Contest / DP まとめコンテスト
という問題セットがあります。実際に動的計画法の考え方を使って問題を解いてみたい、という方にお勧めです！