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