mod 4 最优路径问题

《mod 4 最优路径问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、mod4最优路径问题3101220231234在上图中找出从第1点到第4点的一条路径，要求路径长度mod4的余数最小。分析：这个图是一个多段图，而且是一个特殊的多段图。虽然这个图的形式比一般的多段图要简单，但是这个最优路径问题却不能用动态程序设计方法来做。因为一条从第1点到第4点的最优路径，在它走到第2点、第3点时，路径长度mod4的余数不一定是最小，也就是说最优策略的子策略不一定最优——这个问题不满足最优化原理。但是我们可以把它转换成判定性问题，用递推法来解决。设fk(sk)——从第1点到第k点的长度mod4为sk的路径是否存在的标志

2、。显然（边界条件）（这里lenk，i表示从第k-1点到第k点之间的第i条边的长度）最后的结果就是可以使f4(s4)值为真的最小的s4值。fillchar(f，sizeof(f)，false)；f[1，0]←true；{边界条件}fork←2tondo{阶段：逐条边延伸}fors←0to3do{状态：枚举当前路径长度对4的每一个余数}foru←1tok-1点出发的边数do{决策：枚举k-1点出发的每一条边}f[k，s]←f[k，s]orf[k-1]mod4]；fori←0to3doiff[n，i]thenbreak；输出i；总结：本题意在

3、说明，不具有最优子策略（即不满足最优化原理）的阶段性问题，不能用动态规划解决。