(Возможный) контрпример к общему минимальному покрытию вершин на дереве Алго и мой подход

Question

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

C (x) = min (1 + сумма (C (i) для i у детей x), len (дети x)) + sum(C(i) для i у внуков x))

Предполагая, что дерево укоренено в узле 1, я попробовал этот алгоритм для цепочки узлов 1-2-3-4-5-6, чтобы получить следующий C (i):

| C(1) | C (2) | С (3) | C (4) | C (5) | C (6) |

| 3 | 2 | 2 | 1 | 1 | 1 |

Тем не менее, правильный ответ для C(1) должен быть 2, что достигается путем маркировки узлов 2 и 5.

Я решил попробовать свой собственный подход, который подробно описан ниже:

int solve(int curr, int height){
    if(dp[curr][height] > -1) return dp[curr][height];
    if(int(children[curr].size()) == 0) return dp[curr][height] = height > 1 ? 1 : 0;
    if(height == 3){
        int ret = 1;
        for(int i = 0; i < int(children[curr].size()); i++){
            int next = children[curr][i];
            ret += solve(next, 1);
        }
        return dp[curr][height] = ret;
    }
    int ret1 = 0; int ret2 = 1;
    if(height == 2){
        for(int i = 0; i < int(children[curr].size()); i++){
            int next = children[curr][i];
            ret1 += solve(next, 3); ret2 += solve(next, 1);
        }
        return dp[curr][height] = min(ret1, ret2);
    }
    for(int i = 0; i < int(children[curr].size()); i++){
        int next = children[curr][i];
        ret1 += solve(next, 2); ret2 += solve(next, 1);
    }
    return dp[curr][height] = min(ret1, ret2);
}

curr - текущий узел, в котором мы находимся, а height - это расстояние от ближайшего отмеченного узла над ним. Идея состоит в том, что, как только узел имеет высоту = 3, он должен быть отмечен в этом конкретном пути. В противном случае мы можем пропустить пометку на данный момент. Исключением является листовой узел, который должен быть помечен, если соседний узел не помечен.

Может кто-нибудь проверить правильность моего подхода, а также объяснить, почему первый алгоритм не проходит цепной тест?

Заранее спасибо!

Answer 1

Первый алгоритм действительно работает. В минимальном покрытии вершин каждое ребро должно быть инцидентно как минимум одной вершине. В вашем "контрпримере" не отмечены ни вершины 3, ни 4, поэтому у ребра (3,4) нет вершины в наборе. Таким образом, {2, 5} не является покрытием вершин.

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

И даже если вы используете неправильное определение, ваш подход не будет работать. Вершина с расстоянием 3 до отмеченной родительской вершины не должна быть отмечена. Посмотрите на этот пример:

  0
  |
  1
  |
  2
 / \
3   4
    |
    5

В этом примере, если отмечена вершина 0, вершины 3 и 4 также помечаются, потому что они находятся на расстоянии 3 от вершины. Но нет необходимости отмечать вершину 4, вместо этого мы могли бы также отметить вершину 5. Очевидно, что в этом примере это даст такое же количество вершин, но я уверен, что вы могли бы расширить это на более крупный пример, где ваш подход терпит неудачу.

Идея решения для другого определения:

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

Вы можете сделать это снова с глубиной поиска и DP. Пусть dp[v] будет кратчайшим расстоянием между v и отмеченным узлом в поддереве v. Чтобы вычислить v, сначала вычислите все значения dp дочерних узлов, а затем решите, нужно ли это отмечать или нет. Если у любого ребенка dp[child] = 2, вам нужно отметить v и поставить dp[v] = 0. В противном случае вам не нужно отмечать его и dp[v] = min(dp[children] + 1), В конце вам также может понадобиться отметить корневой узел.

Примечание: я не проверял это.