欧拉项目#18方法

Question

我正在研究欧拉项目.特别是#18.
总而言之,我们的想法是从三角形中找到最大路径:

   3
  7 4
 2 4 6  
8 5 9 3

3 + 7 + 4 + 9 = 23.

对此进行阅读,大多数人表示这是通过从下到上的工作而不是使用从上到下工作"贪婪"的算法来正确解决的.

我可以理解,从顶部开始向下选择你发现的最大值是"短视",可能不是整体最大值.

但为什么从底部到顶部的方法更好？
在我看来,它遇到了同样的问题.

例如,在示例中的三角形中,我们将得到(从底部开始):
9 + 6 + 4 + 3 = 22 <23

那么为什么要从下到上开始呢？

Answer 1

这就是所谓的动态编程.

你有这样的三角形:

   3
  7 4
 2 4 6  
8 5 9 3

当您从底部移动到顶部时,您可以计算最后一次迭代的最佳选择.在这种情况下,您将获取最后一行,8 5 9 3并在上一行之外最大化总和.

迭代1:假设你已经last-1迈出了一步.

你2 4 6有线,让我们迭代它.

从2开始,你可以去8或5,所以8更好(从2开始最大化你的结果)所以你计算第一个和8 + 2 = 10.

从4开始,你可以去5或9,所以9更好(从4开始最大化你的结果)所以你计算第二个和9 + 4 = 13.

从6开始,你可以去9或3,所以9再次更好(从6开始最大化你的结果)所以你计算第三个和9 + 6 = 15.

这是第一次迭代的结束,你得到了总和10 13 15.

现在你有了较低维度的三角形:

    3
  7  4
10 13 15  

现在继续,直到你得到一个值,正好是23.

Answer 2

区别在于自上而下和自下而上.区别在于贪婪和"前沿"方法.

贪婪的算法不一定会帮助你,因为如果树的最佳部分无法触及,你将无法恢复.例如:贪婪算法将从上到下选择路径1-3.它会完全错过9.

    1
   2 3
  9 1 1

为了找到真正的最大值,你必须基本上遍历所有路径.

如上所述,自下而上的方法没有这个问题.它最多检查n*(n-1)个路径:每个元素2个.然而,称之为"自下而上"的方法具有误导性.

为什么？因为有一种自上而下的方法是等价的.其实质是你有一种"边疆",对边境后面的所有树木都有最好的结果.无论您是向上还是向下移动边界都是次要的.对于上例中的自上而下方法,您可以为每一行计算每个元素的总和以及它上面两个最佳总数的最大值:

     1
    3 4
  12 5 5

在自下而上的方法中,您为每一行计算每个元素的总和以及它下面两个最佳总数的最大值.按相反顺序:

  9  1 1
   11 4
    12

这些自上而下和自下而上的方法都有相同的工作.

Answer 3

使用您的示例,接近它的"自下而上"方式是:

检查底行,你可以从每个元素得到的最多

8,5,9,3

检查从下到下的行,您可以从每个元素中获得的最多(取决于您是从左侧还是右侧):

2 + max(8,5),4 + max(5,9),6 + max(9,3)= 10,13,15

所以这很棒; 我们通过将它们压在一起来消除2行,将它们替换成一行,从而减少问题

     3
   7   4
10  13  15

显然我们可以继续重复这一点.检查下一行,你可以从每个元素得到的最多

7 + max(10,13),4 + max(13,15)= 20,19

所以从顶部来看,你可以得到的最多

3 + max(20,19)= 23

QED.

Answer 4

实际上,你不需要自下而上; 你可以自上而下开始,只要你做得好.

自下而上的工作方式最好地通过了解金字塔每个层面发生的事情来说明.路径肯定必须在某个时刻穿过每个级别.

    x
   x x
  x h x
 x y y x
x y y y x

让我们说吧h.从允许路径的定义来看,路径只能跟随到y标记的地方,形成类似于原始的问题 - 如果我们找到通过ys的最大路径并且整个三角形的最大路径实际上经过h,它肯定会跟随ys中的最大路径(如果没有,你可以在较小的三角形中切换路径部分并获得整体更好的路径).

因此,如果您构建算法自上而下计算从当前节点向下的最大路径,您将获得正确的结果(即最大路径值,您可以从中轻松获取路径本身).

现在,这需要O(N)(N表示数字的数量),因为对于每个地方,您只考虑两个路径并使用较低级别的预先计算的值.

实际上,相同的算法可以自上而下实现,如果您记住结果,则从顶部开始并递减.

best_length(node)
{ 
  if(node is terminal)
    return value(node)
  int m = 0
  for(next : lower neighbors of node)
    m = max(best_length(next), m)
  return m + value(node);
}

自上而下这样做的另一种可能性就是逆转计算.您从顶部开始,针对考虑其上邻居的每个节点,从该节点的顶部结尾获取路径长度(而不是从该节点向下到底行的路径).最后,您从底行收集数据,然后就完成了.

Answer 5

采用自下而上的方法会消除路径，而自上而下的方法只会增加潜在的路径。

因为您可以更快地消除不良路径，所以广度优先搜索成为最佳解决方案。任一方向的深度优先搜索都是错误的（正如您所展示的）并且速度很慢。