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