Angenommen, Sie haben eine Menge von Mengen, wobei jede Menge ein paar Untermengen hat.
Set1 = {(Banane, Ananas, Orange), (Apfel, Grünkohl, Gurke), (Zwiebel, Knoblauch)}
Set2 = {(Banane, Gurke, Knoblauch), (Avocado, Tomate)}
...
SetN = {...}
Das Ziel besteht nun darin, aus jeder Menge eine Teilmenge auszuwählen, während jede Teilmenge mit jeder anderen ausgewählten Teilmenge konfliktfrei sein muss. Für dieses Beispiel in Spielzeuggröße wäre eine mögliche Lösung die Auswahl (Banane, Ananas, Orange) (aus Set1) und (Avocado, Tomate) (aus Set2).
Ein Konflikt würde auftreten, wenn man die erste Teilmenge von Set1 und Set2 auswählen würde, weil die Banane in beiden Teilmengen enthalten wäre (was nicht möglich ist, weil sie nur einmal existiert).
Obwohl es viele Algorithmen gibt, konnte ich keinen geeigneten Algorithmus auswählen. Ich stehe irgendwie fest und würde mich über Antworten auf die folgenden Fragen freuen:
1) Wie finde ich einen geeigneten Algorithmus und stelle dieses Problem so dar, dass es vom Algorithmus verarbeitet werden kann?
2) Wie eine mögliche Lösung für dieses Spielzeug-Beispiel aussehen könnte (jede Sprache ist in Ordnung, ich möchte nur die Idee verstehen).
Edit1: Ich habe auch über simuliertes Annealing nachgedacht (eine mögliche Lösung zurückgeben). Dies könnte von Interesse sein, um beispielsweise die Gesamtkosten der Auswahl der Sätze zu minimieren. Ich konnte jedoch nicht herausfinden, wie man eine geeignete Problembeschreibung erstellt, die die "Konflikte" berücksichtigt.
Dieses Problem kann als genaue Abdeckung Problem verallgemeinert formuliert werden.
Erstelle ein neues Atom für jede Gruppe von Sets (Set1, Set2, etc.) und verwandle deine Eingabe in eine Instanz wie folgt:
%Vor% macht die Set* Atome primär (genau einmal bedeckt) und die anderen Atome sekundär (höchstens einmal bedeckt). Dann können Sie es mit einer Verallgemeinerung von Knuths Algorithmus X lösen.
Mit Blick auf die Liste der Sets hatte ich das Bild eines Irrgartens mit mehreren Eingängen. Die Aufgabe ähnelt der Verfolgung von Pfaden von oben nach unten, die frei von Teilmengenüberschneidungen sind. Das Beispiel in Haskell wählt alle Eingänge aus und probiert jeden Pfad aus und gibt diejenigen zurück, die Erfolg haben.
Ich verstehe, wie der Code funktioniert (Algorithmus):
Wählen Sie für jede Teilmenge in der ersten Menge jede Teilmenge in der nächsten Menge aus, in der die Schnittmenge dieser Teilmenge mit jeder der Teilmengen im akkumulierten Ergebnis Null ist. Wenn keine Teilmengen den Kriterien entsprechen, brechen Sie diese Belastung der Schleife. Wenn es keine Sätze mehr gibt, aus denen Sie auswählen können, geben Sie das Ergebnis zurück. Rufen Sie die Funktion rekursiv für alle ausgewählten Teilmengen auf (und entsprechende Akkumulationsergebnisse).
%Vor%AUSGABE:
%Vor%Tags und Links algorithm design-patterns