5.10

[nonamenobody]

Hi!

Da ich in der letzten Zeit nicht in der VO war, weiß ich nicht, wie genau die Implementierung von Branch and Bound besprochen wurde. Die allgemeine Erklärung im Skriptum ist ja sehr abstrakt. Soll man hier sozusagen "konkreteren" Pseudocode schreiben, oder reicht es, alle Ungleichheitszeichen umzudrehen?

lg
Philipp

[grassi3000]

Also ich rätsle schon einige Tage, wie hier die Schranken zu wählen sind....

[_logonoff_]

tja, nach langem herumgrübeln und studium des folgenden artikels

http://www.csulb.edu/~obenli/Research/IE-encyc/bb.html

bin ich zu folgender lösung gekommen, die denke ich, passen müsste:

unsere zielfunktion (die maximiert werden will) ist folgende:
z(x_1 ... x_5) = 7x_1 + 3x_2 + 10x_3 + 4x_4 + 13x_5
wobei x_1 bis x_5 element von {0, 1} sind (0 steht klarerweise für "beispiel nicht rechnen" und 1 für "beispiel rechnen")
eingegrenzt wird die maximierungsaufgabe durch die nebenbedingung der dauer:
40x_1 + 10x_2 + 60x_3 + 20x_4 + 90x_5 <= 180

die probleme p werden bei mir in sextupel (denke das heißt so :-) folgenden formats gespeichert: (offset, x_1, x_2, x_3, x_4, x_5), wobei offset für die position im enumerationsbaum steht, d.h. bezeichnet, welche x bereits fixiert sind und welche noch frei sind.

nun zum pseudocode (angelehnt an algorithmus 55):


L = 0
π = {(0, 0, 0, 0, 0, 0)}
solange ein P' element π existiert {
entferne P' aus π
berechne für P' die lokale untere schranke L' durch einsetzen in die zielfunktion
berechne für P' die lokale obere schranke U' durch einsetzen in die zielfunktion, wobei alle x_i ab i=offset auf 1 gesetzt werden
falls L' > L dann {
L = L'
}
falls U' > L { //sofern nach der heuristik noch die chance besteht, die aktuelle untere schranke zu überflügeln
A = P' mit x_offset = 1 und offset++
B = P' mit x_offset = 0 und offset++
falls A und B die nebenbedingung erfüllen {
π = π vereinigt mit A, B
}
}
}


hier noch die menge π, wobei ich π jeweils nach der auflösung der sextupel eines offsets notiert habe:
(das bitmuster ist offset_x1x2x3x4x5)

π = {0_00000}
π = {1_10000, 1_00000}
π = {2_00000, 2_01000, 2_10000, 2_11000}
π = {3_00000, 3_00100, 3_01000, 3_01100, 3_10000, 3_10100, 3_11000, 3_11100}
π = {4_00100, 4_00110, 4_01100, 4_01110, 4_10000, 4_10010, 4_10100, 4_10110, 4_11000, 4_11010, 4_11100, 4_11110}
π = {5_00100, 5_00101, 5_00110, 5_00111, 5_01100, 5_01101, 5_01110, 5_01111, 5_10100, 5_10110, 5_11010, 5_11011, 5_11100, 5_11110}
zu guter letzt bleibt dann über:
π = {5_01111}

ich hoffe ich hab mich nirgends vertan....

[grassi3000]

Mhm ... schaut Logisch aus, deine LSG, blos dass du nicht die optimale LSG hast.

es geht 30,180 wenn du BCDE machst also:
π = {5_01111}

Du hast hier was doppelt:
[π = {3_00000, 3_01100, 3_01000, 3_01100, 3_10000, 3_10100, 3_11000, 3_11100}

[Kugelfisch]

Ahm kann das irgendwer kurz und pregnant erklären?

Ich steh total an!

Thx a lot!!

[grassi3000]

Soweit ich das verstanden habe, ist Branch&Bound sehr ähnlich wie die dynamische Programmierung.

Du suchst dir mal einen Startwert, und eine momentan beste Lösung. Das kann in dem Fall beides gleich sein, wie "nur das erste beispiel machen" (=das erste bsp ausgewählt und bonuspunkte dafür kassieren).

Dann iterierst du wieder weiter, wobei du nur die aktuell beste Lösung weiterverwendest, (dort wo schon was ausgwählt ist, und wo du noch immer am meisten an Zeit verbrauchen kannst).
Da gibst wieder was dazu, und vergleichst es mit den "alten" Lösungen. Wenn du wieder eins hast, mit mehr Bonuspunkten, wo du noch immer viel Zeit zur verfügung hast, wählst du das als deine Neue schranke ....

Solange, bis du keine Zeit mehr zur verfügung hast.
Wichtig ist, dass man die aktuell gewählte Lösung zwar auswählt, aber immer wieder vergangene andere Lösungen überprüft, ob diese nicht besser sind, als die aktuelle. Wenn das der Fall ist, dann ist das deine neue beste Lösung.

Das vom logonoff mit den funktionen ist hier auch nicht ganz unwichtig, denn damit werden die Teillösungen auf ihre Eigenschaften überprüft.

Der wesentliche Unterschied zur Dynamischen Programmierung ist, dass man nicht immer alle Lösungen pro ebene weiterverfolgt, sondern nur die aktuell beste

[Kugelfisch]

Ahm jo danke... Ich werd mir das ganze noch in einschlägiger Literatur ansehen.
So ganz hab ichs noch nicht.

Gut dann tschü und nochmals thx

[_logonoff_]

ad grassi:

danke, habs schon ausgebessert

ad kugelfisch:

lies dir das im skriptum nochmal durch bzw. denk dir den algorithmus 55 durch. wenn du dann noch den von mir oben geposteten link anschaust solltest du die lösung ohne große probleme nachvollziehen können (dort isses relativ praxisnah erklärt, nicht so abstrakt wie im skriptum).

[Odo]

ad logonoff, grassi3000: Irgentwie glaube ich, dass ihr beide mit Breitensuche nach neuen Lösungen sucht. Sollte man aber bei Branch&Bound nicht erst irgendeine Lösung finden und die dann ausbessern? Das geht doch am schnellsten mit der Tiefensuche, wobei man natürlich die Lösungswege, die ihre obere Schranke kleiner als die bisher beste gefundene Lösung haben, nicht mehr betrachtet.