Dieses Problem kam in der realen Welt auf, aber ich habe es in eine allgemeinere "Lehrbuch-ähnliche" Formulierung übersetzt. Ich vermute, dass es NP ist, aber ich bin besonders daran interessiert zu wissen, ob es einen Namen hat oder gut bekannt ist, da ich denke, dass ich nicht der erste sein kann, der ihm begegnet. ;-)Ist dieses Problem NP, und hat es einen Namen?
Stellen Sie sich vor es gibt eine Potluckparty mit N Gästen. Jeder Gast darf sein "Signature Dish" zur Party bringen oder nichts mitbringen. Jeder Gast mag oder hasst jedes der Gerichte, die die anderen Gäste mitbringen (und dies ist im Voraus bekannt, da sie alle alte Freunde sind!), Aber sie alle mögen ihre eigenen Gerichte.
Gibt es einen deterministischen Algorithmus, der keine exponentielle Zeit benötigt, um den kleinsten Satz von Gerichten zu finden, der die Bedingung erfüllt, dass alle Gäste mindestens ein Gericht nach ihrem Geschmack finden? Ich sage "das" kleinste, aber tatsächlich gibt es mehrere Lösungen, und ich würde sie gerne alle kennen, wenn möglich. Stellen Sie sich eine abstraktere Matrix vor, in der alle Elemente entweder 0 oder 1 sind und alle diagonalen Elemente 1 sind. Was sind die kleinsten Sätze von Zeilen, so dass die Summe (oder das binäre ODER) von die Reihen in jedem Satz haben keine Nullen? (Die Zeilen wären die Gerichte, die Spalten wären die Gäste, 1 würde bedeuten, dass ein Gast ein Gericht mag, und diagonale Elemente sind 1, da jeder sein eigenes Gericht mag.)
Dies könnte auf nicht-quadratisch verallgemeinert werden Matrizen oder durch Entfernen der Regel diagonal = 1 (obwohl letzteres garantiert, dass es immer mindestens eine Lösung geben wird). Aber ich interessiere mich nicht für diese Fälle im Moment ...
Ich habe bereits ein Programm, das es durch eine erschöpfende Suche löst und schnell genug ist für N um 20, aber es braucht exponentielle Zeit. Ich denke, ich kann stochastischen Algorithmen wiederholen müssen gut genug Lösungen für größere Werte von N.
Added
Wow, danke für die schnelle Antwort zu finden! "Set cover", das ist der Name, nach dem ich gesucht habe. :)
Große Frage, gute Antwort. –