How to determine the maximum cost of a route in an n high numerical pyramid

Question

I have a digital pyramid like this

7 4 8 1 8 9 2 4 6 7 4 6 7 4 9 4 9 7 3 8 8 routes: 32 

each number indexed by how powerful in its line.

  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 ) 

this pyramid has 2 ^ (n-1) routes (you can go through the 2-form form of each number) If the pyramid is above this minimum, you can easily calculate all the routes and compare with each other. But if you have 50 pyramids with 562949953421312 routes, the problem is a little more complicated.

I start from the very beginning, starting with the most powerful numbers, but I soon realized that the maximum cost of a route does not necessarily begin or end with large numbers.

Then I thought that maybe secret indexes (where you can go further from the number) would help, but I didn’t even implement this because I assumed that it still uses a lot of resources and is not optimal.

And now I'm confused how to restart thinking about this problem ... any advice appreciated

Answer 1

Think of your pyramid as a tree with a root at the top of the pyramid: I think you need a route with a maximum cost from the root to any of the leaf nodes (at the bottom of the pyramid). OK, this is actually not a tree, because a node can have two parents, in fact, you can go to node at level i no more than two nodes at level i-1 .

In any case, I think you can calculate the route with the maximum cost using dynamic programming. Let me rewrite your data as a matrix:

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

and let the missing elements of the matrix be 0. Let us call this matrix v (for values). Now you can build the matrix c (for costs), where c(i,j) is the maximum cost to reach the node tree at position (i,j) . You can calculate it with this repetition:

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

where c(h,k) is 0 when you get to the position from the matrix. Essentially, we say that the maximum cost of switching to a node in position (i,j) is the cost of the node itself plus the maximum between the costs of getting two possible parents at the i-1 level.

Here is an example c for your example:

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

For example, take i=3, j=2 :

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

From c you see that the most expensive traffic costs 48 (and you have two of them).

Answer 2

The easiest way is to go from bottom to top, and you have O (N) specificity. In this case, you do not need dynamic programming or recursion. Just create another tree where the number at a higher level is the maximum amount of the bottom layer.

Answer 3

I suggest you look at Dijkstra Algorithm and A * .

I find that Dijkstra is more accurate than A *, but slower.

Answer 4

If the numbers represent the cost of moving between the two nodes of the graph, then Dijkstra's algorithm will find the shortest path.

Answer 5

I think that even if you use the proposed Dijkstra algorithm, you still have to check every route. First of all, because there is no single start and end point, but there are 50 starting points for the end point. Therefore, the algorithm should be tested 50 times.

And since each option has 2 ways, it is impossible to skip it. You can never rule out the path until you are at the very end.

Therefore, I do not think that there is a faster way to find the longest path (and not the shortest, as in the Dijkstra Algorithm), then check all the routes.

Answer 6

as you can consider the DAG tree. Do a topological sort, then relax (relax to the maximum, not the min), each edge, because it is in the topological order O (E + V).