Эта проблема возникла в реальном мире, но я перевел ее в более общую «учебную» формулировку. Я подозреваю, что это NP, но мне особенно интересно узнать, есть ли у него имя или оно хорошо известно, так как я думаю, что не смогу встретить его первым. ; -)
Представьте себе, что там пьяная вечеринка с N гостями. Каждый гость может принести свое «фирменное блюдо» на вечеринку или ничего не принести. Каждый гость любит или ненавидит каждое из блюд, которое могут принести другие гости (и это известно заранее, так как они все старые друзья!), Но все они любят свои собственные блюда.
Существует ли детерминированный алгоритм, который не требует экспоненциального времени для поиска наименьшего набора блюд, который удовлетворяет условию, что все гости найдут хотя бы одно блюдо по своему вкусу? Я говорю «самое маленькое», но на самом деле может быть несколько решений, и я хотел бы знать их все, если это возможно.
Или, более абстрактным образом, представьте квадратную матрицу, в которой все элементы равны 0 или 1, а все диагональные элементы равны 1. Какие наименьшие наборы строк такие, что сумма (или двоичное ИЛИ) для строки в каждом наборе не имеют нулей? (Строки - это блюда, столбцы - гости, 1 означает, что гость любит блюдо, а диагональные элементы равны 1, так как каждый любит свое блюдо.)
Это можно обобщить на неквадратные матрицы или удалить правило diagonal = 1 (хотя последнее гарантирует, что всегда будет хотя бы одно решение). Но сейчас мне плевать на эти дела ...
У меня уже есть программа, которая решает ее путем исчерпывающего поиска и достаточно быстра для N около 20, но это требует экспоненциального времени. Я думаю, что мне, возможно, придется вернуться к стохастическим алгоритмам, чтобы найти достаточно хорошие решения для больших значений N.
Добавлена
Ух ты, спасибо за быстрый ответ! «Установите крышку», это имя, которое я искал. :)