2010-02-18 7 views
23

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. :)

+0

Große Frage, gute Antwort. –

Antwort

22

Dies nennt man das SET COVER Problem und es ist NP-vollständig.

0

Das Set-Cover-Problem, wie im Wikipedia-Artikel beschrieben, mit dem Antti Huima verbunden ist, fehlt die Eigenschaft eines jeden Gastes, der sein eigenes Gericht mag. Ich weiß nicht, ob das einen Unterschied macht.

+0

Nein, es macht keinen Unterschied von der Komplexität Perspektive ... auch das Problem ist nicht wirklich voll SET COVER direkt, weil in dem Problem die Anzahl der verschiedenen Elemente gleich der Anzahl der Sätze, die im Allgemeinen ist keine Einschränkung in SET COVER . –

Verwandte Themen