ここ半年ほど動的計画法の勉強を続けているのですが、漸化式の立て方がさっぱりわかりません。
ナップザック問題や格子路の様な問題はなんとか理解できたのですが、それ以外の問題で使おうとすると
どのように動的計画法を利用すればいいかも思いつかない状況です。
アルゴリズムイントロダクションに書いてある
①最適解の構造を特徴づける
②最適解の値を再帰的に定義
といった部分はやはり多くの問題を解いて慣れるしかないのでしょうか?
また、①②を考えるときどのような事を意識すればよいのでしょうか
抽象的な質問ですみませんがご教授お願いします。
動的計画法の漸化式の立て方について
Re: 動的計画法の漸化式の立て方について
お望みの回答ではないかもしれません。
遺伝的アルゴリズムを適用した製品を作っていた時がありました。
問題を定義して遺伝子型と評価方法を決めるための汎用的な手段は見つけられず、閃きに頼っていました。
もう少し正確に書くと、プロとして作る以上「閃きませんでした」とは言えないため、
仕様を満たす最低限の性能のものは確保(設計段階まで)した上で、
あーでもないこーでもないと考え、良いアイデアが浮かべば実装して性能をテストしました。
私にはかなり楽しい仕事でした。
asdjackさんの求めているレベルがどの程度のものか判りませんが、
応用力が乏しいと新しい問題に対応できないのではないかと思います。
一度、視野を広げるために、動的計画法以外のアルゴリズムについても、
研究してみてはいかがでしょうか。
遺伝的アルゴリズムを適用した製品を作っていた時がありました。
問題を定義して遺伝子型と評価方法を決めるための汎用的な手段は見つけられず、閃きに頼っていました。
もう少し正確に書くと、プロとして作る以上「閃きませんでした」とは言えないため、
仕様を満たす最低限の性能のものは確保(設計段階まで)した上で、
あーでもないこーでもないと考え、良いアイデアが浮かべば実装して性能をテストしました。
私にはかなり楽しい仕事でした。
asdjackさんの求めているレベルがどの程度のものか判りませんが、
応用力が乏しいと新しい問題に対応できないのではないかと思います。
一度、視野を広げるために、動的計画法以外のアルゴリズムについても、
研究してみてはいかがでしょうか。
Re: 動的計画法の漸化式の立て方について
回答ありがとうございます。たいちう さんが書きました: 一度、視野を広げるために、動的計画法以外のアルゴリズムについても、
研究してみてはいかがでしょうか。
確かに動的計画法というのに拘りすぎていたかもしれません。
他のアルゴリズムなども勉強して視野を広げてみたいと思います。