1

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

Корень - это пустой узел, связанный с исходным состоянием системы. Состояние, связанное с узлом 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

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

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

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

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

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

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

ответ

0

Как вы заметили, ветка и граница могут использоваться для решения вашей проблемы. Просто увеличьте узлы, которые кажутся наиболее перспективными до тех пор, пока вы не найдете полные решения, отслеживая самое известное решение. Если узел имеет 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 
+0

Почему вы выбора узлов в соответствии с U (N) (то есть самое высокое значение коэффициента усиления, которое может быть достигнуто за счет узла п)? Так как U (n) становится все меньше и меньше по мере увеличения глубины узла, выбор узлов с наивысшим U (n) приводит к тому, что всегда выбираются узлы на первых уровнях, а затем листья. Это должно привести к решению грубой силы (изучить все дерево). – Eleanore

+0

@Eleanore Я понял U (n) как верхнюю границу лучших решений, которые могут быть достигнуты от n (т. Е. Верхняя граница длины пути между корнем и листьями ниже n). После повторного чтения вашего вопроса это должно быть U (n) + gain (n), не так ли? – Julien

+0

Предположим, что n и m являются двумя узлами в дереве, так что n является родительским элементом m. Затем коэффициент усиления между n и m может быть получен следующим образом: коэффициент усиления = U (n) - U (m). Таким образом, U (n) можно рассматривать как верхнюю границу коэффициентов усиления ребер, выходящих из n. Это связано с тем, что U (m) не может быть больше U (n), так как U (n) становится меньше и меньше по мере увеличения глубины. На самом деле максимизация коэффициента усиления эквивалентна минимизации U (n) из-за этого отношения. Таким образом, должен ли он способствовать решению, максимизируя его? – Eleanore