Блог

существует ли алгоритм в O (n) для вычисления максимального соответствия для взвешенного дерева?

Я нашел только алгоритмы для невзвешенных деревьев или двудольных графов. У меня возникли некоторые проблемы с преобразованием этих алгоритмов для деревьев. С помощью ручки и бумаги я также обнаружил, что алгоритм для невзвешенных деревьев не работает для взвешенных деревьев. Я думаю, что рекурсивно это заняло бы больше, чем O (n), каковы альтернативы? Может быть, динамическое программирование?

Помощь была бы очень признательна. Спасибо 🙂

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

Вычисление легко выполняется в postorder (DFS): максимальное совпадение с корнем для узла — это просто сумма наилучших совпадений для каждого дочернего поддерева. Максимальное совпадение с корнем для узла — это наилучшее совпадение с корнем, сопоставленным с неподвластным корню поддеревом для одного из его дочерних элементов, добавляемое к лучшим совпадениям от других дочерних элементов.