動的計画法の漸化式の立て方について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
asdjack
記事: 22
登録日時: 8年前

動的計画法の漸化式の立て方について

#1

投稿記事 by asdjack » 6年前

ここ半年ほど動的計画法の勉強を続けているのですが、漸化式の立て方がさっぱりわかりません。
ナップザック問題や格子路の様な問題はなんとか理解できたのですが、それ以外の問題で使おうとすると
どのように動的計画法を利用すればいいかも思いつかない状況です。
アルゴリズムイントロダクションに書いてある
①最適解の構造を特徴づける
②最適解の値を再帰的に定義
といった部分はやはり多くの問題を解いて慣れるしかないのでしょうか?
また、①②を考えるときどのような事を意識すればよいのでしょうか
抽象的な質問ですみませんがご教授お願いします。

たいちう
記事: 418
登録日時: 9年前

Re: 動的計画法の漸化式の立て方について

#2

投稿記事 by たいちう » 6年前

お望みの回答ではないかもしれません。
遺伝的アルゴリズムを適用した製品を作っていた時がありました。
問題を定義して遺伝子型と評価方法を決めるための汎用的な手段は見つけられず、閃きに頼っていました。
もう少し正確に書くと、プロとして作る以上「閃きませんでした」とは言えないため、
仕様を満たす最低限の性能のものは確保(設計段階まで)した上で、
あーでもないこーでもないと考え、良いアイデアが浮かべば実装して性能をテストしました。
私にはかなり楽しい仕事でした。

asdjackさんの求めているレベルがどの程度のものか判りませんが、
応用力が乏しいと新しい問題に対応できないのではないかと思います。
一度、視野を広げるために、動的計画法以外のアルゴリズムについても、
研究してみてはいかがでしょうか。

asdjack
記事: 22
登録日時: 8年前

Re: 動的計画法の漸化式の立て方について

#3

投稿記事 by asdjack » 6年前

たいちう さんが書きました: 一度、視野を広げるために、動的計画法以外のアルゴリズムについても、
研究してみてはいかがでしょうか。
回答ありがとうございます。
確かに動的計画法というのに拘りすぎていたかもしれません。
他のアルゴリズムなども勉強して視野を広げてみたいと思います。

閉鎖

“C言語何でも質問掲示板” へ戻る