我有一个像这样的数字金字塔
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条路线，问题就有点难了。
我原以为我是从最强大的数字开始的，但很快我意识到，最大路由成本不一定是从大数字开始或结束的。
然后我想也许二级索引(你可以从一个数字走得更远)会有帮助，但我甚至没有实现，因为我认为它仍然使用很多资源，不是最优的。
现在我很困惑如何重新开始思考这个问题…欢迎指教
把你的金字塔想象成一棵根在金字塔顶端的树:我想你想要从根到任何叶节点(金字塔底部)的代价最大的路线。好吧，它实际上不是树，因为一个节点可能有两个父节点，实际上你可以从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(你有两个)。
最简单的方法是自下而上，你有0 (N)的复杂性。在这种情况下，不需要动态规划或递归。只需重新构建一个树，其中较高层次的数量是较低层次数量的最大值。
我建议你看看Dijkstra的算法和A*。
我相信Dijkstra's比A*更准确，但更慢。
如果这些数字表示在图的两个节点之间移动的成本，那么Dijkstra算法将找到最短路径。
我认为即使你使用建议的Dijkstra算法，你仍然需要测试每条路由。首先因为没有单一的起点和终点，但是终点有50个起点。因此，该算法必须测试50次。
因为每个选项都有两条路径，所以没有办法跳过一条。你永远不能排除一条路，直到你走到最后。
所以我不认为有一个更快的方法来找到最长的路径(所以不是最短的Dijkstra的算法)，然后测试所有的路线。
你可以把树看作DAG做一个拓扑排序然后松弛(松弛到最大值而不是最小值)每条边，因为它们在拓扑排序O(E+V)