Максимизация усиления на деревьях

Question

Рассмотрим дерево, в котором каждый узел связан с системным состоянием и содержит последовательность действий, выполняемых в системе.

Корень - это пустой узел, связанный с исходным состоянием системы. Состояние, связанное с узлом n, получается путем применения последовательности действий, содержащихся в n, к исходному состоянию системы. Последовательность действий узла n получается путем очередности нового действия в последовательности действий родителя.

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

Некоторые «математика»:

• каждая система состояние S связанно со значением U(S)
• коэффициента усиления достигается с помощью узла n, связанного с состоянием S не может быть больше, чем U(S) и меньше, чем 0
• Если n и m являются узлами в дереве, а n является родителем m, U(n) - U(m) = g(n,m), то есть коэффициент усиления на границе между n и m представляет собой сокращение от Un к m

Смотрите рисунок для примера.

Моя цель состоит в один найти путь в дереве, что гарантирует высокий коэффициент усиления (где выигрыш пути вычисляется путем суммирования всех завоеваний ребер на пути):

Path* = arg max_{path} (sum g(n,m), for each adjacent n,m in path) 

Обратите внимание, что дерево NOT, известное в начале, и, таким образом, решение, которое не требует посещения всего дерева (отбрасывание тех путей, которые, конечно же, не приводят к оптимальному решению), чтобы найти оптимальное решение, было бы лучший вариант.

Примечание: Я получил ответ here и here для аналогичной задачи в автономном режиме, то есть, когда граф был известен. Однако в этом контексте дерево неизвестно, и, таким образом, алгоритмы, такие как Bellman-Ford, будут работать не лучше, чем подход с грубым подходом (как это было предложено). Вместо этого, я хотел бы построить что-то похожее на backtracking без построения всего дерева, чтобы найти лучшее решение (ветвь и связанная?).

EDIT: U (S) становится меньше и меньше по мере увеличения глубины.

Answer 1

Как вы заметили, ветка и граница могут использоваться для решения вашей проблемы. Просто увеличьте узлы, которые кажутся наиболее перспективными до тех пор, пока вы не найдете полные решения, отслеживая самое известное решение. Если узел имеет U (S) ниже самого известного решения во время процесса, просто пропустите его. Когда у вас больше нет узла, все готово.

Ниже приведен алгоритм:

pending_nodes <- (root) 
best_solution <- nothing 

while pending_nodes is not empty 
    Drop the node n from pending_nodes having the highest U(n) + gain(n) 

    if n is a leaf 
     if best_solution = nothing 
      best_solution <- n 
     else if gain(best_solution) < gain(n) 
      best_solution <- n 
     end if 
    else 
     if best_solution ≠ nothing 
      if U(n) + gain(n) < gain(best_solution) 
       stop. best_solution is the best 
      end if 
     end if 

     append the children of n to pending_nodes 
    end if 
end while