Как определить максимальную стоимость маршрута в высокой числовой пирамиде

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 максимум из двух узлов на уровне i-1.

В любом случае, я думаю, вы можете рассчитать маршрут с максимальной стоимостью, используя динамическое программирование. Позвольте мне переписать ваши данные в виде матрицы:

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

, как вы можете. Рассмотрите дерево как DAG. Сделайте топологическую сортировку, затем ослабьте (ослабьте до максимума, не мин.) Каждое ребро, поскольку они находятся в топологической сортировке O (E + V).

Answer 4

Я думаю, что даже если вы используете предложенный алгоритм Дейкстры, вам все равно придется тестировать каждый маршрут.Прежде всего потому, что нет единой начальной и конечной точки, но есть 50 начальных точек для конечной точки.Таким образом, алгоритм должен быть протестирован 50 раз.

И поскольку каждая опция имеет 2 пути, пропустить один из них невозможно.Вы никогда не сможете исключить путь, пока не окажетесь в самом конце.

Поэтому я не думаю, что есть более быстрый способ найти самый длинный путь (поэтому не самый короткий, как в алгоритме Дейкстры), чем тестировать все маршруты.

Answer 5

Если числа представляют стоимость перемещения между 2 узлами графа, то Алгоритм Дейкстры найдет кратчайший путь.

Answer 6

Я предлагаю вам взглянуть на Алгоритм Дейкстры и A *.

Я считаю, что Дейкстра более точен, чем А *, но медленнее.