科研之友
微信
新浪微博
Facebook
分享链接
摘要
Rollout algorithms are heuristic algorithms that can be applied to solve deterministic and stochastic dynamic programming problems. The basic idea is to use the cost obtained by applying a well known heuristic, called the base policy, to approximate the value of the optimal cost-to-go. We develop a theoretical approach to prove, for the 0-1 knapsack problem, that the minimum performance ratio of the rollout algorithms tends to be significantly greater when the performance ratio of the corresponding base policy is poor and that the worst-case performance ratio is significantly better than the one of the corresponding base policies.
- 出版日期2012-2
