Возможная NP-полная проблема?

Question

Мне просто хотелось бы, чтобы кто-нибудь проверил, является ли следующая проблема NP-полной или на самом деле существует лучшее/более простое решение, чем простая проверка комбинации перебором.

В нашем программном обеспечении есть своего рода проблема с распределением ресурсов, и я объясню ее на примере.

Допустим, нам нужно, чтобы в дневную смену на работе работали 4 человека.Это число, а также тот факт, что это «дневная смена», зафиксированы в нашей базе данных.

Однако мы не требуем, чтобы кто-то заполнил эти места, есть некоторые требования, которые необходимо выполнить, чтобы соответствовать всем требованиям.

Допустим, из этих четырех двое должны быть медсестрами, а один - врачами.

Один из врачей также должен работать в составе определенной бригады.

Итак, у нас есть такой набор информации:

Дневная смена:4
1 врач
1 врач, необходимо работать в бригаде А
1 медсестра

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

Например, предположим, что мы выбираем для работы Джеймса, Джона, Урсулу и Мэри, где Джеймс и Урсула — врачи, а Джон и Мэри — медсестры.

Урсула также работает в команде А.

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

Например, если пройтись по списку и сначала выбрать Урсулу, мы сможем сопоставить ее с критерием «1 врач».Затем мы добираемся до Джеймса и замечаем, что, поскольку он не работает в команде А, другие критерии «1 врач должен работать в команде А» не могут быть заполнены им.Поскольку двое других — медсестры, они тоже не соответствуют этим критериям.

Итак, мы отступаем и сначала проверяем Джеймса, и он тоже может соответствовать первым критериям, а затем Урсула может соответствовать критериям, которые нужны этой команде.

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

Это единственное решение, может ли кто-нибудь придумать лучшее?

---

Редактировать:Некоторые разъяснения.

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

Проблема, однако, в том, что это часть системы планирования реестра, в которой может быть задействовано довольно много людей, как «Нам нужны X человек в дневную смену», так и «У нас есть этот пул из Y людей». который будет это делать», а также потенциал для большого «У нас есть список критериев Z для тех людей X, которым придется каким-то образом совпадать с этими людьми Y», а затем вы добавляете к тому факту, что у нас будет несколько дней, чтобы сделать тот же расчет в режиме реального времени, пока лидер корректирует список, а затем возникла необходимость в быстром решении.

По сути, руководитель будет видеть на экране общую информацию о том, сколько людей все еще не хватает, как в дневную смену в целом, так и сколько людей соответствует различным критериям, и сколько людей мы на самом деле пропустили. ned в дополнение к тем, которые у нас есть.Этот дисплей должен будет обновляться в полуживом режиме, пока лидер корректирует список с помощью «Что, если Джеймс возьмет на себя дневную смену вместо Урсулы, а Урсула возьмет ночную смену».

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

Вот почему я люблю StackOverflow :)

Answer 1

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

Как отметил ebo в комментариях, ваша ситуация выглядит так, как будто ее можно сформулировать как точная проблема с обложкой, который вы можете применить Алгоритм Кнута X к.Если вы выберете этот путь, пожалуйста, дайте нам знать, как это сработает для вас.

Answer 2

Похоже, у тебя есть проблема удовлетворения ограничений.

В вашем случае я бы сначала рассмотрел методы распространения ограничений - таким образом вы сможете уменьшить проблему до управляемого размера.

Что произойдет, если никто не соответствует критериям?

Answer 3

То, что вы описываете, - это «Проблема соседа по комнате», она кратко описана в этот тезис.

Потерпите, я ищу ссылки получше.

РЕДАКТИРОВАТЬ

Вот еще один довольно плотный Тезис.

Answer 4

Что касается меня, то я, скорее всего, попытался бы найти сокращение до сопоставление двудольного графа проблема.Кроме того, доказать, что проблема является NP, обычно гораздо сложнее, чем не найти полиномиального решения.

Answer 5

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

Answer 6

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

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

Если я правильно помню, NSolver также включает в пример кода упрощение реальной задачи по составлению списка медсестер, которую предложил доктор.Чун работал в Гонконге.И есть документ о проделанной им работе.

Answer 7

Мне кажется, что у вас есть пара отдельных проблем, которые было бы намного проще решить:

- Выберите одного доктора из команды A- выберите другого доктора из любой команды- выберите две медсестры

Итак, у вас есть три независимые проблемы.

Уточнение: обязательно ли иметь двух врачей (одного из указанной бригады) и двух медсестер или одного врача из указанной бригады, двух медсестер и еще одного, который может быть как врачом, так и медсестрой?

Answer 8

Некоторые вопросы:

1. Является ли цель удовлетворить ограничения точно, или только примерно (но как можно больше)?
2. Может ли человек быть членом нескольких команд?
3. Каковы все возможные ограничения?(Например, может ли нам понадобиться врач, входящий в несколько команд?)

Если вы хотите удовлетворить ограничения точно, то я бы упорядочил ограничения по убыванию строгости, то есть те, которых труднее всего достичь (например,врач И команда А в приведенном выше примере) должны быть проверены первый!

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

Answer 9

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

Грубая сила, ветвь и граница и подобные методы занимают слишком много времени.Детерминированные алгоритмы, такие как сначала заполняйте самые большие смены очень неоптимальны.Метаэвристика — очень хороший способ справиться с этой проблемой.

Взгляните конкретно на реальный пример списка медсестер в Drools Planner.Легко добавить множество ограничений, например «молодые медсестры не хотят работать в субботу вечером» или «некоторые медсестры не хотят работать много дней подряд».