ゆるく動的計画法

OYPosted by

どうも。OYです。

今回は動的計画法というものについてゆるく解説します。あ、前回同様アルゴリズムの話です。
注釈多くなるのもあれなのでできるだけ専門用語は控えます。

・動的計画法ってなんだよ。

ある問題を経過的に分割し、その部分問題それぞれの最適解を求めることで問題全体の最適解を得るアルゴリズム。また、そういうアルゴリズムの基底に存在する考え方のことです。

・なんでわざわざそんなことするんだよ。

まず、最適解を求める問題って、学校でやるようなテストで例えると、満点以外に存在価値がないんです。つまり1問でも減点が出たらその時点で追試確定となります。ひっでえ

1問目を解きました。ただしそれが最適かどうかはわかりません。そんな状況で次以降の部分問題を解いても1問目が最適でなければその時点でに追試確定なってしまいます。つまり1問目以外の問題なんかやるだけ無駄手間ですよね。()

1問目を解いて提出、最適解でなければそのまま追試を受ける。これを最適解が出るまで繰り返す。これなら1問目が最適解であろうがなかろうが常に1問しか解いていないので無駄がありません。
最適解が出たならそれを記憶し、次の部分問題も同じ方法で最適解を出す。これを繰り返せばよいのです。

まるでとんちですね。

 

ifの条件式で論理積を用いたとき、1問目が最適でないと判断された時点で残りの問題は評価すらおこなわれません。そのため、他の部分問題を解いても無駄手間にはならないだろうというツッコミはできないのです。

 

・無駄手間を省けるのは分かったけど、具体的にどのくらい効率がいいんだよ。

ある問題を解くのに、問題のサイズに対して2のn乗の計算時間がかかるとします。

その問題のサイズが100だとします。その問題が部分問題10個(サイズも均等に10個)に分けられるとします。

これをそのまま解く場合、単純に2^100 = 2^10 * 2^10 ≒ 100万

部分問題1個を解く場合、2^10 ≒ 1000
これが10問あるので大体1万です。

上記例の場合、サイズ100の時点で100倍近くの差が出ています。またサイズが大きくなればなるほど効率の差も大きく広がります。

 

 

うーん。厳密にはちょっと違う、端折りすぎなのでは?ってところが散見されるのですが、まあミリしらな方に向けて簡易的に「だいたい」を伝えるのが目的なのでこれくらいがちょうどいいのかなと。

以上、ゆるく動的計画法でした。

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA