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

Question

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

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

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

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

Из этих 4, скажем, 2 из них должны быть медсестрами, а 1 из них - врачами.

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

Answer 9

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

Терпите меня, я ищу лучшие ссылки.

EDIT

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