动态规划方法的应用研究
所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。⑷ 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。2 动态规划方法的应用2.1 货郎担问题2.2 多段图的最短路径问题多段图的最短路径问题，是求从源点s到达收点t的最小花费的通路。数组元素cost[i]存放顶点i到达收点t的最小花费；数组元素path[i]存放顶点i到达收点t的最小花费通路上的前方顶点编号；数组route[n]存放从源点s出发，到达收点t的最长通路上的顶点编号。第一阶段，确定第k-1段的所有顶点到达收点t的花费最大的通路。第二阶段，用第一阶段的信息，确定第k-2段的所有顶点到达收点t的花费最大的通路。当gi（xi）都是线性函数时，它是一个线性规划问题；当gi（xi）是非线性函数时，它是一个非线性规划问题。但当n比较大时，具体求解是比较麻烦的。然而，由于这类问题的特殊结构，可以将它看成一个
<<上一页 下一页>>
广州市越秀区图书馆版权所有。
联系电话：020-87673002
本站访问人数：