Hallo,
ich suche nach geeigneten Verfahren um folgendes Problem zu lösen:
Objekt A: P1,P5,P7,P9
Objekt B: P2, P5, P8
Objekt C: P9
Objekt D: P2, P5
…
Welche Px (minimale Menge) werden benötigt, damit jedes Objekt wenigstens durch ein P beschrieben wird?
Hier ist es einfach: P5 und P9 oder P2 und P9
Wie muss man vorgehen, wenn man so ein Problem mit einer deutlich größeren Anzahl von Objekten und Parametern vor sich hat?
Hallo July,
mir fallen da zwei Ansätze ein. Beim ersten bin ich mir nicht sicher, ob der in jedem Fall zu einem globalen Minimum führt, aber er sollte einfacher zu implementieren sein.
Für beide Ansätze kannst du vorher aber eine Bereinigung durchführen. Suche die Objekte heraus, die nur durch einen Parameter beschrieben werden. Diese Parameter werden in jedem Fall gebraucht. Entferne dann alle Objekte, die durch diese Parameter beschrieben werden. Das dient nur der Beschleunigung der Berechnung.
Ansatz 1
Merke dir zu jedem Parameter, welche Objekte durch ihn beschrieben werden. Suche dir den Parameter mit der größten Liste und übernimm diesen in die Ergebnisliste. Subtrahiere von allen verbleibenden Listen die Objekte aus der Liste des übernommenen Parameters. Sobald alle Listen leer sind, bist du fertig. Die Listen entsprechen dann den Objekten, die durch einen Parameter,aber von keinem schon übernommenen beschrieben werden.
Ansatz 2
Wir interpretieren das ganze als Graph. Die Knoten sind dabei alle Teilmengen der Objektmenge. Wir müssen nicht alle nutzen, sonst ergibt das ja eine exponentielle Zeit- und Platzkomplexität. Die Kanten sind gerichtet und beschreiben jeweils einen Parameter. Eine Kante P von Knoten M1 nach Knoten M2 bedeutet, dass M2 aus M1 durch Subtraktion aller durch P beschriebenen Objekte entsteht. Alle Kanten haben das Gewicht 1. Aufgabe ist es nun, den kürzesten Weg von Knoten mit der Objektmenge zum Knoten mit der leeren Menge zu finden. Dafür können bekannte Algorithmen (bspw. Dijkstra oder A*) verwendet werden. Für A* muss allerdings eine sinnvolle Heuristik gefunden werden. Eventuell kann man die Mächtigkeit der Knotenmengen verwenden.
Nico
Hallo Nico,
vielen Dank für Deine Antwort.
Die erste Lösung hatte ich so bereits implementiert bis auf einen kleinen entscheidenden Fehler: Ich hab mit dem Parameter angefangen, der die wenigesten Objekte beschreibt. (was natürlich Quatsch ist). Aber auf Deine Weise kann ich 110 Parameter auf ganze 6 reduzieren - klasse 
Den zweiten Ansatz werd ich mir nochmal genau durchdenken. Momentan hab ich ihn noch nicht ganz verstanden.
Hallo,
einen Teilgraph für dein Beispiel findest du hier: http://picload.org/view/lddoopp/graph.png.html.
Dijkstra ist wahrscheinlich weniger geeignet, da der zu viele Knoten betrachtet. Dafür kommt er garantiert zum globalen Minimum.
Nico
Danke für das Bildchen. Jetzt verstehe ich das Prinzip. Ich probiere es mal aus.
July
