Проблема с наибольшим независимым набором с использованием динамического программирования

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

Например, рассмотрим следующее бинарное дерево. Самый большой независимый набор (LIS) равен {10, 40, 60, 70, 80}, а размер LIS равен 5.

Решение динамического программирования решает данную проблему, используя решения подзадач восходящим образом. Можно ли решить данную задачу, используя решения подзадач? Если да, то каковы подзадачи? Можем ли мы найти наибольший размер независимого набора (LISS) для узла X, если мы знаем LISS для всех потомков X? Если узел рассматривается как часть ЛИС, то его потомки не могут быть частью ЛИС, но могут быть его внуки. Ниже приводится оптимальное свойство подструктуры.

1) Оптимальная основа:
Пусть LISS(X) указывает размер наибольшего независимого множества дерева с корнем X.

     LISS(X) = MAX { (1 + sum of LISS for all grandchildren of X),
                     (sum of LISS for all children of X) }

Идея проста: для каждого узла X есть две возможности: либо X является членом множества, либо не является членом. Если X является членом, то значение LISS(X) равно 1 плюс LISS всех внуков. Если X не является членом, то значение представляет собой сумму LISS всех дочерних элементов.

2) Перекрывающиеся подзадачи
Ниже приведена рекурсивная реализация, которая просто следует рекурсивной структуре, упомянутой выше.

Временная сложность описанного выше наивно-рекурсивного подхода экспоненциальна. Следует отметить, что приведенная выше функция снова и снова вычисляет одни и те же подзадачи. Например, LISS узла со значением 50 оценивается для узла со значениями 10 и 20, поскольку 50 является внуком 10 и дочерним элементом 20.

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

Ниже приведена реализация решения на основе динамического программирования. В следующем решении к узлам дерева добавляется дополнительное поле «liss». Начальное значение «liss» равно 0 для всех узлов. Рекурсивная функция LISS() вычисляет liss для узла, только если он еще не установлен.

Временная сложность: O (n), где n — количество узлов в данном двоичном дереве.
В качестве упражнения можно попробовать следующие расширения приведенного выше решения.
1) Расширьте приведенное выше решение для n-арного дерева.
2) Приведенное выше решение изменяет данную структуру дерева, добавляя дополнительное поле «liss» к узлам дерева. Расширьте решение, чтобы оно не изменяло древовидную структуру.
3) Приведенное выше решение возвращает только размер LIS, но не печатает элементы LIS. Расширьте решение, чтобы распечатать все узлы, являющиеся частью ЛИС.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.