この後、questionを探索したところ、knapsack problemまたは非整数制約を使用して動的プログラミングアルゴリズムを使用して解決することはできません。私の実現について正しいのですか?ダイナミックプログラミングアルゴリズムには他にも限界がありますか?動的プログラミングアルゴリズムの制限
2
A
答えて
2
基本的に、可能なスコアの数(解の品質)は有限であり、メモリに収まるのに十分に低いと言えるでしょう。非整数とは一般に非離散を意味し、無限の可能な解の得点につながります。
N個の解決策スコアしかない場合は、N個の解決スコアを取得する必要があります。指数関数的なものではありません。それは動的プログラミングの背後にあるアイデアです。
1
私は、ダイナミックプログラミングが情報理論上の下限と一致することが知られていないので、ダイナミックプログラミングが最高の利用可能な技術であるかどうかはわかりません。ここ
はan example problem from David Eppsteinである:nは実数のソートされたリストが与えられる
、1とnの間のkのすべての値について正確にk個の要素を含む最小間隔 を見つけます。 二次的な時間にこの の問題を解決する簡単な動的プログラミングアルゴリズムがありますが、最もよく知られている下限は linearです。より速いアルゴリズムを記述するか、計算のいくつかの妥当なモデルでより大きなより低い値を に結びつけてください。
関連する問題
- 1. 動的プログラミングアルゴリズム
- 2. 文字列と動的プログラミングアルゴリズム
- 3. 動的プログラミングアルゴリズムと現実の利用
- 4. Seam - エンティティクエリ - 動的制限
- 5. 両方向の無制限/動的ViewPager
- 6. Javaでの最長共通サブシーケンスの動的プログラミングアルゴリズム
- 7. ナップザック問題の変形に対する動的プログラミングアルゴリズムの作成
- 8. ナップザックJavaコードに類似した動的プログラミングアルゴリズム
- 9. VB.Net一般的な制限
- 10. AndroidのFirebaseクエリリファレンスの制限を動的に変更する
- 11. asp.netの動的データの制限はどこですか?
- 12. jQueryタイムピッカーの時間を動的に制限しますか?
- 13. Express(node.js)のアップロードファイルサイズを動的に制限する
- 14. データベースの行数を自動的に制限する方法は?
- 15. Unityカスタムエディタパネルのスライダを動的に制限する
- 16. コロナ設定の物理的制限
- 17. データ型昇進の制限の動機
- 18. 浮動小数点数の制限
- 19. extjs3エディタグリッド制限キー動作の入力
- 20. 動的制御値
- 21. クリック数の制限、制限、無効化
- 22. が無制限のメモリ制限
- 23. DB接続プールサイズ合理的な制限?
- 24. リポジトリパターン:制限、目的、および
- 25. バックエンドエラーおよび取得活動制限
- 26. mysql無制限プライマリキー自動インクリメント
- 27. Sharebar浮動小数点制限 - WordPress
- 28. 制限
- 29. 制限
- 30. 制限
私は、ここに加えて、Theoretical Computer Scienceのスタック交換(http://cstheory.stackexchange.com/)の人々は、この質問には多くの洞察があります。 –