Programmieraufgabe 2016

  • Hallo!


    Ich suche jemanden der vielleicht die Programmieraufgabe besprechen will, also das man sich gemeinsam vll den Branch and Bound und die nötigen Datenstrukturen für das Programmieren überlegt. Wäre da jemand dabei?


    lg

  • Ja wäre dabei! Kann aber erst ab frühestens Mittwoch Nachmittag bzw. Donnerstag. Ich habe ALGODAT2 (und ein sehr ähnliches Programmierbeispiel) schon vor ca. 3 Semestern angefangen, konnte es damals aber aus Zeitdruck durch andere LVAs nicht beenden. Wäre also motiviert, das jetzt fertig zu kriegen und kann mich (hoffentlich) noch an ein paar Sachen erinnern.


    Hab dir mal message mit meiner Email als Forum-PM geschickt.

  • Hint: https://github.com/flowlo/kmst
    Und der Thread von damals: https://www.informatik-forum.at/showthread.php?93770


    Damals wurde die Programmieraufgabe in einen Wettebwerb umfunktioniert und ich wurde zweiter.


    Es haben doch einige Leute per PM gefragt was da abgeht, deshalb hier eine generelle Antwort für alle:


    Wovon lebt Branch-and-Bound?
    Das Verfahren enumeriert prinzipiell alle möglichen Lösungen, deren Anzahl in diesem Fall (kMST) exponentiell mit der Größe des Eingabegraphen steigt (konstruiere alle teilgraphen mit Knotenzahl k). Damit eine sinnvolle Laufzeit erzielt werden kann, müssen Lower Bound und Upper Bound so gewählt werden, dass die Differenz zwischen den beiden Schranken möglichst schnell möglichst klein wird. Solange ihr keinen logischen Fehler in euren Lösungen habt, werdet ihr also per Definition immer die Optimallösung finden, aber das dauert womöglich "ewig". Es bringt nichts den Code selbst zu optimieren (wenn er mal halbwegs akzeptabel Code ist), bevor man nicht geeignete Bounds hat.


    Was ist eine Lower Bound?
    Eine Lower Bound ist eine Untergrenze für noch zu erreichende Lösungen. Wenn in eurer Enumeration eine Lower Bound gilt, heißt dass, das ihr keine Lösung mehr erzeugen könnt, die besser ist (weniger Gewicht) als diese Bound. Sobald die Lower Bound größer ist als die Upper Bound ist klar, dass keine global beste Lösung mehr gefunden werden kann und der Enumerationszweig kann fallen gelassen werden. Das Ziel ist also die Lower Bound Schritt für Schritt nach oben zu bekommen, damit man möglichst früh möglichst viele Enumerationszweige ausschließen kann.


    Was ist eine Upper Bound?
    Die Upper Bound ist die Obergrenze für Lösungen in einem Enumerationszweig. Eine geltende Upper Bound kann nicht mehr überschritten werden. Das heißt alle noch zu enumerierenden Lösungen müssen besser sein als die Upper Bound. Euer Ziel muss sein, dass die Upper Bound Schritt für Schritt kleiner wird, und sich im Idealfall irgendwann mit der Lower Bound schneidet.


    Wie kann man Branchen?
    Ihr könnt zum Beispiel über die Menge der Knoten branchen, also einen Knoten einmal wählen und einmal nicht wählen (und dann jeweils rekursiv weiter). Die zweite Naheliegende Möglichkeit ist über die Kanten (wähle Kante oder nicht) zu branchen.


    Welche Bounds kann man wählen?
    Was immer sinnvoll erscheint und korrekt ist. Ihr könnt mit verschiedensten Ansätzen experimentieren und mitverfolgen wie sich andere Bounds auf die Laufzeit eures Algorithmus auswirken. Ich hatte zum Beispiel keine Upper Bound abgesehen vom tatsächlichen Gewicht meiner Lösungen. Die Lower Bound habe ich als das Gewicht der besten k - 1 wählbaren Kanten definiert (auch relativ simpel). Hier kann man sich noch mehr austoben und bessere Ansätze finden.


    Wie kann man von von Anfang an gute Bounds haben?
    Oft bringt es etwas eine "Konstruktionsheuristik" anzuwenden, bevor die eigentliche Suche nach dem globalen Optimum im Suchraum mittels Branch-and-Bound angestellt wird. Eine Konstruktionsheuristik ist meist deutlich schneller (soll heißen, geringere Komplexitätsklasse) das tatsächliche exakte Verfahren (in unserem Fall BnB). Es bieten sich hier Greedy-Algorithmen zur Konstruktion des MST an, insbesondere der Alrogithmus von Prim, der einfach nach deim fixieren von k Knoten beendet werden kann.
    Diese so relativ billig erhaltenen Graphengewichte unserere "k-Greedy-Graphen" stellen jedenfalls obere Schranken für das kMST dar.


    Was kann man noch optimieren?
    In meinem Fall hat es sich ausgezahlt, die Wurzelknoten aufsteigend mit dem Gewicht des entsprechenden "k-Greedy-Graphen" zu bearbeiten. Und natürlich den Code selbst.


    Ich diskutiere gerne mit und freue mich über ein "Thanks", wenn euch der Beitrag hilft.

  • Hi! Danke für deinen Beitrag - es ist sehr hilfreich. Du gehst mit for (int item : roots.values()) alle Knoten durch und startest den BnB, das heißt das du für jeden Knoten einen neuen rekursiven Baum machst jeweils beginnend bei einem anderen Knoten. Dann schaut der jeweilige Baum so aus, dass du einen Knoten auswählst (linker Ast) oder nicht auswählst (rechter Ast) usw. Interpretiere ich dein Branch and Bound richtig?

  • Hi! Danke für deinen Beitrag - es ist sehr hilfreich. Du gehst mit for (int item : roots.values()) alle Knoten durch und startest den BnB, das heißt das du für jeden Knoten einen neuen rekursiven Baum machst jeweils beginnend bei einem anderen Knoten. Dann schaut der jeweilige Baum so aus, dass du einen Knoten auswählst (linker Ast) oder nicht auswählst (rechter Ast) usw. Interpretiere ich dein Branch and Bound richtig?


    Ja, das ist vollkommen richtig. Die Schleife über die Knoten am Anfang braucht es, weil die Rekursion ja irgendwo angestoßen werden muss, und ich im Vorhinein nicht mit Sicherheit sagen kann, welche Knoten ausgeschlossen werden können. Beachte aber, dass roots.values() bereits nach Gewicht sortiert ist, das bringt auch nochmal einen Vorteil.


    In der rekursiven Funktion selbst wird dann ein Knoten gewählt und nicht gewählt (siehe Schreibzugriffe auf Array taken).


    Außerdem solltest du verstehen wie ich Knoten auswähle, meine Rekursionsschritte beschränken sich nämlich nicht auf die Adjazenzen eines einzelnen Knotens, sondern die Auswahl wird über die global billigste Kante getroffen. Ich wähle die Kante, rufe rekursiv auf, und dann entferne ich die Kante wieder und gehe in meiner Schleife (über die Kanten nach Gewicht) weiter.

  • Hallo, ich suche auch jemanden, mit dem ich Programmierbeispiel gemeinsam machen kann. Wenn ihr schon besprochen habt, darf ich mich beitreten?

  • Welche Bounds verwendet ihr so? Nur Lösungen als Upper Bound und illusorisch gute Kantenmengen als Lower Bound (die womöglich nicht einmal zusammenhängend sind) erscheint mir doch zu primitiv. Seid ihr auf bessere Bounds gekommen?

  • Ja, das ist vollkommen richtig. Die Schleife über die Knoten am Anfang braucht es, weil die Rekursion ja irgendwo angestoßen werden muss, und ich im Vorhinein nicht mit Sicherheit sagen kann, welche Knoten ausgeschlossen werden können. Beachte aber, dass roots.values() bereits nach Gewicht sortiert ist, das bringt auch nochmal einen Vorteil.


    In der rekursiven Funktion selbst wird dann ein Knoten gewählt und nicht gewählt (siehe Schreibzugriffe auf Array taken).


    Außerdem solltest du verstehen wie ich Knoten auswähle, meine Rekursionsschritte beschränken sich nämlich nicht auf die Adjazenzen eines einzelnen Knotens, sondern die Auswahl wird über die global billigste Kante getroffen. Ich wähle die Kante, rufe rekursiv auf, und dann entferne ich die Kante wieder und gehe in meiner Schleife (über die Kanten nach Gewicht) weiter.


    Ok verstehe. Das heißt du benutzt den Prim um jeden Knoten herum und schickst es an das Framework. Dieses nimmt dann das kleinste gefundene Gewicht und stellt es als die erste UpperBound ein. Wobei höchstwahrscheinlich wird der Prim nicht die Lösung liefern. Danach tust du an das Framework einen neuen Wert schicken (setSolution) wenn BnB zu Ende ausgeführt wird, also wenn wir genug Knoten shcon ausgewählt haben. Wenn dieser Wert kleiner ist als die bisher kleinste gefundene obere Schranke dann wird dieser als das neue UpperBound übernommen. Also sind die so gefundenen oberen Schranken nicht nur für das jewilige Teilproblem gültig sondern global gültig.

  • Hallo,


    hat jemand, der schon eine funktionierende Lösung hat oder kurz davor steht, lust sich morgen nach der Algodat 2 Vorlesung zu treffen? Habe schon eine funktionierende Lösung, gibt jedoch noch Verbesserungspotential. Als Treffpunkt bietet sich natürlich der Lernraum im 1. UG (beim Audimax Ausgang innnen) an oder ein ZID-Internetraum beim Hauptgebäude. Bei interesse bitte eine PM schicken, weil ich nicht so oft hier rein schaue.


    LG,
    barfoos

  • Ok verstehe. Das heißt du benutzt den Prim um jeden Knoten herum...


    Ich blicke in deinem Code beim Prim Algorithmus nicht ganz durch. ... Wie hast du das implementiert?


    Ja, das war schlecht formuliert. Es ist kein Algorithmus von Prim streng laut Folien (wenn du bei dieser Aufgabe nicht darüber hinauskommst Pseudocode in Javacode zu übersetzen, wirst du sie nicht schaffen), aber die Idee ist eine sehr ähnliche:




    Würde man das für k = |V| ausführen, hätte man den MST.


    ... und schickst es an das Framework. Dieses nimmt dann das kleinste gefundene Gewicht und stellt es als die erste UpperBound ein.


    Yep.


    Wobei höchstwahrscheinlich wird der Prim nicht die Lösung liefern.


    Dieser Prim-artige Algorithmus liefert gültige Lösungen, aber nicht notwendigerweise die Optimallösung, genau.


    Danach tust du an das Framework einen neuen Wert schicken (setSolution) wenn BnB zu Ende ausgeführt wird, also wenn wir genug Knoten shcon ausgewählt haben. Wenn dieser Wert kleiner ist als die bisher kleinste gefundene obere Schranke dann wird dieser als das neue UpperBound übernommen. Also sind die so gefundenen oberen Schranken nicht nur für das jewilige Teilproblem gültig sondern global gültig.


    Richtig. Eine vollständige Lösung des Problems (Subgraph G' mit |V(G)'| = k der Baum ist) kann immer als globale obere Schranke verwendet werden. Wenn man die obere Schranke anders berechnet, was natürlich auch möglich ist, muss man hier etwas genauer aufpassen. Eine Upper Bound ist nicht zwingend global zu definieren, man kann genauso gut lokale Upper (und auch Lower) Bounds für Teilbäume des Entscheidungsbaums definieren, die dann nur transitiv für die entsprechenden Kinder gelten. So eine Bound könnte man beispielsweise als Argument der rekursiven BnB Funktion implementieren.

  • flowlo


    Ich verstehe aber noch nicht ganz wann du immer die lowerBound setzt. Diese ist ja lokal also für jeden Rekursionsbaum wird sie von dir eigens angepasst.


    Und wie tief kann bei dir so ein Rekursionsbaum eigentlich werden? Meiner Meinung nach nicht länger als die Anzahl der Kanten im Graphen.


    Danke für deine Hilfe. Deine Erklärung helfen mir viel beim Verständnis.

  • Ich verstehe aber noch nicht ganz wann du immer die lowerBound setzt. Diese ist ja lokal also für jeden Rekursionsbaum wird sie von dir eigens angepasst.


    Die Lower Bound wird immer dann gesetzt, wenn feststeht, dass eine Kante nicht gewählt wird. Also hier, nachdem der rekursive Call returnt hat. Oder hier, wenn ich eine Kante ausschließe, weil sie einen Kreis erzeugen würde. Und dann gilt die Lower Bound natürlich auch für alle rekursiven Aufrufe weiterhin.


    Und wie tief kann bei dir so ein Rekursionsbaum eigentlich werden? Meiner Meinung nach nicht länger als die Anzahl der Kanten im Graphen.


    Hmm, naja ganz so simpel ist es dann doch nicht. Die Tiefe des Baums ist durch O(k) beschränkt. Das sieht man recht leicht anhand meines Funktionsarguments "left" (das angibt wie viele Kanten noch fehlen) und der Terminationsbedingung (left == 0). Das Argument wird bei jedem rekursiven Aufruf um eins dekrementiert. Bei den ersten Aufrufen ist left = k - 1. Die Tiefe des Baums ist damit recht klar erkennbar.


    Was darüber hinaus noch interessant ist, ist die Breite das Baums abhängig von der Ebene des Elternknotens. Meine Schleife über die Kanten ist durch die Anzahl der noch relevanten Kanten beschränkt. Und das variiert natürlich abhängig von der Struktur des Graphen incl. der Gewichte der Kanten. Hier könnte man sicher auch eine gute Annäherung finden, schaut aber auf den ersten Blick recht kompliziert aus.


    Jedenfalls sollte dir klar sein, dass mein Entscheidungsbaum wohl deutlich breiter als tief ist. Ob man das so will oder als gute/schlechte Charakteristik empfindet sei mal dahingestellt. Mit etwas Trickserei könnte man evtl. ein besseres Verhältnis zwischen Breite und Tiefe erzielen, aber dazu müsste man sich zumindest einmal Gedanken über die Abschätzung der Breite machen (siehe oben) und das ist mir ad hoc zu kompliziert.


    Danke für deine Hilfe. Deine Erklärung helfen mir viel beim Verständnis.


    Sehr gerne, freut mich :)

  • Die Lower Bound wird immer dann gesetzt, wenn feststeht, dass eine Kante nicht gewählt wird. Also hier, nachdem der rekursive Call returnt hat. Oder hier, wenn ich eine Kante ausschließe, weil sie einen Kreis erzeugen würde. Und dann gilt die Lower Bound natürlich auch für alle rekursiven Aufrufe weiterhin.


    Verstehe damit wird sozusagen die aktuelle Kante die nicht geht aus der lowerBound rausgechimmissen in dem man von der lowerBound das Gewicht der Kante abzieht und es wird die nächstbeste Kante zur lowerBound hinzugefügt. Damit wächst unsere lowerBound langsam im Laufe des Programms.


    Ich verstehe nur noch die Wahl der nächstbesseren Kante nicht also
    i < left - 1 ? edges[left - 1].weight : edges[i + 1].weight


    Müsste das nicht immer edges[i+1] sein nachdem der Edge Array geordnet ist?

  • Ich verstehe nur noch die Wahl der nächstbesseren Kante nicht also
    i < left -1? edges[left -1].weight : edges[i +1].weight


    Müsste das nicht immer edges[i+1] sein nachdem der Edge Array geordnet ist?


    Angenommen wir haben gerade entschieden, dass die Kante edges[i] nicht gewählt wird. Nun soll die Lower Bound erhöht werden. Wenn wir nun also edges[i].weight von der Lower Bound abziehen, müssen wir das Gewicht einer schwereren Kante wieder aufaddieren. Das bedeutet aber nicht zwingend, dass es die nächste Kante sein muss (edges[i + 1]). Vielleicht ist es ja möglich einen noch größeren Anstieg der Lower Bound zu erzielen (also eine Kante edges[j] mit j > i + 1)?!


    Für den Fall, dass wir bei unsererer Iteration erst weniger Kanten betrachtet haben, als wir eigentlich noch für eine Lösung brauchen, ist dies tatsächlich möglich. Wenn wir nämlich wissen, dass wir noch mindestens eine gewisse Anzahl an Kanten brauchen, können wir gleich die entsprechnde Kante "von links" nehmen, die wird nämlich schwerer sein als edge[i] und auf jeden Fall in der bestmöglichen Lösung enthalten sein, da es keine Lösung mit weniger Kanten geben kann: Aus i < left - 1 folgt, dass i + 1 <= left - 1.


    Off-Topic Werbeeinschaltung: Meinen Code nach vier Jahren wieder zu lesen und zu erklären ist eigentlich gar nicht so leicht. Wenn ihr eure Fähigkeit formal zu denken verbessern wollt, kann ich euch das Fach "Argumentieren und Beweisen" wärmstens empfehlen, hat mir sehr geholfen.

  • Wie hättet ihr die beiden Fragen vom Blatt beantwortet.

    Welche Vorteile/Nachteile hat binäres Branchen im konkreten Fall. Welche Alternativen gibt es?


    Wann weiß man beim Branch and Bound, dass die beweisbar beste Lösung gefunden wurde.

  • Wie hättet ihr die beiden Fragen vom Blatt beantwortet.

    Welche Vorteile/Nachteile hat binäres Branchen im konkreten Fall. Welche Alternativen gibt es?


    Wann weiß man beim Branch and Bound, dass die beweisbar beste Lösung gefunden wurde.


    Bei der ersten Frage hätte ich gesagt, die Alternative wäre es beispielsweise für jede Kante zu branchen und damit ein nicht binäres Branching zu erreichen. Binäres Branching hat den Vorteil das nicht viele Vergleiche mit jedem Knoten passieren müssen. Bei einem großen Graphen wäre es viel Aufwand den Branch auszurechnen wenn man nicht binärs Branching verwendet.


    Bezüglich wann man weiß wenn die beste beweisbare Lösung gefunden wurde - ich denke wenn die untere Schranke gleich (oder größer) der oberen Schranke ist. Habt ihr andere Ideen?

  • Hab jetzt bei der Abgabe gesagt, dass ein Nachteil vom binären Branchen beim kMST ist, dass ich nicht (ohne umständliches Nachprüfen) weiß, ob eine Kante die ich dazunehme überhaupt jemals verbunden werden kann (z.B. nicht zu weit weg ist). Ich hab jetzt so gebrancht, dass ich immer Kanten nehme, die mit den gerade ausgewählten benachbart sind und mir so sicher sein kann, nur theoretisch mögliche Kombinationen auszuwählen. Das hat ihm auch so gepasst. Man könnte es aber auch einfacher machen und immer nur die jetzigen und einen benachbarten oder alle benachbarten ohne die jetzigen nehmen für die nächsten Branches (wenn ich das richtig verstanden habe). Was ein Vorteil von binären Branchen seien kann weiß ich nicht wirklich. Dass es einfacher ist?


    Lokaler Upper Bound kann man übrigens mit einer Art mini-Prim pro Branch berechnen, dass hätte ich noch für die Dual-Heuristik gebraucht (verwende nur den globalen Upper). Aber passt schon.