AXIOMS FOR DYNAMIC PROGRAMMING
This paper describes an abstract framework, called valuation network (VN), for representing and solving discrete optimization problems. In VNs, we represent information in an optimization problem using functions called valuations. Valuations represent factors of an objective function. Solving a VN involves using two operators called combination and marginalization. The combination operator tells us how to combine the factors of the objective function to form the global objective function (also called joint valuation). Marginalization is either maximization or minimization. Solving a VN can be described simply as finding the marginal of the joint valuation for the empty set. We state some simple axioms that combination and marginalization need to satisfy to enable us to solve a VN using local computation. We describe a fusion algorithm for solving a VN using local computation. For optimization problems, the fusion algorithm reduces to non-serial dynamic programming. Thus the fusion algorithm can be regarded as an abstract description of the dynamic programming method, and the axioms can be viewed as conditions that permit the use of dynamic programming.
- 粉丝: 0
- 资源: 7
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助