Рассмотрим дерево, в котором каждый узел связан с системным состоянием и содержит последовательность действий, выполняемых в системе.Максимизация усиления на деревьях
Корень - это пустой узел, связанный с исходным состоянием системы. Состояние, связанное с узлом n
, получается путем применения последовательности действий, содержащихся в n
, к исходному состоянию системы. Последовательность действий узла n
получается путем очередности нового действия в последовательности действий родителя.
Перемещение от узла к другому (то есть добавление нового действия в последовательность действий) создает коэффициент усиления, который привязан к краю, соединяющему два узла.
Некоторые «математика»:
- каждая система состояние
S
связанно со значениемU(S)
- коэффициента усиления достигается с помощью узла
n
, связанного с состояниемS
не может быть больше, чемU(S)
и меньше, чем0
- Если
n
иm
являются узлами в дереве, аn
является родителемm
,U(n) - U(m) = g(n,m)
, то есть коэффициент усиления на границе междуn
иm
представляет собой сокращение отU
n
к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) становится меньше и меньше по мере увеличения глубины.
Почему вы выбора узлов в соответствии с U (N) (то есть самое высокое значение коэффициента усиления, которое может быть достигнуто за счет узла п)? Так как U (n) становится все меньше и меньше по мере увеличения глубины узла, выбор узлов с наивысшим U (n) приводит к тому, что всегда выбираются узлы на первых уровнях, а затем листья. Это должно привести к решению грубой силы (изучить все дерево). – Eleanore
@Eleanore Я понял U (n) как верхнюю границу лучших решений, которые могут быть достигнуты от n (т. Е. Верхняя граница длины пути между корнем и листьями ниже n). После повторного чтения вашего вопроса это должно быть U (n) + gain (n), не так ли? – Julien
Предположим, что n и m являются двумя узлами в дереве, так что n является родительским элементом m. Затем коэффициент усиления между n и m может быть получен следующим образом: коэффициент усиления = U (n) - U (m). Таким образом, U (n) можно рассматривать как верхнюю границу коэффициентов усиления ребер, выходящих из n. Это связано с тем, что U (m) не может быть больше U (n), так как U (n) становится меньше и меньше по мере увеличения глубины. На самом деле максимизация коэффициента усиления эквивалентна минимизации U (n) из-за этого отношения. Таким образом, должен ли он способствовать решению, максимизируя его? – Eleanore