“(1:k) Сопоставление с деревом” - Разрешимо за полиномиальное время?

Question

Несколько месяцев назад там был хороший вопрос в отношении "1: проблема с совпадением n" и, похоже, не существует многовременного алгоритма.

Я хотел бы добавить ограничения, чтобы найти максимальное соответствие для задачи сопоставления 1: n с помощью полиномиального алгоритма.Я хотел бы сказать:"Для вершины A1 выберите либо {B1, B2, B5}, либо {B2,B3}, если вершины еще не взяты из другой A-вершины", т.е.Я бы не допустил всех возможных комбинаций.

Это можно было бы выразить, если бы мы ввели вспомогательные вершины H для каждого выбора и заменили ребра деревьями => мы получаем проблему, аналогичную обычному двудольному сопоставлению.Каждая вершина A или B может иметь только одно ребро в сопоставлении.Ребра, ведущие к вершинам в H или из них, либо все находятся в сопоставлении, либо ни одно из них не присутствует в сопоставлении.Представьте себе следующий трехчастный график:

Теперь определите h_ij="корневое дерево, содержащее H_ij", чтобы легко выразить соответствие:

• Тогда в примере M ={h12,h22} было бы одним "максимальным" совпадением, хотя задействованы не все вершины из B
• Набор {h12,h23} не является совпадающим, потому что тогда B3 пришлось бы выбирать дважды.

Была бы тогда эта проблема разрешима за полиномиальное время?Если да, существует ли многовременное решение для взвешенного варианта (w(h_ij))?Если нет, не могли бы вы поспорить или даже доказать это для такого "простого человека", как я, или предложить другие ограничения для решения проблемы сопоставления 1: n?

Например.может ли граф быть преобразован в общий граф, который затем можно было бы решить с помощью взвешенного сопоставления для общих графов?Или мог бы ответвления или даже подходящие леса помочь здесь?

PS:это не домашнее задание ;-)

Answer 1

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

Кажется, вы не очень четко определили свою проблему, но если я правильно понял ваше намерение, похоже, что ваша проблема NP завершена (и "эквивалентна" Упаковка набора).

Мы можем предположить, что допустимые размеры наборов одинаковы (k) для всех A_i, чтобы найти соответствие [1: k], так как любой другой размер набора может быть проигнорирован.Чтобы найти максимальное k, мы просто запускаем алгоритм для [1:k] для k = 1,2,3..и т.д.

Итак, ваша проблема в том (я думаю ...), что:

Дано m семейств множеств F_i = {S_1i, .., S_n(i)i} (|F_i| = размер F_i = n (i), не обязательно должен совпадать с |F_j |), каждый набор размера k, вы должны найти по одному набору из каждого семейства (скажем, S_i), такому, что

• S_i и S_j не пересекаются для любого i neq j.
• количество S_i является максимальным.

Мы можем показать, что он NP-полон для k = 3 в два этапа:

1. NP-Полная задача Упаковка набора может быть уменьшено это.Это показывает, что это NP-Сложно.
2. Ваша проблема заключается в NP и может быть сведена к набору упаковки.Это и 1) подразумевает, что ваша проблема NP-завершена.Это также помогает вам использовать любые аппроксимационные / рандомизированные алгоритмы, уже существующие для упаковки наборов.

Проблема заключается в упаковке набора:

Учитывая n множеств S_1, S_2, ..., S_n, найдите среди них максимальное количество попарно непересекающихся множеств.

Эта проблема остается NP-завершенной , даже если |S_1| = |S_2| = ...= |S_n| = 3 и называется проблемой упаковки из 3 наборов.

Мы будем использовать это, чтобы показать, что ваша проблема NP-сложна, предоставляя простое сокращение от упаковки из 3 наборов к вашей проблеме.

Учитывая S_1, S_2, .., S_n просто образуют семейства

F_i = {S_i}.

Теперь, если ваша задача имела решение за полиномиальное время, то мы получаем набор множеств {S_1, S_2, ..., S_r} такой, что

• S_i и S_j не пересекаются
• Количество S_i является максимальным.

Это простое сокращение дает нам решение проблемы упаковки из 3 наборов, и, таким образом, ваша проблема является NP-сложной.

Чтобы увидеть, что эта проблема находится в NP, мы сводим ее к Set-Packing следующим образом:

Дано F_i = {S_1i, S_2i, ..., S_ni}

мы рассматриваем множества T_ji = S_ji U {i} (т.е.мы добавляем идентификатор семейства в сам набор) и прогоняем их через алгоритм упаковки наборов.Я оставлю это вам, чтобы понять, почему решение Set-Packing дает решение вашей проблемы.

---

Для максимальный решение, все, что вам нужно, - это жадный алгоритм.Просто продолжайте подбирать наборы, пока не сможете выбрать больше.Это было бы полиномиальное время.