Hallo auch,
seit ein paar Tage beschäftige ich mich nach Jahren mit meinem eigentlichen Lieblingsthema, dem Backtracking.
Das benötige ich für folgende Aufgabe:
Zur Zeit programmiere ich einen Produktkonfigurator in dem der Kunde mehre Geräte auswählen kann (mehrfachwahl ist möglich).
Der problematische Algorithmus soll hingehen und aus allen verfügbaren Produktpaketen diejenigen raussuchen (auch mehrfach), die die Auswahl des Kunden abdecken.
Damit der Kunde sich nicht betrogen fühlt, sollte natürlich die billigste Kombination aus Paketen angegeben werden (ein Paket kann mehrere, sowohl verschiedene als auch gleiche, Geräte enthalten, als auch nur ein Gerät).
Das brüllt meiner Meinung nach nach Backtracking.
Bevor ich den Ablauf beschreibe, hier ein paar Kürzel:
Mg = Menge der ausgewählten Geräte
Mg' = Menge der noch verfügbaren Geräte (am Anfang gleich Mg)
Vp = Verfügbaren Pakete, deren Inhalt Teilmenge von Mg ist (sortiert nach komplexe/große Pakete zuerst, um möglichst schnell eine gute Kombination zu finden)
Vp' = Menge der noch verfügbaren Pakete, deren Inhalt Teilmenge von Mg' ist (Reihenfolge wie bei Vp, wird beibehalten)
Bg = TeilMengen von Mg', die nicht zum Erfolg führten
Lp = Lösungsmenge, die eine oder mehre Mengen von Paketen enthält, die die Auswahl des Kunden abdeckt.
Max = aktuell niedrigste Zahl von Paketen für eine gültige Kombination
Von daher bin ich auch wie folgt beim "Tracking" vorgegangen:
Die Vorgehensweise sieht so aus, dass ich pro Rekursionsaufruf die Menge Mg und die dazugehörige Menge Vp habe.
Ich suche eine Kombination aus Paketen, von daher muss ich über Vp iterieren.
Aufgrund der Sortierung fange ich also beim Backtracking den ersten möglichen Lösungsknoten mit einem großen Paket ab, so dass die Wahrscheinlichkeit recht groß ist, dass die ersten möglichen Kombinationen schon billig sind.
Ich erstelle Mg' indem ich den Packungsinhalt des aktuellen Pakets von Mg abziehe.
Anhand einer kleinen Abfrage erstelle ich Vp' von Vp mittels des aktuellen Pakets (falls dieses Paket nicht mehr gefüllt werden kann, wird es von Vp abgezogen, falls nochmal möglich, beibehalten).
Danach rufe ich mit Vp' als Vp und Mg' als Mg die Funktion vom neuen auf.
Jetzt zum "Back":
Am Anfang der Backtrackingfunktion, also noch bevor ich über Vp iteriere, überprüfe ich Vp und Mg.
Ist die Vp = 0, sind also keine Verpackungen mehr verfügbar, sollte ich eine Lösung gefunden haben (In der Regel gibt es für jedes Gerät auch eine Single-Verpackung, wo nur das Gerät selber enthalten ist).
Überprüfung, ob die Lösung schon bekannt ist, wenn nicht, dann füge hinzu, ansonsten RETURN FALSE.
Zur Sicherheit wurde hier noch eine weitere Abfrage eingebaut, die überprüft, ob Mg = 0 ist. Falls es wider erwarten doch mal Geräte gibt, die es nur in Zusammenhang mit anderen Geräten zu kaufen gibt, kann es ja sein, dass Vp = 0 ist, aber nicht alle Geräte in der Lösung vorkommen (können), dann würde auch hier RETURN FALSE greifen.
Im Grunde war es das schon.
An der Stelle des Rekursionsaufrufes wird der Rückgabewert zwischengespeichert, so das im Idealfall, wenn es in einer Stufe TRUE war, dieser auch zurückgegeben wird, ansonsten FALSE.
Das Problem:
Ich lasse mir die Lösungen in einer Datei ausgeben, aufgrund der Umgebung (PHP auf Server) sagt irgendwann der Browser "Keine Lust mehr".
Die (ersten) guten Lösungen findet er innerhalb einer Sekunde, aber durchlaufen muss der Algorithmus soweit ja alles, von daher hört er kaum auf. Pro Rekursion ein Testeintrag in die Datei führte zu mehreren Millionen Zeilen.
Die Hoffnung, das Problem durch einige typische Optimierungen in den Griff zu bekommen, wurde zunichte gemacht.
Hier die Optimierungen:
Max:
Warum soll ich eine Lösung verfolgen, wenn ich jetzt schon weiss, dass es mehrere Pakete wären/ dass es teurer wird, als in den bisherigen Lösungen?
Also neben den Lösungen auch Max gespeichert (bzw Min). Habe ich in einer Rekursionsstufe keine Lösung gefunden (BACK), könnte ich ja über Vp iterieren und ggf noch eines hinzufügen. Das macht dann bei einem passenden aber nur Sinn, wenn dadurch nicht Summe > Max wird. Sollte das der Fall sein, kann ich mir das Generieren von Vp', Mp' und den erneuten Rekursionsaufruf sparen.
"Böses" Vg':
Nach oben beschriebenem Verhalten habe ich 3 Stellen, wo ein Rekursionsaufruf einen Misserfolg zurückgeben kann: Wenn keine Pakete mehr da sind, aber noch Geräte vorhanden. Wenn Eine Lösung schon existiert. Wenn ein Rekursionsstufe komplett durch ist, aber dabei keine erfolgreiche Lösung hervorgekommen ist.
Jedes Mal, wenn einer der 3 Fälle auftritt, wird die Mg bzw Mg' zu Bg hinzugefügt.
Bevor nun ein Rekursionsaufruf bzgl eines neuem Vp' und eines neuen Mg' aufgrufen wird, wird überprüft, ob Mg' nicht schon in Bg vorhanden ist, wenn ja, so wird ein erneuter Aufruf unterlassen, da der Misserfolg ja schon vorprogrammiert ist.
Trennung von Multipaketen und Singlepaketen:
Grundsätzlich werden Pakete, die nur ein Gerät enthalten von den anderen getrennt. Diese werden dann nur abgefragt, wenn keine weiteren Pakete mehr verfügbar sind (Vg = 0). Das erspart weitere Rekursionsaufrufe, mit Singlepaketen. Zusätzlich muss aber die Kombination bzgl. des Preises gegen Max überprüft werden. Wenn hier dann festgestellt wird, dass nach dem Hinzufügen der Singlepakete die Kombination in Preis/Paketanzahl überschritten wird, wird diese nicht Lp hinzugefügt und stattdessen FALSE zurückgegeben (gleichzeitig auch der Restbestand Bg hinzugefügt).
Aufgrund der überschaubaren Größe der Menge an Singlepaketen als Liste wird diese nicht bei jedem Aufruf gefiltert, sondern einfach so übergeben, um hier unnötige Iterationen beim Filtern zu sparen.
Soweit so viel Text.
Programmiert ist das Ganze in PHP, als Datenstrukturen werden zur Zeit ausschliesslich Arrays benutzt. Zur Überprüfung von Mengen werden Listen mit Strings (meist Kommaseparierte Werte der Arrays) genutzt.
Bei um die 22 vom Kunden ausgewählten Geräten läuft das Skript innerhalb von 1 Sekunde durch und schliesst mit sinnvollen Ergebnissen ab.
Je mehr es werden, um so länger dauert es. Laut temporäre Textdateiausgabe scheint er aber auch dann innerhalb von einer Sekunde die wichtigsten Lösungen gefunden zu haben.
Was nun irgendwie fehlt, scheint ein sinnvoller Abbruch.
Ich hoffe, soweit war alles gut verständlich.
Ich bedanke mich jetzt schon mal für eine Antwort.
seit ein paar Tage beschäftige ich mich nach Jahren mit meinem eigentlichen Lieblingsthema, dem Backtracking.
Das benötige ich für folgende Aufgabe:
Zur Zeit programmiere ich einen Produktkonfigurator in dem der Kunde mehre Geräte auswählen kann (mehrfachwahl ist möglich).
Der problematische Algorithmus soll hingehen und aus allen verfügbaren Produktpaketen diejenigen raussuchen (auch mehrfach), die die Auswahl des Kunden abdecken.
Damit der Kunde sich nicht betrogen fühlt, sollte natürlich die billigste Kombination aus Paketen angegeben werden (ein Paket kann mehrere, sowohl verschiedene als auch gleiche, Geräte enthalten, als auch nur ein Gerät).
Das brüllt meiner Meinung nach nach Backtracking.
Bevor ich den Ablauf beschreibe, hier ein paar Kürzel:
Mg = Menge der ausgewählten Geräte
Mg' = Menge der noch verfügbaren Geräte (am Anfang gleich Mg)
Vp = Verfügbaren Pakete, deren Inhalt Teilmenge von Mg ist (sortiert nach komplexe/große Pakete zuerst, um möglichst schnell eine gute Kombination zu finden)
Vp' = Menge der noch verfügbaren Pakete, deren Inhalt Teilmenge von Mg' ist (Reihenfolge wie bei Vp, wird beibehalten)
Bg = TeilMengen von Mg', die nicht zum Erfolg führten
Lp = Lösungsmenge, die eine oder mehre Mengen von Paketen enthält, die die Auswahl des Kunden abdeckt.
Max = aktuell niedrigste Zahl von Paketen für eine gültige Kombination
Von daher bin ich auch wie folgt beim "Tracking" vorgegangen:
Die Vorgehensweise sieht so aus, dass ich pro Rekursionsaufruf die Menge Mg und die dazugehörige Menge Vp habe.
Ich suche eine Kombination aus Paketen, von daher muss ich über Vp iterieren.
Aufgrund der Sortierung fange ich also beim Backtracking den ersten möglichen Lösungsknoten mit einem großen Paket ab, so dass die Wahrscheinlichkeit recht groß ist, dass die ersten möglichen Kombinationen schon billig sind.
Ich erstelle Mg' indem ich den Packungsinhalt des aktuellen Pakets von Mg abziehe.
Anhand einer kleinen Abfrage erstelle ich Vp' von Vp mittels des aktuellen Pakets (falls dieses Paket nicht mehr gefüllt werden kann, wird es von Vp abgezogen, falls nochmal möglich, beibehalten).
Danach rufe ich mit Vp' als Vp und Mg' als Mg die Funktion vom neuen auf.
Jetzt zum "Back":
Am Anfang der Backtrackingfunktion, also noch bevor ich über Vp iteriere, überprüfe ich Vp und Mg.
Ist die Vp = 0, sind also keine Verpackungen mehr verfügbar, sollte ich eine Lösung gefunden haben (In der Regel gibt es für jedes Gerät auch eine Single-Verpackung, wo nur das Gerät selber enthalten ist).
Überprüfung, ob die Lösung schon bekannt ist, wenn nicht, dann füge hinzu, ansonsten RETURN FALSE.
Zur Sicherheit wurde hier noch eine weitere Abfrage eingebaut, die überprüft, ob Mg = 0 ist. Falls es wider erwarten doch mal Geräte gibt, die es nur in Zusammenhang mit anderen Geräten zu kaufen gibt, kann es ja sein, dass Vp = 0 ist, aber nicht alle Geräte in der Lösung vorkommen (können), dann würde auch hier RETURN FALSE greifen.
Im Grunde war es das schon.
An der Stelle des Rekursionsaufrufes wird der Rückgabewert zwischengespeichert, so das im Idealfall, wenn es in einer Stufe TRUE war, dieser auch zurückgegeben wird, ansonsten FALSE.
Das Problem:
Ich lasse mir die Lösungen in einer Datei ausgeben, aufgrund der Umgebung (PHP auf Server) sagt irgendwann der Browser "Keine Lust mehr".
Die (ersten) guten Lösungen findet er innerhalb einer Sekunde, aber durchlaufen muss der Algorithmus soweit ja alles, von daher hört er kaum auf. Pro Rekursion ein Testeintrag in die Datei führte zu mehreren Millionen Zeilen.
Die Hoffnung, das Problem durch einige typische Optimierungen in den Griff zu bekommen, wurde zunichte gemacht.
Hier die Optimierungen:
Max:
Warum soll ich eine Lösung verfolgen, wenn ich jetzt schon weiss, dass es mehrere Pakete wären/ dass es teurer wird, als in den bisherigen Lösungen?
Also neben den Lösungen auch Max gespeichert (bzw Min). Habe ich in einer Rekursionsstufe keine Lösung gefunden (BACK), könnte ich ja über Vp iterieren und ggf noch eines hinzufügen. Das macht dann bei einem passenden aber nur Sinn, wenn dadurch nicht Summe > Max wird. Sollte das der Fall sein, kann ich mir das Generieren von Vp', Mp' und den erneuten Rekursionsaufruf sparen.
"Böses" Vg':
Nach oben beschriebenem Verhalten habe ich 3 Stellen, wo ein Rekursionsaufruf einen Misserfolg zurückgeben kann: Wenn keine Pakete mehr da sind, aber noch Geräte vorhanden. Wenn Eine Lösung schon existiert. Wenn ein Rekursionsstufe komplett durch ist, aber dabei keine erfolgreiche Lösung hervorgekommen ist.
Jedes Mal, wenn einer der 3 Fälle auftritt, wird die Mg bzw Mg' zu Bg hinzugefügt.
Bevor nun ein Rekursionsaufruf bzgl eines neuem Vp' und eines neuen Mg' aufgrufen wird, wird überprüft, ob Mg' nicht schon in Bg vorhanden ist, wenn ja, so wird ein erneuter Aufruf unterlassen, da der Misserfolg ja schon vorprogrammiert ist.
Trennung von Multipaketen und Singlepaketen:
Grundsätzlich werden Pakete, die nur ein Gerät enthalten von den anderen getrennt. Diese werden dann nur abgefragt, wenn keine weiteren Pakete mehr verfügbar sind (Vg = 0). Das erspart weitere Rekursionsaufrufe, mit Singlepaketen. Zusätzlich muss aber die Kombination bzgl. des Preises gegen Max überprüft werden. Wenn hier dann festgestellt wird, dass nach dem Hinzufügen der Singlepakete die Kombination in Preis/Paketanzahl überschritten wird, wird diese nicht Lp hinzugefügt und stattdessen FALSE zurückgegeben (gleichzeitig auch der Restbestand Bg hinzugefügt).
Aufgrund der überschaubaren Größe der Menge an Singlepaketen als Liste wird diese nicht bei jedem Aufruf gefiltert, sondern einfach so übergeben, um hier unnötige Iterationen beim Filtern zu sparen.
Soweit so viel Text.
Programmiert ist das Ganze in PHP, als Datenstrukturen werden zur Zeit ausschliesslich Arrays benutzt. Zur Überprüfung von Mengen werden Listen mit Strings (meist Kommaseparierte Werte der Arrays) genutzt.
Bei um die 22 vom Kunden ausgewählten Geräten läuft das Skript innerhalb von 1 Sekunde durch und schliesst mit sinnvollen Ergebnissen ab.
Je mehr es werden, um so länger dauert es. Laut temporäre Textdateiausgabe scheint er aber auch dann innerhalb von einer Sekunde die wichtigsten Lösungen gefunden zu haben.
Was nun irgendwie fehlt, scheint ein sinnvoller Abbruch.
Ich hoffe, soweit war alles gut verständlich.
Ich bedanke mich jetzt schon mal für eine Antwort.