Минимальная вершина обложки дерева: формула динамического программирования

Question

Я пытаюсь понять, как сформулировать проблему нахождения вершинного покрытия дерева минимального размера в качестве проблемы динамического программирования, и у меня есть некоторые проблемы. Для меня наиболее интуитивно понятным является формулировка нединамического программирования, включающая поиск по глубине. По сути, это включает в себя выполнение DFS для листовых узлов, включая их родительские узлы в вершине вершины минимального размера, и повторение до корня. Псевдокод, как это:

// DFS based solution 
find_minimum_vertex_cover_dfs(root) { 
    // leaf nodes aren't in minimum size vertex cover 
    if (root == NULL || isLeafNode(root)) { 
     return; 
    } 

    for (each child node of root) { 
     find_minimum_vertex_cover_dfs(child node); 
     // child isn't in minimum size vertex cover so need to cover edge 
     // from current root to child by including current root 
     if (!isInMinCover(child node)) { 
      include root in minimum vertex cover; 
     } 
    } 
} 

формулировка динамического программирования, который я получил от here выглядит следующим образом:

DynamicVC(root): 
    for each child c: 
     Best[c][0], Best[c][1] = DynamicVC(c) 

    withoutRoot = sum over all c of Best[c][1] 
    withRoot = 1 + sum over all c of min(Best[c][0], Best[c][1]) 

    return (withoutRoot, withRoot) 

Я думаю, я понимаю идею подзадач будучи вычисления минимального размера вершинного покрытия для поддерево, укорененное в каждой вершине, включая эту вершину в обложке и исключающую эту вершину из обложки. У меня есть два вопроса:

1. Мне кажется наиболее естественным использовать тот факт, что листовые узлы никогда не будут находиться в минимальном покрытии вершин и, следовательно, будут использовать решение на основе DFS. Зачем использовать динамическое программное решение этой проблемы?
2. Я привык к построению матрицы динамического программирования снизу итеративно без фактического использования рекурсии. В этом случае, однако, поскольку мне нужно начать с вычисления решений для листовых узлов, пересекающих дерево с использованием рекурсии для построения матрицы динамического программирования из листовых узлов, кажется мне наиболее интуитивным. Мне просто кажется странным, потому что все проблемы динамического программирования, над которыми я работал до сих пор, избегали необходимости в этом. Я что-то упустил?

Редактировать: Поскольку я думал об этом, возможно, что-то меня смутило, так это то, что в этом случае репликация DFS на дереве является более знакомым мне. Я выполнял множество проблем с динамическим программированием, но это первый из них, включающий обход дерева/графа, а в других проблемах я могу просто использовать некоторые циклы для вычисления больших и больших подзадач. Я полагаю, что я мог бы сделать версию динамического программирования более знакомой мне, используя явный стек и проводя обход дерева таким образом, а не через рекурсию. Имеет ли это смысл?

Answer 1

1: Нет действительно веской причины. Это просто работает, поэтому не используйте его. Для меня решение DP, которое вы показали, более интуитивно понятное, чем рекурсивное.

2: Динамическое программирование о подзадачах меморандума рекурсивного решения. Выполнение алгоритма DP часто включает сначала определение рекурсии, а затем добавление к нему memoization. Рекурсивное решение может быть автоматически преобразовано в DP: просто создайте глобальную хеш-таблицу типа (subproblem id -> result) и в начале проверки рекурсивного вызова, если хэш-карта уже содержит результат для данной подзадачи, если это так, верните ее сразу же, иначе вычислите его и помещать в хэшмап. Такой подход часто будет таким же быстрым, как упоминавшийся выше подход «снизу вверх».