回复 业余的业余
也在网络上搜索到过这个名称,基本都不知道意思,没学过算法。
我的想法是这样,就是模 ...
realnumber 发表于 2019-2-14 09:06
对了。我没细看你的过程,但被水沁润的过程,这个关键词说到点子上了,这就是单源最短路径额Dijkstra算法思路的核心。
本质上就是在不断的扩大同心圆(朋友圈),以包含更多的节点(Node), 这里是金字塔的方块。最初的时候,圆里只有圆心,就是初始节点(1,1,1), 然后从所有节点中找出到这点距离最近的,加入这个朋友圈,接着,再在剩下的节点中找通过朋友圈中的任何一点,到圆心,即初始节点最近的节点,加入朋友圈。以此类推,直到目标节点,即金字塔的最顶块进入了朋友权,算法结束,得到最优值。
思路虽然简单,实现需要极巧。要选取和你要进行的操作最适合的数据结构。但是,即使类似冒泡法的最笨的办法,也保证了算法具有多项式时间复杂度。如果用回溯法一类的状态空间搜索,你得到的应该是类似指数复杂度的。
动态规划应该可以,但既然贪心算法(Dijkastra) 可以,就不用管其它的路了。 |