如何确定一个较高的数字金字塔最大路由成本 [英] how to determine maximum route cost in a n high numeric pyramid

问题描述

我有这样一个数字金字塔

I've got a numeric 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

每个数字由多么强大的产品线索引。

every 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 )

在这个金字塔有2 ^（N-1）航线（你可以走2路形成每个号码） 如果金字塔高该低，很容易就可以计算出所有路由，并比较海誓山盟。但是，如果你有一个50高的金字塔562949953421312路线，这个问题有点难度。

in this pyramid there are 2^(n-1) routes (you can go 2 way form each number) If the pyramid high this low, it's easy you can calculate all the routes, and compare to eachother. But if you have an 50 high pyramid with 562949953421312 routes, the problem little bit more difficult.

我thoght我从底层做起，从最强大的数字开头，但很快我意识到，最大的路由开销不necesserly开始或结束在大的数字。

I thoght I start from the bottom beginning from the most powerful numbers, but soon i realized, the max route cost ain't necesserly start or end up in big numbers.

然后我想，也许secoundary指标（在哪里可以从一个数字去futher）会有所帮助，但我甚至didin't实现该becouse我认为它仍然使用多少资源，而不是最优的。

Then I thought maybe secoundary indexes (where can you go futher from a number) will help, but I didin't even implement that becouse I assumed its still uses much resources and not optimal.

而现在我很困惑如何重新思考这个问题...... pciated任何意见AP $ P $

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

推荐答案

想想你的金字塔与根在金字塔顶部的树：我觉得你想要从根本上最高性价比的任何途径叶节点（金字塔底部）。好吧，这实际上不是一棵树，因为一个节点可能有两个父母，其实你可以到一级我从最多两个节点级<$ C节点$ C> I-1 。

Think of your pyramid as a tree with the root at the top of the pyramid: I think you want the route with the maximum cost from the root to any of the leaf nodes (bottom of the pyramid). OK, it's not actually a tree, because a node may have two parents, in fact you can get to a node at level i from at most two nodes at level i-1.

不过，我想你可以通过使用动态规划计算的最大成本路径。让我重写你的数据在矩阵状的方式：

Anyway, I think you can compute the route with the maximum cost by using dynamic programming. Let me rewrite your data in a matrix like way:

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）。您可以使用此复发计算它：

and let the missing elements of the matrix be 0. Let's call this matrix v (for values). Now you can build a matrix c (for costs) where c(i,j) is the maximum cost for reaching the tree node at position (i,j). You can compute it with this recurrence:

C（I，J）= V（I，J）+最大值{C（I-1，J-1），C（I-1，J）}

其中， C（H，K） 0，当你到一个位置出来的矩阵。从本质上说，最大的成本获取到节点的位置（I，J）是节点本身的成本加上获得其两个可能的成本之间的最大父母级 I-1 。

where c(h,k) is 0 when you get to a position out of the matrix. Essentially we say that the maximum cost for getting to node at position (i,j) is the cost of the node itself plus the maximum between the costs of getting to its two possible parents at level 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（你有其中两个）。

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

这篇关于如何确定一个较高的数字金字塔最大路由成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！