View Full Version : [Frage] Aufgabe 5.5
a.menace
25-05-2003, 17:54
Bei Branch and Bound werden eine globale Unterschranke und die lokalen Oberschranke für jeden einzelnen Lösungsknoten errechnet. Ist die Oberschranke in einem Knoten kleiner also die Unterschranke, so kann man den Knoten samt seinem Unterbaum streichen und davon ausgehen das die optimale Lösung in einem anderen Unterbaum versteckt ist.
In unserem Beispiel haben wir als Unterschranke den Wert 15, weil in unserem Bsp genau G2,G3,G4 reinpassen(deren Gewicht ist 70)
als Oberschranke haben wir den Wert 23, weil wir in unserem Bsp genau G2+G3+9/10G1 einpacken können und somit unser Rucksack mit 100 Kilos gestopft ist.
nach wi/gi G1= 0,20 G2= 0,26 G3= 0,24 G4= 0,06
absteigend Sort nach wi/gi = G2, G3, G1, G4
buechsengustel
25-05-2003, 18:05
hab ich auch genau so
gleich beim ersten Knoten denke ich, du darfst G4 nicht mehr einpacken. Es heißt ja nicht, dass du alle Ggstd. die nicht mehr reinpassen überspringen sollst und dann einen, der zufälligerweise wieder reinpasst doch einpackst, oder?
Ansonsten hab ichs auch so, nur halt immer bei unterer Schranke 14 statt 15
ich auch. Aber noch etwas. Da wir immer zuerst dorthin laufen wo wir als erstes einpacken frage ich mich warum du auf der rechten seite (Also dort wo du G2 nicht eingepackt hast) überhaupt noch eines tiefer rechnest.
Du erkennst ja sofort, weil du als obere und untere Schranke 17 erhalten hast (und alle Lösungen im linken schon kennst), daß eine untere Schranke schon größer ist als die obere im rechten. Du verwirfst es ja daher auch sofort.
Grüße,
wolti
gleich beim ersten Knoten denke ich, du darfst G4 nicht mehr einpacken. Es heißt ja nicht, dass du alle Ggstd. die nicht mehr reinpassen überspringen sollst und dann einen, der zufälligerweise wieder reinpasst doch einpackst, oder?
Naja, Da das Ziel eine untere Schranke zu ermitteln ist, ist das sicher besser es so zu machen. Ich habs ihn meiner ersten Version auch so gemacht, und liefert klarerweise auch das gleiche Ergebniss.
Grüße,
Wolti
buechsengustel
25-05-2003, 19:38
@ sensei: doch, das heißt es.
"Die untere Schranke erhält man, indem man alle Gegenstände, deren Variable noch nicht festegelegt ist, in der durch F gegebenen Reihenfolge durchläuft und den aktuellen Gegenstand einpackt, falls noch Platz in der Badetasche ist."
für alle Gi , i=1...N {
falls (bereits fixiertes gewicht + Gi <= K) dann {
packe Gi ein;
}
i = i + 1;
}
buechsengustel
25-05-2003, 19:42
@ wolti
ja, das stimmt schon. der rechte teilbaum hört bei mir auch gleich nach dem ersten kind (mit 17,17) auf.
Könnte mir vielleicht jemand erklären, wie das mit der oberen Schranke funktioniert? Vor allem die Sache mit r*(gi/wi). Das check ich noch nicht wirklich.
Wär ganz toll!!:)
Lg Stella
Könnte mir vielleicht jemand erklären, wie das mit der oberen Schranke funktioniert? Vor allem die Sache mit r*(gi/wi). Das check ich noch nicht wirklich.
Wär ganz toll!!:)
Lg Stella
Das mit der oberen Schranke ist ganz einfach. Du würdest einfach den Rest des Rucksackes noch mit dem besten Gegenständen füllen (drum habe wir sie sortiert), und den Rest noch mit einem Teil wo nicht mehr reinpasst. Dies ist eine obere Schranke, da die nie überschritten werden kann.
Hast du zum Beispiel schon fixiert, dass Gegenstand 1 drinnen ist und Gegenstand 2. So berechnet sich eine untere Schranke dahinein, dass einfach noch irgendwie ein paar Sachen reinpackst. Die obere Schranke, der bestmögliche Fall wo es geben könnte, wäre wenn du von dem letzten Gegenstand, der nicht mehr in den Rucksack geht gerade noch soviel mitnehmen könntest das er voll wäre.
r ist also der Rest vom Platz im Rucksack. Der Gegenstand i hat Gewicht gi und wert wi. Wir dividieren jetzt wi/gi. Dan wissen wir, wieviel Wert er auf einer Platzeinheit erzeugen würde. Das multipliziert mit r gibt dann einen Wert wo wir noch dazunehmen und das ist eine obere Schranke.
Oder anders. Alle möglichen Lösungen in diesem Pfad sind nach oben beschränkt durch diese Schranke.
Grüße,
Wolti
Thx Wolti!!! Jetzt hab ichs! http://hades.gothic.at/iforum/images/smilies/idea.gif
Lg Stella
Da ist dann aber in der Angabe ein Fehler, oder? Da steht nämlich:
... Dann zählt man r*gi/wi noch zu dem Wert ...
Stimmt das, dass das in der Angabe falsch ist?
der nutzen is sicher wert pro gewicht. und deswegen r* wert/gewicht noch dazuzählen... buchstaben für wert und gewicht nehmen sie teilweise recht verschiedene, am besten man merkt sichs also mit den worten...
also: wert/gewicht, dann hab ich für EINE gewichtseinheit den wert, dann r-mal nehmen, um kapazität des rucksacks voll auszuschöpfen!
hätte da noch eine frage dazu:
warum wird bei dem knoten {G2,G3} [u:15,O:15] abgebrochen?
daneben {G1,G2} [u:19,o:19] hab ihc ja eine ähnliche situation und mach weiter?
gut, ich gebs zu, branch and bound ist noch ein buch mit 7 siegeln für mich, aber ....
ja, wenn ich das verstehen würde wärens schon nur noch 6 :)
danke
sebi
Georg Kraml
27-05-2003, 00:18
warum wird bei dem knoten {G2,G3} [u:15,O:15] abgebrochen?
Weil dieser Knoten eine lokale Oberschranke hat, die unter der zu diesem Zeitpunkt aktuellen globalen Unterschranke liegt. Ausführlicher: Zu dem Zeitpunkt, zu dem wir {G2,G3} untersuchen, wissen wir bereits, dass die optimale Lösung einen Wert von ÜBER 15 hat, es hat daher keinen Sinn, einen Baumast weiter zu verfolgen, dessen beste Lösung einen Wert von HÖCHSTENS 15 haben wird.
daneben {G1,G2} [u:19,o:19] hab ihc ja eine ähnliche situation und mach weiter?
Ähnlich, ja. Aber eben nicht äquivalent.
also der einzige Ast in dem die unterschranke größer als 15 ist ist der ast wenn man nur G2 nimmt und dann G3 nicht. (U:19)
aber heißt es nicht es der baum wird durch tiefensuche durchlaufen, immer in dem ast mit 1 beginnend? Und dann wüsste ich zu dem Zeitpunkt noch gar nichts von der Schranke U:19.
oder ist das auch falsch?
lg und danke
sebi
Tiniiiii
27-05-2003, 23:46
Ich bin verwirrt ... könnte jemand so nett sein eine richtige Lösung (jpg, txt) posten??? Eine (halb)falsche Lösung & 1000 Korrektur Postings bringen nicht wirklich Übersichtlichkeit in die Sache ...
Pleeeaaase & thanx! Wär ur lieb!
Eigentlich kannst du dich auf die Lösung von a.menace durchaus verlassen, also die allererste jpg. Da gibt's überhaupt keine Fehler; gut vielleicht fehlen ein paar Bezeichnungen, wie G_3+ oder so, aber es ist schon fehlerfrei...
Ich würde zu 95% das selbe posten :)
im skriptum auf Seite 141 steht doch falls untere Schranke = obere Schranke ist man fertig, da die optimale Lösung gefunden wurde.
Das wäre doch gleich ganz am anfang des Baumes bei O=17 U=17 ( also da wo ich g2 weglasse ) :confused:
Bin auch grade draufgekommen. Also hat wer vielleicht eine ERklärung dafür?
Die Zeit wird schon ein bissi knapp
Danke
im skriptum auf Seite 141 steht doch falls untere Schranke = obere Schranke ist man fertig, da die optimale Lösung gefunden wurde.
Das wäre doch gleich ganz am anfang des Baumes bei O=17 U=17 ( also da wo ich g2 weglasse ) :confused:
bin mir zwar nicht ganz sicher, aber wenn ich mir das so überleg denke ich, dass das nur gilt wenn ich das problem nicht in teilprobleme aufgeteilt habe. also angenommen wir hätten bei diesem beispiel eine gesamt kapazität von 105 einheiten. dann hätte ich doch gleich am anfang eine obere schranke mit 24 und die untere wäre dann nämlich auch 24. naja dann ists natürlich naheliegend dass das bereits das ergebnis ist. aber wenn wir konkret auf unser beispiel nochmal zurückgehen, also mit K=100 dann haben wir doch als, bezeichnen wirs von mir aus als oberste schranke, 23.
grösser als 23 gehts sicher nicht. naja und o=17, u=17 sagt dann insofern nichts aus. wenn schon, dann bräucht ma hier irgendwo ne untere schranke die 23 ergibt und dann bräucht ma nimma weitertun, denn wenns nicht besser wie 23 werden kann und auch nicht schlechter, dann wirds wohl genau 23 werden, aber wenn dies auftretet dann eh gleich am anfang bevor wir in teilprobleme teilen.
denke ich zumindest.
mfg JayJay
man kann das 17,17 nicht weglassen, weil auf der selben ebene eine bessere obere schranke existiert (linker Ast)... dort gehn die Lösungen bis O=23, was natürlich besser ist. d.h. für g1 nicht einpacken ist 17 die optimale lösung, aber bei g1 einpacken kanns noch bessere geben...
man kann das 17,17 nicht weglassen, weil auf der selben ebene eine bessere obere schranke existiert (linker Ast)... dort gehn die Lösungen bis O=23, was natürlich besser ist. d.h. für g1 nicht einpacken ist 17 die optimale lösung, aber bei g1 einpacken kanns noch bessere geben...
ich glaub die frage vom gero war wegen dem was auf seite 141 vom skriptum steht, von wegen dass man bei gleicher oberer und unterer schranke bereits das ergebnis gefunden hat, und ich glaub das gilt nur dann wenn wir das problem noch nicht in teilprobleme aufgeteilt haben, also mehr oder weniger noch in der wurzel sind.
weiss schon wie es gemeint ist
thnx euch 2en und viel Glück heut :thumb:
tschurlo
30-05-2003, 18:55
So, ich werf jetzt ganz frech eine bereits beantwortete Frage nochmal auf, weil ich es noch immer nicht ganz verstehe:
Weil dieser Knoten eine lokale Oberschranke hat, die unter der zu diesem Zeitpunkt aktuellen globalen Unterschranke liegt...
Der Satz verwirrt mich ein bisserl... die lokale Oberschranke ist 15, was ist die globale Unterschranke? Auch 15, weil es noch keine kleinere gibt? Aber dann waeren die beiden ja gleich...???
Ausführlicher: Zu dem Zeitpunkt, zu dem wir {G2,G3} untersuchen, wissen wir bereits, dass die optimale Lösung einen Wert von ÜBER 15 hat, es hat daher keinen Sinn, einen Baumast weiter zu verfolgen, dessen beste Lösung einen Wert von HÖCHSTENS 15 haben wird.
Das wissen wir daher, dass wir fuer eine obere Schranke bereits mal den Wert 23 hatten?
lg
Was ich mich frage ist, wie genau die Konstruktion des Baumes erfolgt ? :confused:
Ich fange an mim ersten Knoten, noch nix eingepackt. Obere Schranke -> 23, untere 15 -> aufteilen. Links mit G2, rechts ohne -> Schranken ausrechnen -> weiterrechnen .. da bei G2 ohne G3 eine obere & untere Schranke von 19 rauskommt kann ich den rechten Ast killen. weil 19/19 auch im nächsten Knoten ist, kann ich die anderen Äste auch killen und komme so auf G1, G2 & G4 ... richtig so ?
:confused: bin mir noch nicht ganz sicher, ob ich das richtig verstanden habe ... :confused:
Greetz, :ahhh: Freeek
Unic0der
31-05-2003, 19:19
:confused: :confused: :confused:
Ich dachte mir als ich das Beispiel gesehen habe: Lässig - Branch and Bound - kann ich eh.
Naja, ich habs jetzt nicht zambracht, weil sich hier die Vorgehensweise anscheinend sehr von der im Skriptum beschriebenen unterscheiden dürfte.
Könnte vielleicht jemand so nett sein eine kleine Anleitung zu posten, sodass ich das Beispiel hinkriege ? Ich brauch ja nicht gleich eine komplette Erklärung von Branch und Bound ;) ... :thumb:
Bitte! :D :D :) :D :D :) :D :D
Millencolin
01-06-2003, 21:34
:confused: :confused: :confused:
... Könnte vielleicht jemand so nett sein eine kleine Anleitung zu posten, sodass ich das Beispiel hinkriege ?... ich häng da auch gerad!! hat zuerst so einfach ausgeschat, und dann ..... http://hades.gothic.at/iforum/images/smilies/wallbash.gif
ricotool
01-06-2003, 23:43
wieso muss man bei knoten {+g2,-g3,+g1} weitermachen? es wird ja eine lokale obere schranke von O=19 für diesen knoten berechnet und vorher (bei knoten {+g2, -g3}) kam eine neue globale untere schranke von U=19 heraus. :confused:
ricotool
15-06-2003, 13:59
hat niemand eine ahnung?
weiß nicht.... mich beschäftigt das beispiel immer noch, hab aber wohl das verfahren nicht ganz verstanden... ergo: komm nicht drauf
ich weiß nicht, ob das sonst noch jemanden intressiert, aber spätestens kurz vor der VO-prüfg. wird das ganze wieder wichtiger, schätze ich. hatte eigentlich auf das rep in dieser frage gesetzt, doch das ist ja einen sehr plötzlichen (und grausamen) tod gestorben.
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.