Ce problème est apparu dans le monde réel, mais je l'ai traduit dans une formulation plus "générique". Je soupçonne que c'est NP, mais je suis particulièrement intéressé de savoir s'il a un nom ou est bien connu car je pense que je ne peux pas être le premier à le rencontrer. ;-)Est-ce que ce problème est NP, et a-t-il un nom?
Imaginez qu'il y ait une fête-partage avec N invités. Chaque invité peut apporter son "plat de signature" à la partie, ou n'apporter rien. Chaque invité aime ou déteste chacun des plats que les autres invités peuvent apporter (et c'est connu à l'avance car ils sont tous de vieux amis!), Mais ils aiment tous leurs propres plats. Y at-il un algorithme déterministe qui ne prenne pas de temps exponentiel pour trouver le plus petit ensemble de plats qui satisfasse la contrainte que tous les invités trouveront au moins un plat à leur goût? Je dis "le" plus petit, mais en fait il peut y avoir plusieurs solutions, et j'aimerais les connaître toutes si possible. Ou, de manière plus abstraite, imaginons une matrice carrée où tous les éléments sont 0 ou 1, et tous les éléments diagonaux sont 1. Quels sont les plus petits ensembles de rangées tels que la somme (ou le OU binaire) de les rangées dans chaque ensemble n'ont pas de zéros? (Les lignes seraient les plats, les colonnes seraient les invités, 1 signifie qu'un client aime un plat et des éléments en diagonale sont 1 puisque tout le monde aime leur propre plat.)
Cela pourrait être généralisé à la non-carré matrices, ou en supprimant diagonale = 1 règle (bien que ce dernier garantit qu'il y aura toujours au moins une solution). Mais je ne me soucie pas de ces cas pour le moment ...
J'ai déjà un programme qui le résout grâce à une recherche exhaustive et qui est assez rapide pour N autour de 20, mais cela prend du temps exponentiel. Je pense que je peux avoir besoin de recourir à des algorithmes stochastiques pour trouver des solutions assez bonne pour les plus grandes valeurs de N.
Ajouté
Wow, merci pour la réponse rapide! "Set cover", c'est le nom que je cherchais. :)
Bonne question, bonne réponse. –