Гипотетический вопрос. Скажем, мне дано дерево T и список пар узлов (x, y) в T. Меня спрашивают, сколько из двух пар я могу подключить одновременно (connect x with y), используя каждое ребро в T не более одного раза ,Подключение узлов в дереве
Как это сделать?
Это не NP-твердый для деревьев. Например, вы можете сделать следующее.
Корни дерева произвольно.
Для каждой вершины v вычислите оптимальное решение, ограниченное поддеревом v.
Кроме того, для каждого v для каждого пути p, который содержит родительский край v, вычисляет оптимальное решение, ограничиваемое поддеревом v, за исключением пути p.
(2) и (3) может быть вычислен с использованием решений меньших проблем в поддереве v.
Вероятно, проще всего посмотреть на шаги 1, 2 и 3 и выяснить, что такое повторение, но для того, чтобы дать вам представление, (2) можно вычислить, взяв максимум из нескольких решений: решения для детей v (т. е. сумма решений, полученных на шаге 2 для каждого ребенка) и по одному для каждого пути, который включает v плюс решения для второго шага для других детей (это будет по существу включать сумму одного или два решения, полученные на этапе 3 для детей v, плюс сумма решений, полученных на этапе 2 для других детей).
Похоже, вы описываете проблему коммивояжера? Где вы пытаетесь посетить как можно больше узлов без использования какого-либо края в два раза? Это NP-жесткий и в центре внимания многих исследований. http://en.wikipedia.org/wiki/Travelling_salesman_problem – TZHX 2010-11-26 20:52:32