Как разбить множество на заданное количество непересекающихся подмножеств при соблюдении некоторых условий?

11

Я дал множество , целое число , и неотрицательные целые числа . Моя проблема состоит в нахождении непересекающиеся подмножества из такие , что:A{1,,k}skaijsSj{1,,k}

  1. j=1sSj=A ; и
  2. |Sj|aij для всех и .iSjj=1,,s

Как решить эту проблему? Сложно ли найти реальное решение?

Я думаю , что это не так легко решить эту проблему , потому что я попробовал некоторую процедуру , которая начинается с некоторого и правопреемников до числа от назначен больше , чем для некоторого присвоенного. Но это не правильно , потому что я мог оставить некоторые , которые не могут быть отнесены к какому - либо (из - за их , которые могут быть не удовлетворены).j{1,,n}i{1,,k}ijaijiijaij

Метод грубой силы, когда я должен генерировать все подмножества и протестировать каждый из них, работает для меня ( ) , но очень неэффективно.Ak=8,n=3

drzbir
источник
Проверьте, соответствует ли редактирование вопросу, который вы хотите задать. Кроме того , откуда взялось? Является ли это фиксированной константой (не входной частью, но фиксированной на все время) или частью входной информации? Наконец, вы ищете практическое решение? или вы ищете теоретическую сложность этой проблемы? Если первое, то вы пытались с помощью целочисленного линейного программирования? amax
DW

Ответы:

10

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

В задаче покрытия вершин нам дан граф и число , и наша задача состоит в том, чтобы определить, существует ли какое-то подмножество из не более вершин из такое, что каждое ребро в инцидентно по крайней мере с одной вершиной из . (Эквивалентно: возможно ли убить каждое ребро в , удалив не более вершин?)G=(V,E)rUrVEUGr

Во- первых, разбиение во подмножеств непересекающихся эквивалентно присвоения каждому элементу в именно один из возможных меток. Основная идея редукции создать ярлык для каждой вершины в , и «разрешить» каждому ребру быть назначен только один из двух меток , соответствующих его концов, в следующем смысле: назначая ребро в парное не этикетка вводит нет (подлинный) ограничение на то , что другие ребра могут быть назначены и ту же метку, при назначении ребра к не соответствующим предотвращает этикетки любой другой край присваивается один и тот же ярлык - что, конечно , имеет эффект выталкивания вверх число отдельных ярлыков требуется.AsAsSjvjV

Чтобы построить экземпляр вашей проблемы из экземпляра Vertex Cover:(A,a,s)(G,r)

  1. Установите вИ создать элемент в для каждого ребра в . (Эти пары можно рассматривать как целые числа ; любая биекция между ними подойдет.)k|E|(i,j)AvivjE1,,k
  2. Установите значениеесли или ; в противном случае установите на 1.a(b,c),d|E|d=bd=ca(b,c),d
  3. Установите .s=r

Если является YES-экземпляром Vertex Cover, то легко увидеть, что только что экземпляр вашей проблемы также является YES-экземпляром: просто выберите метки соответствующие вершинам в любом решении и для каждого ребро Назначают соответствующий элемент какой бы ни один из знаков или был выбран (произвольно выбирать , если были выбраны оба метки). Это решение использует подмножества и является действительным, потому что единственными действующими являются те для соответствующего(G,r)SjvjUvbvcE(b,c)ASbScsaijметки, которые имеют (не) эффект предотвращения более чемребрам присваивается один и тот же ярлык.|E|

Осталось показать, что YES-экземпляр вашей проблемы подразумевает, что оригинал является YES-экземпляром Vertex Cover. Это немного более сложным, так как действительное решение к в общем случае может назначить ребро не -corresponding метка , т.е. , что означает , что мы не можем обязательно «считывать» действительную вершину крышку от действительного решения .X=(A,a,s)(G,r)YX(i,j)Smm{i,j}UY

Однако назначение несоответствующей метки имеет высокую стоимость, что серьезно ограничивает структуру решения: всякий раз, когда ребру назначается такая метка , с , факт что гарантирует, что это должен быть единственный край, которому назначена эта метка. Таким образом, в любом решении содержащем такое не соответствующим образом помеченное ребро , мы можем построить альтернативное решение следующим образом:(i,j)Smm{i,j}a(i,j),m=1Y(i,j)SmY

  1. Произвольно выберите новую метку для как или .Sz(i,j)SiSj
  2. Назначьте этот новый ярлык. Если это приводит к неверному решению, это должно быть потому, что ровно одному другому ребру , уже был присвоен ярлык . В этом случае установите и перейдите к шагу 1.(i,j)(i,j)z{i,j}Sz(i,j)=(i,j)

Вышеприведенный алгоритм должен завершаться одним из двух способов: либо найдена новая метка которая не вводит противоречий, либо найден полный цикл вершин. В первом случае найдено действительное новое решение с множествами , а во втором случае найдено действительное новое решение с множествами ; В любом случае, мы построили правильное новое решение с по крайней мере еще одним ребром, назначенным соответствующей метке. После повторения всего этого процесса самое большеераз мы дадим правильное решение из которого можно будет прочитать решение исходной проблемы Vertex Cover .Szs1s|E|Y

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

j_random_hacker
источник
Спасибо за помощь. Есть ли у вас идеи, как можно (приблизительно) решить эту проблему? (Как, например, я могу использовать методы для решения проблемы покрытия вершин?) Я попробовал какой-то жадный подход, но иногда он не может привести к выполнимому решению. (То, как я выбираю делает жадный подход когда может существовать решение.)Sj
drzbir
Что ж, ожидается, что из-за жадного подхода иногда не удастся вывести выполнимое решение, поскольку, если бы оно всегда было так, вы бы решали NP-сложную задачу в поли-времени ;-) Помните, что это не обязательно неправильно, если не может найти решение: вполне может быть, что никакого приемлемого решения не существует.
j_random_hacker
Что касается методов решения, один из них, который мне нравится, называется поиском луча. Это в основном разновидность ветвления и ограничения, которая «забывает» достаточно плохие частичные решения, чтобы ограничить использование памяти. (B & B сам по себе является очень хорошим подходом и иногда быстро решает проблемы, и он немного проще, чем поиск луча, поэтому его стоит попробовать - но, поскольку это точный метод, в некоторых случаях он, конечно, может занять тысячелетия.)
j_random_hacker
(Все нижеприведенное относится и к поиску луча, и к B & B.) B & B - очень общий метод. Главное в этом - использовать специфику проблемы, чтобы организовать принимаемые вами решения таким образом, чтобы как можно больше плохих решений (то есть решений, которые не приводят к возможным решениям) принимаются на ранних этапах дерева поиска. (Эти решения будут приниматься где-то , и каждый уровень, который они получают на более глубоком уровне, удваивает количество раз, которое они получают.) Для вашей проблемы я бы предложил сначала расположить элементы в порядке в порядке убывания «плохости», где. ..A
j_random_hacker
... плохость элемента может быть, например, минимумом по всем , разрывая связи по второму минимуму, затем третьему минимуму и т. д. Грубо говоря, «худшим» элементом будет элемент это наиболее сильно ограничивает любой набор, к которому он добавлен. В каждом узле на глубине в дереве поиска у вас будет частичное решение, в котором первые (и, следовательно, «худшие») элементы уже были назначены наборам; вам нужно будет выбрать, какой из наборов назначить -ому элементу: то есть вам потребуется до рекурсивных вызовов. ("До", потому что мы надеемся, что ...iaijjddn(d+1)n
j_random_hacker