Я дал множество , целое число , и неотрицательные целые числа . Моя проблема состоит в нахождении непересекающиеся подмножества из такие , что:
- ; и
- для всех и .
Как решить эту проблему? Сложно ли найти реальное решение?
Я думаю , что это не так легко решить эту проблему , потому что я попробовал некоторую процедуру , которая начинается с некоторого и правопреемников до числа от назначен больше , чем для некоторого присвоенного. Но это не правильно , потому что я мог оставить некоторые , которые не могут быть отнесены к какому - либо (из - за их , которые могут быть не удовлетворены).
Метод грубой силы, когда я должен генерировать все подмножества и протестировать каждый из них, работает для меня ( ) , но очень неэффективно.
Ответы:
Эта проблема является NP-трудной сокращением от Vertex крышки.
В задаче покрытия вершин нам дан граф и число , и наша задача состоит в том, чтобы определить, существует ли какое-то подмножество из не более вершин из такое, что каждое ребро в инцидентно по крайней мере с одной вершиной из . (Эквивалентно: возможно ли убить каждое ребро в , удалив не более вершин?)G=(V,E) r U r V E U G r
Во- первых, разбиение во подмножеств непересекающихся эквивалентно присвоения каждому элементу в именно один из возможных меток. Основная идея редукции создать ярлык для каждой вершины в , и «разрешить» каждому ребру быть назначен только один из двух меток , соответствующих его концов, в следующем смысле: назначая ребро в парное не этикетка вводит нет (подлинный) ограничение на то , что другие ребра могут быть назначены и ту же метку, при назначении ребра к не соответствующим предотвращает этикетки любой другой край присваивается один и тот же ярлык - что, конечно , имеет эффект выталкивания вверх число отдельных ярлыков требуется.A s A s Sj vj V
Чтобы построить экземпляр вашей проблемы из экземпляра Vertex Cover:(A,a,s) (G,r)
Если является YES-экземпляром Vertex Cover, то легко увидеть, что только что экземпляр вашей проблемы также является YES-экземпляром: просто выберите метки соответствующие вершинам в любом решении и для каждого ребро Назначают соответствующий элемент какой бы ни один из знаков или был выбран (произвольно выбирать , если были выбраны оба метки). Это решение использует подмножества и является действительным, потому что единственными действующими являются те для соответствующего(G,r) Sj vj U vbvc∈E (b,c)∈A Sb Sc s aij метки, которые имеют (не) эффект предотвращения более чемребрам присваивается один и тот же ярлык.|E|
Осталось показать, что YES-экземпляр вашей проблемы подразумевает, что оригинал является YES-экземпляром Vertex Cover. Это немного более сложным, так как действительное решение к в общем случае может назначить ребро не -corresponding метка , т.е. , что означает , что мы не можем обязательно «считывать» действительную вершину крышку от действительного решения .X=(A,a,s) (G,r) Y X (i,j) Sm m∉{i,j} U Y
Однако назначение несоответствующей метки имеет высокую стоимость, что серьезно ограничивает структуру решения: всякий раз, когда ребру назначается такая метка , с , факт что гарантирует, что это должен быть единственный край, которому назначена эта метка. Таким образом, в любом решении содержащем такое не соответствующим образом помеченное ребро , мы можем построить альтернативное решение следующим образом:(i,j) Sm m∉{i,j} a(i,j),m=1 Y (i,j)↦Sm Y′
Вышеприведенный алгоритм должен завершаться одним из двух способов: либо найдена новая метка которая не вводит противоречий, либо найден полный цикл вершин. В первом случае найдено действительное новое решение с множествами , а во втором случае найдено действительное новое решение с множествами ; В любом случае, мы построили правильное новое решение с по крайней мере еще одним ребром, назначенным соответствующей метке. После повторения всего этого процесса самое большеераз мы дадим правильное решение из которого можно будет прочитать решение исходной проблемы Vertex Cover .Sz s−1 s |E| Y′′
Эта конструкция явно полиномиального времени, поэтому из вашей задачи вытекает NP-сложность.
источник