Трудно ли NP заполнять мусорные ведра с минимальными ходами?

33

Есть бункеров и типов шаров. У го бина есть метки для , это ожидаемое количество шаров типа .nmiai,j1jmj

Вы начинаете с шариков типа . Каждый шар типа имеет вес и хочет поместить шары в контейнеры так, чтобы имела вес . Распределение шаров, удовлетворяющее предыдущему условию, называется выполнимым решением.bjjjwjici

Рассмотрим выполнимое решение с шарами типа в bin i , тогда стоимость равна \ sum_ {i = 1} ^ n \ sum_ {j = 1} ^ m | a_ {i, j} -x_ {I, J} | , Мы хотим найти минимально возможное решение.xi,jjiΣязнак равно1NΣJзнак равно1м|aя,J-Икся,J|

Эта проблема явно NP-сложна, если нет ограничений на {весJ} . Проблема суммы подмножеств сводится к существованию допустимого решения.

Однако, если мы добавим условие, что весJ делит весJ+1 для каждого J , то уменьшение суммы подмножеств больше не работает, поэтому не ясно, остается ли возникающая проблема NP-трудной. Проверка существования выполнимого решения занимает всего О(Nм) времени (в конце в конце вопроса), но это не дает нам возможного решения с минимальными затратами.

Задача имеет эквивалентную целочисленную формулировку программы. Дано aя,J,ся,бJ,весJ для 1яN,1Jм :

Минимизировать:Σязнак равно1NΣJзнак равно1м|aя,J-Икся,J|при условии:ΣJзнак равно1мИкся,JвесJзнак равнося для всех 1яNΣязнак равно1NИкся,JбJ для всех 1JмИкся,J0 для всех 1яN,1Jм

Мой вопрос

Является ли вышеуказанная целочисленная программа NP-трудной, когда весJ делит весJ+1 для всех J ?

Алгоритм для определения, существует ли возможное решение за O(Nм) времени :

Определите весм+1знак равновесм(МаксимумJсJ+1) и dJзнак равновесJ+1/весJ . Пусть a%б будет остаток, когда a делится на б .

  1. Если существует ся который не делится на вес1 , верните «не выполнимое решение». (инвариант ся делит весJ всегда будет поддерживаться в следующем цикле)
  2. для J от 1 до м :

    1. КΣязнак равно1N(ся/весJ)%dJ . (необходим минимум шариков весомвесJ )
    2. Если бJ<К , вернуть «не выполнимое решение».
    3. сяся-((ся/весJ)%dJ) для всех . (убрать минимальное количество необходимых шариков весом )явесJ
    4. бJ+1(бJ-К)/dJ . (сгруппируйте меньшие шары в большой шар)
  3. вернуть "есть выполнимое решение".

Полиномиальное решение для частного случая, когда , а - степень с.Nзнак равно1весJ2

Известно, что если и все являются степенями , то этот частный случай может быть решен за полиномиальное время. Nзнак равно1весJ2

Минимизировать:ΣJзнак равно1м|aJ-ИксJ|при условии:ΣJзнак равно1мвесJИксJзнак равнос0ИксJбJ для всех 1Jм

Yuzhou Gu намекнул на это решение , и здесь можно найти описание .

Чао Сюй
источник

Ответы:

0

Некоторый фон. Вышеупомянутая проблема - проблема ранца с ограничениями. Наиболее эффективное решение проблемы ранца с или без ограничений может быть решено за псевдополиномиальное время, все еще NP-Hard. Для некоторых вариантов см. Https://en.wikipedia.org/wiki/Knapsack_problem#Definition . Первое ограничение в этом варианте заключается в том, что стоимость предметов (шариков), помещаемых в рюкзак (мусорные ведра), не имеет значения. Проблема тогда ограничена количеством времени, которое требуется, чтобы поместить предметы в рюкзак. Первоначальная задача требует, чтобы самые ценные предметы были размещены в кратчайшие сроки. Другое ограничение этой версии - весовые коэффициенты и все остальные аргументы являются целыми числами. И ограничение интереса в том, что весыw j + 1 jвесJразделить для всех . Примечание: проблема дробного ранца может быть решена за полиномиальное время, но не дает наиболее практичных решений исходной задачи. В этой задаче используются целые числа, которые делятся равномерно (без рациональных решений). Может быть, посмотрите, в чем же проблема с рюкзаком? ,весJ+1J

Главный вопрос, возможно, должен заключаться в том, является ли эта проблема все еще NP- когда не ограничен полиномом, соответствующим , поскольку задача менее сложна (в P), когда она ограничена? Причина, по которой я говорю, заключается в том, что проблема может показано, что он находится в P, когда ограничен, и NP-Hard, когда не обязательно делит i w j w j w j + 1весJявесJвесJвесJ+1равномерно (веса просто случайные), все ограничения ограничивают сложность этой задачи этими двумя условиями. Эти условия (1. случайная задача о ранце с весом без ограничения по стоимости предмета и 2. задача о ранце с делимым весом без ограничения по стоимости предмета) сводят на нет друг друга с точки зрения уменьшения сложности, так как коэффициенты весов сами могут быть случайными ( особенно когда он неограничен), что накладывает экспоненциальные временные вычисления (это будет показано в примере ниже). Кроме того, поскольку делит , экспоненциально увеличивается для каждогоw j + 1 w j j w jвесJвесJ+1весJJ, Это связано с тем, что вместо использования случайных взвешенных предметов (шаров, удельный вес которых может быть ограничен единичным весом менее 100, или 50, или даже 10), вместо этого ограничение приводит к тому, что сложность времени зависит от количества цифр , так же, как пробное деление, которое является экспоненциальным.весJ

Так что да, вышеуказанная целочисленная программа остается NP-сложной, даже когда делит на все . w j + 1 jвесJвесJ+1J И это легко заметить.

Пример 1: пустьи- степени двойки. Из-за константы два вся проблема решается за квадратичное время, как показывает ваш пример. Веса не случайны, и поэтому расчет решается эффективно.w pNзнак равно1весп

Пример 2: пустьопределяется как, где- простое число, соответствующее, такое, что. Это применимо, так какделитдля всех w jp p j p = 2 , j = 1 : p = 3 , j = 2 , p = 5 , j = 3весJ+1весJ*ппJw j w j + 1 j w j j 1 ,p=2,j=1:p=3,j=2,p=5,j=3,p=7,j=4,...,P,Jwjwj+1j . Мы получаем, что каждый является произведением всех простых чисел до . Значения удельных весов увеличивают как таковые: . Так как есть граница ( ~wjjp j j l o g ( j )1,2,6,30,210,2310,30030,...pjjlog(j)через теорему о простых числах), поскольку все факторы являются простыми числами, мы получаем сложность NP-Intermediate.

Пример 3: пустьопределяется как, где- произвольно выбранное простое число от двух до бесконечности, соответствующее. Это применимо к этой проблеме, так какделитдля всех. Мы получаем первые 5 факторов (случайным образом падая с двух до бесконечности), как. Мы видим, что даже на 5-м шаре вес имеет одиннадцать цифр. К счастью, пятым частным было два, а не простое число порядкаили больше. w jR pwj+1wjRp j w j w j + 1 j 101 , 2657 , 7 , 3169 , 2 10 100Rpjwjwj+1j101,2657,7,3169,210100

выше третий пример - это то, что происходит, когда не ограничен (случайные веса) полиномом, соответствующим . Сложность времени экспоненциальная, NP-Hard. Для некоторой перспективы просто сложите все веса, посмотрите, подходят ли они. Но не существует решения, позволяющего решить его значительно быстрее, сделав весовые коэффициенты делимыми, чем попытка каждого подмножества проверить, работает ли он. После нескольких дюжин шаров, вы все еще входите в царство даже триллионов подмножеств или триллионов цифр. яwji

Джефф
источник
1
Но первичная факторизация считается не NP-сложной. Он считается NP-промежуточным звеном.
rus9384
2
Я не вижу здесь сокращения. Что такое фактическое сокращение? Взяв ввод простой факторизации, и каким-то образом вывести факторизацию, используя решение целочисленной программы.
Чао Сюй
2
Вы подразумевали бы под "вышеупомянутой целочисленной программой NP-hard"? Индивидуальная программа не может быть NP-сложной.
Юваль
1
На самом деле факторизация находится в . Таким образом, это -hard if . NPcoNPNPNP=coNп
rus9384
2
К сожалению, дополнительные изменения не прояснили это. Фактическое сокращение было бы полезно.
Чао Сюй