В поисках связующего дерева с целевой ценой

Question

Я довольно озадачен этим.Новое в публикации, так что извините, если это глупый вопрос.

Скажем, нам дан график G = (V, E) с взвешенными ребрами.Я хотел бы создать остовное дерево G с целевой стоимостью c, где стоимость связующего дерева определяется как сумма всех его краевых затрат.Как мы можем определить, существует ли остовное дерево G со стоимостью c?

Answer 1

Вот удар в это.Вы можете использовать динамическое программирование для решения проблемы суммы подмножеств, а затем для каждого возможного подмножества просто проверить, образует ли оно остовное дерево.Общая формулировка суммы подмножеств выглядит следующим образом: пусть C [i, S] будет логическим значением оператора

Существует подмножество S, которое суммирует с i

Пусть е - произвольное ребро.Тогда обычно повторяется:

C [i, S 'U e] = истинно, если C [i, S'] или C [i - вес (е), S ']

(либо вы используете ребро e, либо не используете его и убедитесь, что использование ребра e не образует цикл).

Если целевая стоимость равна c, вам необходимо выполнитьn развертки для каждого 1 <= i <= c, где n - количество ребер. </p>

Наконец, убедитесь, что количество выбранных ребер на 1 меньше количества вершин, и все они связаны.

Другой подход состоит в том, чтобы просто использовать обратную рекурсию для поиска по всем связующим деревьям <= targetCost. </p>