Anand本記事は、原著者の許諾のもとに翻訳・掲載しております。私が常に頭を悩まされていたのが最適化問題です。これは、コードを理解するだけでも非常に困難な問題です。そこで、これまでに私が学んだことを基に、典型的な動的計画法の問題を取り扱ういくつかの記事を投稿することにしました。今回取り上げるロッド切り出し問題は古典的な最適化問題であり、動的計画法の一例と言えます。ロッド切り出し問題とは?ロッド切り出し問題は、現実世界で私たちが直面するたいていの問題に非常によく似ています。ある長さの棒があり、この棒を最大利益が得られる長さにして切り売りをしたいという状況があると仮定します。ここで問題となるのは、切り出した長さによって棒の値段が異なる点です。細かく切り出した方が大まかに切り出した場合よりも、より多くの利益が得られる可能性があるため、ちょっと違った考え方をする必要があります。先に進む前に、まずはこの問題をより正確に定義しておきましょう。(本数は複数の可能性あり)とする。問題を煮詰めると、結局どこで棒を分割するかという問題に行き着くことがわかります。9このことから、最大利益は10であり、size=2の部分で分割して棒を長さ2になるように2本切り出しした場合であるとわかります。以下のように求められます。最大値が、最大利益となる。どこで切り出されたかをトラッキングするには、追加容量が必要。このケースにおいて、再帰は理想的な候補の1つです。再帰的なコードはこちらをご覧ください。時間計算量とは何か?この問いに対する答えは、切り分ける方法が何通りあるかを考えることで得られます。通りの方法があります。通りまとめると次のようになります:1箇所で切断する場合+2箇所で切断する場合+...k箇所で切断する場合...n-1箇所で切断する場合ソース:http://www.cs.uml.edu/~kdaniels/courses/ALG_503_F12/DynamicRodCutting.pdfこのように、時間計算量は指数関数的になりますが、もっと良い方法があるか見てみましょう。1つの方法として、再帰をメモ化、すなわちメモを取るという方法があります(説明はこちら。して、大きな値であるnに対しては機能しなくなってしまう指数関数的な演算は残ってしまいます。それでは、動的計画法について考えましょう。動的計画法で解決するこの問題では既に、部分構造最適性と部分問題重複性が明らかになっています。....(i-1)箇所で切断を行うことで求められます。}これを説明すると、r(i)は棒を切断しない場合のp(i)であるか、あるいは長さ1に切断した場合の価格をr(i-1)に加えた価格であると読むことができます。このr(i-1)は、事前に解決した、i-1の長さの棒の最大収益に該当します(切断の回数はさらに多くなる場合があります)。長さ2の場合も同様にして、r(i-2)について解けばよいことがわかります。r(i)は、iより小さい値に対して事前に算出された値に依存します。この場合は貪欲法とは異なり、決定を下すために全ての分析を行います。実際、元に戻って、全てのiの値を比較します。これは個々の部分問題の最適値によって次の部分問題を解決するという、部分問題重複性なので、部分構造最適性となります。**(長さ2で切断)このまま続けていくと...表を埋めてみると以下のようになります。2完成した表r(5)の最終的な答えは13になります。ここで13という答えが導き出されるまでに何回切断したかを数えるにはどうしたらいいでしょうか。難しく考えずに、r(5)の計算式から順にさかのぼって(バックトラックして)いけばいいのです。value(訳注:上表のcut行参照)には2とあるので、どこかで切断して長さ2の棒があるはずです。そこで1回切断されたことになります。長さ5に対して長さ2の棒があるので、残りは長さ3になります。そこでr(3)を確認してみましょう。valueが3とありますから、この長さ3はこれ以上短く切断されていないことになります。よって長さ2では切断は1回だけでいいというわけです。長さ5の棒から得られる最大利益は1箇所だけ切断して、長さ2と長さ3の棒に切り出した時となります。この非再帰的なアプローチはボトムアップな方法です。その際の時間計算量は次のようになります。O(n2)のほうがはるかに効率的です。今回の方法では最適化問題の解決のための直観力を養うことはできますが、すべての最適化問題に有効なわけではありません。とっかかりとするにはちょうど良いでしょう。参考までに、動的計画法の関連リンクについても掲示しておきます:http://www.cs.uml.edu/~kdaniels/courses/ALG_503_F12/DynamicRodCutting.pdfhttp://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/ツイート翻訳に対するフィードバックがございましたら、メールまたはGitHubのIssueよりお寄せください。Ltd.リクルートグループサイトへ。