Минимальный вес вершинной оболочки дерева

Существует существующий вопрос, касающийся деревьев, где вес вершины равен ее степени, но меня интересует случай, когда вершины могут иметь произвольные веса.

Это не домашняя работа, но это один из вопросов в руководстве по разработке алгоритма, которое я сейчас читаю; набор ответов дает решение в виде

  1. Выполняйте DFS, на каждом шаге обновляйте Score[v][include], где v - вершина, а include - true или false;
  2. Если v является листом, установите Score [v] [false] = 0, Score [v] [true] = w v, где w v - вес вершины v.
  3. Во время DFS при переходе вверх от последнего дочернего элемента узла v обновите Score[v][include]: Score[v][false] = Сумма для c у детей (v) Score[c][true] и Score [v] [true] = w v + сумма для c у детей (v) из min(Оценка [c][true]; Оценка [c][false])
  4. Извлеките фактическое покрытие, возвращая счет.

Тем не менее, я не могу перевести это на что-то, что работает. (В ответ на комментарий: то, что я до сих пор пробовал, это рисование небольших графиков с весами и прохождение алгоритма на бумаге вплоть до четвертого шага, где часть "извлечь фактическое покрытие" не прозрачна.)

В ответ Али отвечает: так что предположим, у меня есть этот график с вершинами, заданными A и т. д. и вес в паранах после:

A(9)---B(3)---C(2) \ \ E(1) D(4)

Правильный ответ явно {B,E},

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

  • score[D][false] = 0; score[D][true] = 4
  • score[C][false] = 0; score[C][true] = 2
  • score[B][false] = 6; score[B][true] = 3
  • score[E][false] = 0; score[E][true] = 1
  • score[A][false] = 4; score[A][true] = 12

Итак, мой вопрос в основном, что теперь? Делая простую вещь и перебирая score вектор и решение, что является самым дешевым в местном масштабе, не работает; вы в конечном итоге в том числе B, Решение, основанное на родителе и чередовании, также не работает: рассмотрим случай, когда вес E является 1000; теперь правильный ответ {A,B} и они рядом. Возможно, это не должно сбивать с толку, но, честно говоря, я в замешательстве.

Источник

1 ответ

Фактического отката не выполняется (или не требуется). Решение использует динамическое программирование, чтобы избежать обратного отслеживания, поскольку это займет экспоненциальное время. Я предполагаю, что "оценка с возвратом" означает, что оценка содержит частичные результаты, которые вы получили бы, выполняя поиск с возвратом.

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

Ответ дается путем рекурсивного вычисления Score. Стоимость исключения вершины - это стоимость включения ее дочерних элементов. Однако стоимость включения вершины - это то, что менее затратно, включая стоимость включения ее дочерних элементов или их исключения, потому что оба варианта разрешены.

Как предполагает ваше решение, это можно сделать с помощью DFS в пост-заказе за один проход. Уловка состоит в том, чтобы включить вершину, если Score говорит, что она должна быть включена, и включить ее дочерние элементы, если она должна быть исключена, иначе мы бы исключили две смежные вершины.

Вот какой-то псевдокод:

find_cover_vertex_of_minimum_weight(v)
  find_cover_vertex_of_minimum_weight(left children of v)
  find_cover_vertex_of_minimum_weight(right children of v)
  Score[v][false] = Sum for c in children(v) of Score[c][true]
  Score[v][true] = v weight + Sum for c in children(v) of min(Score[c][true]; Score[c][false])
  if Score[v][true] < Score[v][false] then
    add v to cover vertex tree
  else
    for c in children(v)
      add c to cover vertex tree
Источник

На самом деле это не означало ничего запутанного, и это просто динамическое программирование, вы, кажется, почти понимаете весь алгоритм. Если я хочу сделать это более ясным, я должен сказать:

  1. сначала преформуйте DFS на вашем графике и найдите листья.
  2. для каждого листа присваивайте значения, как говорит алгоритм.
  3. Теперь начните с листьев и присвойте значения каждому родительскому листу по этой формуле.
  4. начните присваивать значения родителю узлов, которые уже имеют значения, пока не дойдете до корня вашего графа.

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

Изменить только для объяснения ваших изменений в вопросе. Поскольку у вас есть следующий график, и ответ явно B,E, но вы, хотя этот алгоритм просто дает вам B, и вы ошибаетесь, этот алгоритм дает вам B и E.

A(9)---B(3)---C(2) \ \ E(1) D(4) 

score[D][false] = 0; score[D][true] = 4
score[C][false] = 0; score[C][true] = 2
score[B][false] = 6 this means we use C and D; score[B][true] = 3 this means we use B
score[E][false] = 0; score[E][true] = 1
score[A][false] = 4 This means we use B and E; score[A][true] = 12 this means we use B and A.

и вы выбираете 4, поэтому вы должны использовать B и E. если это был просто B, ваш ответ был бы 3. но, как вы находите правильно, ваш ответ 4 = 3 + 1 = B + E.

Также когда E = 1000

A(9)---B(3)---C(2) \ \ E(1000) D(4)

это на 100% правильно, что ответ B и A, потому что неправильно использовать E только потому, что вы не хотите выбирать соседние узлы. с помощью этого алгоритма вы найдете ответ A и B, и просто проверив, вы можете найти его тоже. предположим, что это охватывает:

C D A = 15
C D E = 1006
A B = 12

Хотя первые два ответа не имеют смежных узлов, но они больше, чем последний ответ, у которых есть смежные узлы. так что лучше всего использовать A и B для укрытия.

Источник
Другие вопросы по тегам