水木社区手机版
- 主题:小学数学推理题2
- 依稀想起了运筹学中的最大流问题，这个有啥通俗易懂的算法吗？
--
FROM 219.144.189.* - 不愧是高知论坛呀
--
FROM 219.144.180.* - 有个问题，站在倒数第二个格子，3，
决定是向上，去5，还是向左，去6 的时候，
因为向左，去6，得到的数字大，所以向左
有没有一种可能，向上，去5，虽然这一步数字小了一点，但继续倒推的时候，能遇到一条数字大的路径，把少的这点补回来？
或者换个说法，向左，去6，这一步的数字是大了，但继续倒推的时候，就只能持续遇到小数字了。
会有这种可能性吗？
【 在 mrunmatched 的大作中提到: 】
: [upload=1][/upload]
--
FROM 219.144.180.* - 明白了，格子里的红色数字，实际上就是以当前格子为起点，到终点的最优路径。
这个题目要求从左上到右下的最优路径，但起点和终点距离太远，可能路径太多，一下看不出来。
所以这个算法就是倒算，先确定离终点近的格子的最优路径，然后由近及远，逐步外推，
直到倒推回起点。
这应该是运筹学里面的一个经典算法，当年也学过的，在各位老师的提示下，终于想起来了，感谢！！
【 在 mrunmatched 的大作中提到: 】
: 没有这个可能性。这个算法最后能得到从任何一个格子出发，到达右下角目标点的最优路径。想一下，从其中任何一个格子出发只能向右和向下两条路，而你已经计算出了从右边节点和从下边节点出发到达目标点的最小代价(最大和)，所以你就能知道你应该往下走还是往右走了。就是一个简单的递推算法。
--
FROM 117.23.81.* - 看明白了，哈哈。
立足一个点，找到局部最优，步步推进。
【 在 SYSQP 的大作中提到: 】
: 不一定要倒着算。
: 借上面一张图，标上箭头和叉叉，就很清楚了。
: - 来自 水木社区APP v3.4.0
--
FROM 117.23.81.*