如何在n高的数字金字塔中确定最大路由成本

Question

我有一个像这样的数字金字塔

       7
      4 8
     1 8 9
    2 4 6 7
   4 6 7 4 9
  4 9 7 3 8 8

routes: 32

每个数字都以其所在行的强大程度为索引。

 0 ( 9 => 1 ) 1 ( 8 => 5 ) 2 ( 8 => 4 ) 3 ( 7 => 2 ) 4 ( 4 => 0 ) 5 ( 3 => 3 )
 0 ( 9 => 4 ) 1 ( 7 => 2 ) 2 ( 6 => 1 ) 3 ( 4 => 3 ) 4 ( 4 => 0 )
 0 ( 7 => 3 ) 1 ( 6 => 2 ) 2 ( 4 => 1 ) 3 ( 2 => 0 )
 0 ( 9 => 2 ) 1 ( 8 => 1 ) 2 ( 1 => 0 )
 0 ( 8 => 1 ) 1 ( 4 => 0 )
 0 ( 7 => 0 )

在这个金字塔中有2^(n-1)条路线(你可以从每个数字往前走2条)如果金字塔的高度这么低，你可以很容易地计算出所有的路线，并相互比较。但如果你有一个50高的金字塔，有562949953421312条路线，问题就会稍微困难一点。

我认为我应该从最强大的数字开始从最底层开始，但很快我意识到，最大路由成本并不一定是以大数字开始或结束的。

然后我想也许第二个索引(你可以从一个数字走得更远)会有帮助，但我甚至没有实现它，因为我认为它仍然占用很多资源，并且不是最优的。

现在我对如何重新开始思考这个问题感到困惑。感谢您的任何建议

Answer 1

把你的金字塔想象成一棵根在金字塔顶部的树:我认为你想要从根到任何叶节点(金字塔底部)具有最大成本的路由。好的，它实际上不是一棵树，因为一个节点可能有两个父节点，实际上你可以从i-1级的至多两个节点到达i级的节点。

不管怎样，我认为你可以用动态规划的方法计算出成本最高的路线。让我以类似矩阵的方式重写您的数据：

7 
4 8 
1 8 9 
2 4 6 7 
4 6 7 4 9 
4 9 7 3 8 8

并将矩阵的缺失元素设为0。让我们称这个矩阵为v (表示值)。现在您可以构建一个矩阵c (表示成本)，其中c(i,j)是到达位置(i,j)处的树节点的最大成本。你可以用这个递归来计算它：

c(i,j) = v(i,j) + max{ c(i-1,j-1), c(i-1,j) }

其中，当您到达矩阵外的某个位置时，c(h,k)为0。本质上，我们说到达位置(i,j)的节点的最大成本是节点本身的成本加上到达其在i-1级的两个可能的父节点的成本之间的最大值。

下面是您的示例的c：

7     
11 15    
12 23 24   
14 27 30 31  
18 33 37 35 40 
22 42 44 40 48 48

例如，让我们以i=3, j=2为例：

c(3,2) = v(3,2) + max{ c(2,1), c(2,2) }
       = 6      + max{ 23    , 24     }
       = 30

从c可以看出，最昂贵路由器需要48英镑(您有两台路由器)。

Answer 2

最简单的方法是自下而上，你的复杂度是O(N)。在这种情况下，您不需要动态编程或递归。只需组成另一棵树，其中较高层的数字是较低层的最大值。

Answer 3

我建议你看看Dijkstra's Algorithm和A*。

我相信Dijkstra的比A*更准确，但更慢。