Branch and Bound

[pozzitiv]

Hi Leute. Brauche dringend Hilfe. Habe eine Aufgabe bekommen die ich bis Montag machen muss, aber nach langem recherchieren kaum was verstanden.
Die Aufgabe lautet demnächst:
Es soll mit Hilfe der Simulation gezeigt werden, wie das Branch and Bound Verfahren bei einer großen Anzahl möglicher Kombinationen die optimale Lösung findet. Wie lange dauert das bei n! Möglichkeiten wenn n=5 ist im Vergleich zu n=10 und n=20 und n=40?

Ich habe stundenlang zu dem Thema was gelesen aber checke trotzdem nicht wie es aussehen soll. Vielleicht kann mir da jemand helfen?

 

[Dow Jones]

Ist denn auch eine konkrete Aufgabe gegeben, die mit Hilfe des Branch-and-Bound Verfahrens gelöst werden soll? So ganz pauschal kann man da ja herzlich wenig zu sagen. BnB bringt einem im Worst Case ja genau gar nichts. ???:L

 

[pozzitiv]

die Aufgabe ist halt die Dauer zu vergleichen. sonst kann man sich alles selbst denken...
hat vielleicht jemand eine Lösung dafür?

 

[ThreadPool]

die Aufgabe ist halt die Dauer zu vergleichen. sonst kann man sich alles selbst denken...
hat vielleicht jemand eine Lösung dafür?

Ja aber um die Dauer durch eine Simulation (praktische Anwendung) zu vergleichen benötigst du ein Problem an dem du das demonstrieren kannst. D.h. du musst dir ein Problem hernehmen das dir ca. 40! Möglichkeiten bietet einen passenden BnB Algorithmus aussuchen und dann schauen wie das sich gegenüber den naiven Algorithmen schlägt. Ich vermute das ihr ein paar Probleme die sich mit BnB lösen lassen irgendwo aufgeführt habt bzw. in einer Vorlesung etc. erwähnt wurden.

Als Beispiel welches sich, denke ich, recht zügig implementieren lassen sollte wäre Tic Tac Toe mit MiniMax und Alpha-Beta-Pruning (abp gehört zu der Klasse der BnB-Methoden). Das bietet dir zwar nur läppische 9! Möglichkeiten aber dadurch ist der Baum noch darstellbar (vernünftige Graphenbibliothek vorausgesetzt) und man kann zeigen wie er ausgedünnt aussieht etc. Weitere Möglichkeiten wären Wegfindung mit A* (der gehört auch zu den BnBs) oder was ganz unspektakuläres das Wasserkrugproblem. Für alle drei aufgeführten Beispiele gibt es reichlich Quellen im Netz, samt theoretischer Erklärung und Implementierung.

 

[SlaterB]

@ThreadPool
das klingt für mich in Bezug auf eine einfache allgemeine Frage

Es soll mit Hilfe der Simulation gezeigt werden, wie das Branch and Bound Verfahren bei einer großen Anzahl möglicher Kombinationen die optimale Lösung findet. Wie lange dauert das bei n! Möglichkeiten wenn n=5 ist im Vergleich zu n=10 und n=20 und n=40?

nicht sehr hilfreich, mir selber fällt allerdings noch weniger ein

 

[ThreadPool]

@ThreadPool
das klingt für mich in Bezug auf eine einfache allgemeine Frage

nicht sehr hilfreich, mir selber fällt allerdings noch weniger ein

Das mag sein aber wir sind uns doch einig das basierend auf den Informationen des Originaltextes nicht vielmehr rauszuholen ist. Wobei wenn man genauer liest: "mit Hilfe der Simulation" - die Annahme getroffen werden könnte es gäbe eine fertige Simulation die man für dieses Experiment verwenden könnte um die Aufgabe zu lösen...

 

[Dow Jones]

die Aufgabe ist halt die Dauer zu vergleichen. sonst kann man sich alles selbst denken...
hat vielleicht jemand eine Lösung dafür?

Der Witz bei BnB besteht ja darin, eine (optimale) Lösung sukzessive aus einer Kombination von Teillösungen zusammenzusetzen. Dazu versucht man jedesmal, wenn man zu seiner bisherigen Kombination von Teillösungen eine neue Teillösung hinzufügt, abzuschätzen, wie gut die Gesamtlösung überhaupt noch werden kann. Dabei hofft man irgendwann festzustellen, das manche (Teil-)Kombinationen von Teillösungen in jedem Fall eine besseres Gesamtlösung ergeben werden als andere. Und diesen anderen betrachtet man dann eben gar nicht mehr weiter, und spart sich sich dadurch die Überprüfung aller Gesamtlösungen, welche diese anderen (schlecheren) Kombinationen von Teillösungen enthalten.

Das Ganze funktioniert aber nur dann, wenn man auch eine Möglichkeit hat die Güte einer Kombination von Teillösung abzuschätzen. Das ist natürlich vollkommen von dem zu lösenden Problem abhängig, und eben diese Problembeschreibung fehlt in deinem Post. Doch genau die Möglichkeit der Abschätzung der Güte ist essentiell für den Erfolg (oder Misserfolg) von BnB.

Wenn in deiner Aufgabe wirklich nichts weiter steht, dann wäre die einzige gerechtfertigte Aussage, das sich BnB nicht schlechter verhält als ein naiver Algorithmus (der alle möglichen Lösungen ausprobiert). Bei 10! möglichen Lösungen würde BnB also höchstens 10!/5! mal so lange brauchen wie für 5! mögliche Lösungen im worst case gebraucht wird. Was keine besonders hilfreiche Aussage ist. :noe:

 

[pozzitiv]

Ich vermute das ihr ein paar Probleme die sich mit BnB lösen lassen irgendwo aufgeführt habt bzw. in einer Vorlesung etc. erwähnt wurden.

Ja, wir hatten was nach dem motto es steht eine blablamaschine zur verfügung mit dieser müssen aber 5 verschiedene Erzeugnisse bearbeitet werden. Erzeugnis 1 hat X1 min Rüstzeit und Y1 min bearbeitungszeit, Erzeugnis 2 hat X2 min Rüstzeit und Y2 min bearbeitungszeit... Erzeugnis 5 hat X5 min Rüstzeit und Y5 min bearbeitungszeit. Die Maschine hat z.B. tägliche bzw. monatliche Laufzeit von z Std. Wie maximiert man die tägliche/monatliche Produktion. Verständlich? =)

Weitere Möglichkeiten wären Wegfindung mit A* (der gehört auch zu den BnBs) oder...

Ich denke mal Wegfindung passt hier ganz gut. Ich habe sogar ein Java-Applet mit der Lösung gefunden (Traveling Salesman Problem - Lösungsansätze - Branch and Bound).
Und ausserdem 2 unterschiedliche Java-Implementierungen, aber keine von beiden funzt richtig.

Weißt vielleicht jemand wo ich eine funktionierende Java-Implementierungen finde?

die Annahme getroffen werden könnte es gäbe eine fertige Simulation die man für dieses Experiment verwenden könnte um die Aufgabe zu lösen...

Das wär natürlich traumhaft)) Aber leider nicht der Fall.
Also man kann sich selbst was aussuchen, ist ihm latte.

Dow Jones, zu dem Algorithmus habe ich mich schon informiert Aber trotzdem danke. Wie gesagt man kann sich die Problemstellung selbst aussuchen, ist dem Dozent unwichtig. Und nochmal:

Ich denke mal Wegfindung passt hier ganz gut. Weißt vielleicht jemand wo ich eine funktionierende Java-Implementierungen finde?

 

[pozzitiv]

Beispiele gibt es reichlich Quellen im Netz, samt theoretischer Erklärung und Implementierung.

Würdest du vielleicht welche zeigen? Also, ich gehe davon aus, dass du welche genau gesehen hast.
Weil ich habe bisher nur keine gute beispiele gefunden. Der eine ist z.B. vom 00er Jahren, mit alter MS-Bibliothek, die nicht mehr zur Verfügung steht. Eine weitere funzt überhaupt nicht.Die dritte ist nur als .jar-Datei da, aber kein Quellcode...and so on...

 

[Dow Jones]

Branch and Bound <- Da gibt's zwei Java Quellcodes, einmal für den Knapsack und einmal für TSP. Aber magst du das nicht lieber selber schreiben? Soo schwer ist's ja auch net.