Разрешимо ли это за полиномиальное (или псевдополиномиальное) время?

Я пытаюсь придумать разумный алгоритм для этой проблемы:

Допустим, у вас есть куча мячей. Каждый шар имеет как минимум один цвет, но может быть и разноцветным. Каждый шар имеет вес и связанную с ним ценность. Есть также куча коробок, каждая из которых только одного цвета. В каждой коробке указано максимальное количество шаров, которое она может вместить. Цель состоит в том, чтобы максимизировать сумму значений в ячейках, не превышая некоторого общего веса, W, и единственное правило:

Чтобы поместить мяч в коробку, на нем должен быть как минимум цвет коробки.

(Например, вы можете положить сине-зеленый шарик в синюю или зеленую коробку, но не в красную коробку.)

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

Мне просто любопытно, есть ли какой-то алгоритм динамического программирования для такого типа задач, чтобы сделать его решаемым за полиномиальное время, или это просто замаскированная проблема коммивояжера. Помогло бы мне, если бы я знал, что существует не более X цветов? Любая помощь приветствуется. Я также мог бы немного формализовать проблему с именами переменных, если это поможет. Спасибо!

Вот простой пример:

Максимальный вес: 5

Мячи:

1 красный шар - (значение = 5, вес = 1)

1 синий шар - (значение = 3, вес = 1)

1 зеленый/красный/синий шар - (значение = 2, вес = 4)

1 зеленый/синий шар - (значение = 4, вес = 1)

1 красный/синий шар - (значение = 1, вес = 1)

Коробки:

1 красный (вмещает 1 мяч)

1 синий (вмещает 2 мяча)

1 зеленый (вмещает 1 мяч)

Оптимальное решение:

красный шар в красной коробке

синий шар и красный/синий шар в синей коробке

зеленый/синий шар в зеленой коробке

Общее значение: 13 (5 + 3 + 1 + 4)

Общий вес: 4 (1 + 1 + 1 + 1)

Примечание: несмотря на то, что зеленый/красный/синий мяч был более ценным, чем красный/синий мяч, его вес привел бы к превышению лимита.

Изменить:

Один уточняющий момент: шары одной цветовой комбинации не обязательно будут иметь одинаковый вес и ценность. Например, у вас может быть красный шар со значением 3 и весом 1, а другой красный шар со значением 2 и весом 5.

Редактировать 2:

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


optimization algorithm mathematical-optimization np traveling-salesman
person Kenny    schedule 12.04.2012    source источник
comment
Числа какого размера являются вашими реальными номерами коробок, шаров, цветов?   -  person AakashM    schedule 12.04.2012
comment
Привет, проблема с рюкзаком? Если шары могут иметь произвольный вес, то мне так кажется. Для этого даже цвета не нужны :)   -  person Voo    schedule 12.04.2012
comment
@AakashM: Относительно маленький: количество ящиков порядка 10. Количество шаров в ящике порядка 10. Общее количество возможных цветов порядка 10. Количество цветов на шарик равно обычно максимум 5 (общий случай - только один или два цвета на шар). Общее количество доступных шаров составляет порядка 1000.   -  person Kenny    schedule 12.04.2012
comment
@Voo: не могли бы вы помочь мне увидеть, как это сводится к рюкзаку? Кажется, что каждая из моих отдельных коробок — это своего рода рюкзак, но у каждой коробки есть ограничение по вместимости, а не по весу, и мне нужно оставаться ниже веса суммы всех коробок, максимизируя ценность.   -  person Kenny    schedule 12.04.2012
comment
@Kenny Это только при условии, что мячи могут иметь произвольный вес, если это правда - объяснение людей, которые уже ответили, такое же, как и я.   -  person Voo    schedule 12.04.2012
comment
Чтобы решить проблему за полиномиальное время, вы должны иметь возможность обрабатывать все экземпляры проблемы. Добавление предела вместимости не имеет значения, потому что вы можете настроить задачу с настолько высоким пределом вместимости, что он не имеет значения (например, установить его на общее количество мячей).   -  person comingstorm    schedule 12.04.2012
comment
Другими словами: добавление предела вместимости может усложнить проблему рюкзака, но не может облегчить ее.   -  person comingstorm    schedule 12.04.2012
comment
Наверное, я надеялся на решение с псевдополиномиальным временем. Я должен был уточнить. Очевидно, что эта задача не менее сложна, чем рюкзак.   -  person Kenny    schedule 12.04.2012

Ответы (5)


arrow_upward
5
arrow_downward

Это не менее сложно, чем задача о рюкзаке — рассмотрим случай, когда все шары красные и есть только одна красная коробка.

В случае, когда шары, имеющие одинаковую комбинацию цветов, должны иметь одинаковый вес и стоимость, рассмотрим случай, когда у вас есть красный/синий, красный/зеленый и т. д. шары и только одна красная коробка.

person Paweł Obrok    schedule 12.04.2012
comment
Ага +1. Однако многоцветный аспект шаров может немного усложнить обычное решение динамического программирования. - person Voo; 12.04.2012
comment
Для уточнения: шары с одинаковой цветовой комбинацией не обязательно будут иметь одинаковый вес и ценность. Например, у вас может быть красный шар со значением 3 и весом 1, а другой красный шар со значением 2 и весом 5. - person Kenny; 12.04.2012
comment
В любом случае, вы можете представить любой экземпляр рюкзака с этой задачей, так что это NP-сложно. - person Paweł Obrok; 12.04.2012
comment
@obrok: понятно. Думаю, я надеялся, что, поскольку вы можете использовать динамическое программирование для решения задачи о рюкзаке за полиномиальное время (предполагая, что веса и значения являются целыми числами), вы могли бы использовать аналогичную технику здесь. - person Kenny; 12.04.2012
comment
На самом деле он псевдополиномиальный - в данном случае это означает полиномиальный по сумме весов - который может быть очень большим даже для небольших задач! Для этой задачи вряд ли существует эффективный динамический алгоритм — состояние очень сложное — каждый вид мяча и ящика нужно рассматривать отдельно, поэтому маловероятно, что узлы в дереве поиска будут повторяться. - person Paweł Obrok; 12.04.2012
comment
Ах, спасибо за разъяснение. Вот чего я боялся. - person Kenny; 12.04.2012
comment
@Kenny Это доказательство не исключает возможности решения динамического программирования (псевдополиномиального). Knapsack слабо NP-полный. Чтобы полностью установить такое несуществование, мы должны свести к нему сильно NP-полную задачу (с некоторыми дополнительными требованиями к самой редукции). - person aelguindy; 13.04.2012

arrow_upward
5
arrow_downward

Если количество ящиков не ограничено, то эта задача является строго NP-трудной за счет сокращения от 3 -partition (установите n/3 ящика и сделайте все вещи радужными со значением = весом).

Если количество ящиков постоянно, то существует алгоритм псевдополиномиального времени с помощью динамического программирования, где каждое состояние DP состоит из того, насколько заполнен каждый ящик.

person junction    schedule 12.04.2012
comment
Не могли бы вы немного рассказать о том, как этот алгоритм DP будет работать при постоянном количестве ящиков? Спасибо! - person Kenny; 13.04.2012
comment
Рассмотрим предметы один за другим. На каждом этапе индексируйте таблицу кортежами, описывающими, насколько заполнен каждый ящик. Например, индекс (2, 2, 3) будет означать, что в первом ящике 2 единицы предметов, во втором тоже 2, а в третьем 3. Каждая запись в таблице — это максимальное значение, которое можно получить по рассматриваемым предметам. до сих пор так, чтобы каждое поле было заполнено до уровня, указанного индексом этой записи. - person junction; 16.04.2012

arrow_upward
3
arrow_downward

Сокращение из ранца происходит следующим образом. Имея экземпляр вашего рюкзака, вы создаете экземпляр задачи о мячах и корзинах: для каждого предмета экземпляра рюкзака у вас есть мяч того же веса и стоимости, что и предмет. Тогда у вас есть коробка, представляющая рюкзак. Шары и коробка все синие. Вместимость ящика — это предел, указанный в задаче о рюкзаке. Учитывая решение вашей задачи, у нас есть набор шаров в коробке, общий вес которых не превышает предела рюкзака, а общая стоимость максимальна.

person Irit Katriel    schedule 12.04.2012

arrow_upward
3
arrow_downward

Эта задача является NP-полной, поскольку включает в себя задачу о рюкзаке.

То есть это не просто похоже на задачу о рюкзаке: если есть одна миска, все шары имеют цвет этой миски, а максимальное количество шаров в миске равно общему количеству шаров, то задача и есть задача о рюкзаке. .

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

person comingstorm    schedule 12.04.2012
comment
Я согласен с тем, что с одной коробкой это сводится к рюкзаку, но я не понимаю, как я мог бы использовать те же методы для решения этой проблемы, когда есть несколько коробок разных цветов. Поскольку мячи могут иметь более одного цвета, потенциально они могут поместиться в разные коробки, поэтому отдельные рюкзаки не являются независимыми. - person Kenny; 12.04.2012
comment
Ваш вопрос заключался в том, что проблема разрешима за полиномиальное время. Это наихудший случай: если вы можете составить любую возможную задачу, которую она не может решить за полиномиальное время, то ответ будет отрицательным. Другими словами: если вы найдете алгоритм, способный решить эту задачу за полиномиальное время, вы докажете, что P=NP. И хотя мы не знаем наверняка наверняка, что это невозможно, это кажется маловероятным... - person comingstorm; 12.04.2012
comment
Спасибо, я должен был уточнить раньше: я надеялся, что псевдополиномиальное решение также может быть возможным/практичным. - person Kenny; 12.04.2012

arrow_upward
0
arrow_downward

Лучшее, что вы можете сделать в этой ситуации, — это получить аппроксимацию оптимального решения — задача о рюкзаке сама по себе не разрешима за полиномиальное время. Вы все равно сможете получить хорошие (хотя и не гарантированно оптимальные) результаты за полиномиальное время, если сможете сгенерировать для этого хороший алгоритм.

person Mikey    schedule 12.04.2012