как определить максимальную стоимость маршрута в числовой пирамиде высотой n
У меня есть такая числовая пирамида
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, проблема немного сложнее.
Я думаю, что я начинаю с самого низа, начиная с самого мощного цифры, но вскоре я понял, что максимальная стоимость маршрута необязательно начинается или заканчивается большими цифрами.
Тогда я подумал, что, возможно, индексы границ (куда вы можете пойти дальше от числа) помогут, но я даже не реализовал это, потому что я предположил, что он все еще использует много ресурсов и не является оптимальным.
И теперь я в замешательстве, как возобновить размышления об этой проблеме... любые советы приветствуются
6 answers
Думайте о своей пирамиде как о дереве с корнем на вершине пирамиды: я думаю, вам нужен маршрут с максимальной стоимостью от корня до любого из конечных узлов (нижняя часть пирамиды). Хорошо, на самом деле это не дерево, потому что у узла может быть два родителя, на самом деле вы можете добраться до узла на уровне 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 (и у вас их два).
Самый простой способ - идти снизу вверх, и у вас есть O(N) сложность. В этом случае вам не нужно динамическое программирование или рекурсия. Просто составьте другое дерево, где число на более высоком уровне равно максимальному числу чисел нижнего слоя.
Я предлагаю вам взглянуть на Алгоритм Дейкстры и A*.
Я считаю, что Дийкстра более точен, чем A*, но медленнее.
Если числа представляют стоимость перемещения между 2 узлами графа, то Алгоритм Дейкстры найдет кратчайший путь.
Я думаю, что даже если вы используете предложенный алгоритм Дейкстры, вам все равно придется тестировать каждый маршрут. Прежде всего потому, что нет единой начальной и конечной точки, но есть 50 начальных точек для конечной точки. Таким образом, алгоритм должен быть протестирован 50 раз.
И поскольку у каждого варианта есть 2 пути, пропустить один из них невозможно. Вы никогда не можете исключить путь, пока не окажетесь в самом конце.
Поэтому я не думаю, что есть более быстрый способ найти самый длинный путь (так что не самый короткий, как в алгоритме Дейкстры), затем протестировать все маршруты.
Поскольку вы можете рассматривать дерево как DAG, выполните топологическую сортировку, затем расслабьте (расслабьтесь до максимума, а не до минимума) каждое ребро, как они находятся в топологической сортировке O(E+V).