grf1973 发表于 2017-12-6 16:49

用VBA解欧拉计划题目（83）--路径和：四个方向

第83题：四个方向

附件还是和81题相同。

grf1973 发表于 2017-12-6 16:50

这几个动态规划的题做得人欲死欲仙啊。。。。。

香川群子 发表于 2017-12-6 22:38

这个复杂了。

grf1973 发表于 2017-12-7 09:47

太复杂了。这题和84题是前100题中唯二没有做出来的题。网上有解法，但我看不懂。英文水平太差了。

香川群子 发表于 2017-12-7 15:47

我思考了一下，需要进行广度递归搜索计算。

grf1973 发表于 2017-12-7 15:59

广度递归搜索，听着就高大尚。

香川群子 发表于 2017-12-7 16:55

不知道是否正确，结果是最短路径=425547

如下图。

香川群子 发表于 2017-12-7 16:58

对5*5例子的验证，也是正确的。


13123410318
20196342150
422111
121
37331

香川群子 发表于 2017-12-7 17:16

从左上开始，按对角线进行数据填充。

随时检查最小值，如发现更小值就对之前的结果进行递归回溯覆盖。保证所有路径记录都是最小值。

香川群子 发表于 2017-12-7 19:41

经确认，第82题也需要递归回溯检查，否则不能得到最短路径。

算法是一样的。不过起始数据为第1列，以及循环方式不同。

有趣的是，如果循环方式改为对角斜线，那么只要进行了4方向递归检查覆盖，也可以得到相同结果。
页: [1] 2 3 4
查看完整版本: 用VBA解欧拉计划题目（83）--路径和：四个方向