Псевдополиномиальное или быстрое решение многокритериальной суммы подмножества

Я ищу быстрое решение для множественной / многоцелевой проблемы суммы подмножества.

В качестве дополнительных ограничений (которые немного упрощают расчет IMO) мы можем предположить, что все значения, включенные в сумму, являются положительными и все связаны с известным предельным значением.

Я знаю, что существует псевдополиномиальное решение O (NK) для задачи суммы подмножества с одной целью, я реализовал решение на основе википедии и этот ответ обмена стеками.

Объясняя эту проблему по-другому, у меня есть два набора положительных чисел, предел которых известен. Для каждого значения A в первом наборе существует комбинация значений во втором наборе, которая суммируется до A. Известно априори, что все значения в первом наборе имеют соответствующую и неконфликтную комбинацию значений, связанных во втором наборе, является есть ли известный быстрый способ вычислить, какие элементы во втором наборе связаны с каждым из значений первого набора?


algorithm knapsack-problem dynamic-programming subset-sum
person viniciuscb    schedule 13.07.2012    source источник
comment
Что именно вы имеете в виду, говоря «не противоречить»? Вы имеете в виду, что каждое значение во втором наборе используется для создания только одного из значений в A? Или вы, возможно, имеете в виду, что каждое решение для значения в A уникально (то есть только одно подмножество второго набора даст это значение) или, возможно, что-то еще?   -  person Jerry Coffin    schedule 14.07.2012
comment
@JerryCoffin, каждое значение во втором наборе используется для создания только одного из значений в A.   -  person viniciuscb    schedule 14.07.2012
comment
В подобной задаче во втором наборе может быть несколько комбинаций, которые в сумме могут давать значение в первом наборе. Проблема в том, что мы должны найти одну комбинацию для каждого значения в первом наборе, и все найденные комбинации используют исключительные значения во втором наборе - это то, что я имею в виду, когда говорю, что они не конфликтуют.   -  person viniciuscb    schedule 14.07.2012

Ответы (1)


arrow_upward
1
arrow_downward

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

В этом проекте я разработал алгоритм, который ищет решение в таблице DP. Это не псевдополином, но я думаю, что в общих случаях он достаточно быстрый.

Я также реализую инструмент Python для решения этих проблем. Может быть, вы захотите попробовать!

Этот инструмент называется msat и поддерживается на github.

Вы можете сослаться на msat.

Или просто используйте pip для его установки (это инструмент Python3):

$ pip install msat

Есть также вводные слайды: слайды.

Если вы хотите узнать подробности, обратитесь к тезису.

person dokelung    schedule 21.04.2016