algorithm - example - ¿Es este problema NP, y tiene un nombre?
np problems (2)
El problema de la cubierta del conjunto, como se describe en el artículo de Wikipedia al que Antti Huima lo vinculó, carece de la característica de que a cada invitado le guste su propio plato. De antemano, no sé si esto hace alguna diferencia.
Este problema surgió en el mundo real, pero lo he traducido en una formulación más genérica de "tipo libro de texto". Sospecho que es NP, pero estoy particularmente interesado en saber si tiene un nombre o si es bien conocido, ya que creo que no puedo ser el primero en encontrarlo. ;-)
Imagina que hay una fiesta con N invitados. Cada invitado puede traer su "plato especial" a la fiesta o no traer nada. A cada invitado le gusta u odia cada uno de los platos que pueden traer los otros invitados (¡y esto se sabe de antemano porque todos son viejos amigos!), Pero a todos les gusta sus propios platos.
¿Existe un algoritmo determinista que no tome tiempo exponencial para encontrar el conjunto más pequeño de platos que satisfaga la restricción de que todos los invitados encontrarán al menos un plato a su gusto? Digo "el" más pequeño, pero en realidad puede haber múltiples soluciones, y me gustaría conocerlas todas si es posible.
O, de una manera más abstracta, imagine una matriz cuadrada donde todos los elementos son 0 o 1, y todos los elementos diagonales son 1. ¿Cuáles son los conjuntos más pequeños de filas de tal manera que la suma (o el OR binario) de las filas en cada ¿El conjunto no tiene ceros? (Las filas serían los platos, las columnas serían los invitados, 1 significaría que a un invitado le gusta un plato y los elementos diagonales son 1 ya que a todos les gusta su propio plato).
Esto podría generalizarse a matrices no cuadradas, o eliminando la regla diagonal = 1 (aunque esta última garantiza que siempre habrá al menos una solución). Pero no me importan esos casos por ahora ...
Ya tengo un programa que lo resuelve a través de una búsqueda exhaustiva y es lo suficientemente rápido para N alrededor de 20, pero toma un tiempo exponencial. Estoy pensando que podría necesitar recurrir a algoritmos estocásticos para encontrar soluciones suficientemente buenas para valores más grandes de N.
Adicional
Wow, gracias por la rápida respuesta! "Establecer portada", ese es el nombre que estaba buscando. :)
Esto se llama el problema SET COVER y es NP-completo.