852 Kurseinheit 2 Stepping-Stone-Methode

Edit: so noch mal, diesmal die richtige Antwort *sfg*

Eine Wurzel ist im Endeffekt eine Quelle eines gerichteten Graphen, also ein Knoten, von dem nur Pfeile ausgehen. Am Anfang malst Du am besten den Graphen immer neben das Tableau und streichst dann die entsprechende gefundene Kante raus. Dann siehst Du sofort die beiden neu entstehenden Teilbäume, ohne lange überlegen zu müssen.

MfG
Thomas

Thomas W. schrieb:

edit: so noch mal, diesmal die richtige Antwort *sfg*

Eine Wurzel ist im Endeffekt eine Quelle eines gerichteten Graphen, also ein Knoten, von dem nur Pfeile ausgehen. Am Anfang malst Du am besten den Graphen immer neben das Tableau und streichst dann die entsprechende gefundene Kante raus. Dann siehst Du sofort die beiden neu entstehenden Teilbäume, ohne lange überlegen zu müssen.

MfG
Thomas

Zum Vergrößern anklicken....

Hallo Thomas,
was taete ich eigentlich ohne Dich?

Gut, wenn ich den Graphen daneben schreibe, erkenne ich es wohl. Kann ich es auch direkt am Tableau sehen? Oder ist das nur fuer logisch Denkende moeglich (ich scheine nicht mehr dazu zu gehoeren).
Danke,
Ulrike

Cobra schrieb:

Hallo Thomas,
was taete ich eigentlich ohne Dich?

Zum Vergrößern anklicken....

da sag ich doch einfach nur Danke für die Blumen

Cobra schrieb:

Gut, wenn ich den Graphen daneben schreibe, erkenne ich es wohl. Kann ich es auch direkt am Tableau sehen? Oder ist das nur fuer logisch Denkende moeglich (ich scheine nicht mehr dazu zu gehoeren).
Danke,
Ulrike

Zum Vergrößern anklicken....

Im Prinzip schon. Die gefundene Zelle mit den negativen reduzierten Kosten soll ja Null werden. Also musst beispielsweise in der Zeile/spalte was subtrahieren/addieren, nämlich genau den Wert der reduzierten Kosten (je nach Potentialen). Meist steht aber in der Zeile/Spalte noch in einer andern Zelle der Wert red. Kosten=0. Damit die erhalten bleiben, musst Du dann in der anderen Richtung wieder was ändern usw. Das kann man eigentlich schlecht erklären, das müsste man mal vorgemacht bekommen.

Wichtig ist halt, die red. Kosten der Zelle auf Null bringen, ohne das in anderen Spalten/Zeilen sich die red. Kosten von Null ändern, außer bei der, die aus der Basis fliegt.

Ich glaub, das versteht jetzt eh niemand.

Thomas W. schrieb:

Ich glaub, das versteht jetzt eh niemand.

Zum Vergrößern anklicken....

zumindest ich verstehe es nicht. Ich male mir einfach den Baum auf...
Danke,
Ulrike

Cobra schrieb:

In den Abbildungen (z.B. 6.8 auf Seite 27) ist mir klar wie man Th und Tk bestimmt und wie man die Potentialaenderung durchfuehrt. Auf Seite 34 ff ist es mir voellig unklar,wie man das macht.

Zum Vergrößern anklicken....

Na ja, scheint nicht voellig klar zu sein. Und zwar:
Auf Seite 28 steht "...entsteht durch die Elimination des Pfeils <p,q>=<1,4> ... die Teilbaeume T1 und T4'..."
Am Ende der Seite und Anfang Seite 29 steht dann '...neuen Basispfeil <h,k> ... Teilbaumes Th oder man subtrahiert chk_quer .... des Teilbaumes Tk'.
Auf Seite 30 wird <2,1> als neuer Basispfeil ausgewaehlt. Nur hier spricht man dann von '... dargestellte Teilbaeume T3' und T2 und von 'Die Knotenpotentiale werden ..., d.h.am Teilbaum T3' aktualisiert'.
Auf Seite 34 steht dann wieder etwas von '...neuen Basispfeil <h,k>...' und '...Teilbaum Th und .... Tk'.
Auf Seite 37 wird die gleiche Berechnung anhand des Tableaus erklaert wie auf Seite 30 anhand des Basisbaums. Nur hier wird der Teilbaum an den die Potentialaenderung vorgenommen mit Tk=T1' bezeichnet. Oben wurde er als T3' bezeichnet.
Also, wonach richtet sich die Bezeichnung der Teilbaeume? An dem zu eliminierenden Pfeil <p,q> oder an dem neuen Basispfeil <h,k>?
Sorry, aber ich bin mal wieder total irritiert.
Gruss,
Ulrike

Ach nicht irritieren lassen.

Auf Seite 28 wurde der Pfeil <1;4'> entfernt und die beiden Teilbäume T1 und T4' genannt. Auf Seite 30 wurde der Pfeil <2;3'> entfernt und die Teilbäume T2 und T3' genannt. Die Teilbäume wurden also einfach mit der Nummer der Knoten bezeichnet, die "auseinandergerissen" wurden. dabei ist k der "empfangende" Knoten, also der Nachfrager, und h ist der "liefernde" Knoten, also der Anbieter.

Ab Seite 34 wurde dann tatsächlich das neue Basisfeld mit (h,k) bezeichnet.

Im Endeffekt ist die Bezeichnung aber ne "Spielerei" und ich würde nicht zu intensiv drüber nachgrübeln. Wichtig ist das Verfahren an sich.

MfG
Thomas

Ulrike,

die Teilbäume entstehen durch den Pfeil, der entfernt wird, somit ist dieser zu berücksichtigen.
Wichtig ist schon, dass du weißt, in welchem Baum du die Knotenpotentiale änderst, da im Teilbaum h die reduzierten Kosten addiert und im Teilbaum k subtrahiert werden.

Gruß,

Angela

Die Diskussion ist zwar schon eine weile her, aber ich stehe vor demselben Problem wie ich auf die Teilbume komm.Immer danebenmalen ist ja hilfreich aber evtl kann mir das nochmal jemand erklären? Ich steh total auf dem Schlauch und häng bei Seite 33 fest.

der letzte Beitrag hier ist zwar schon eine Weile her, ich geb aber trotzdem auch mal noch einen kleinen Kommentar dazu ab.

Meine Variante ohne Zeichnung und Ermittlung von Teilbäumen ist folgende (ist allerdings ein wenig aufwändiger):
Im Algorithmus steht, dass man „uh“ oder „uk“ durch Addition bzw. Subtraktion ermittelt. Wenn man eins der beiden ermittelt hat, kann man die anderen „ui“ und „uj“ mittels der Restriktion (für die Stellen an denen die Basislösungen stehen) red. Kosten = 0 = cij – ui + uj berechnen. Ich geh dann jedes „ui“ oder „uj“ so durch wie zu Beginn bei der Aufstellung der „ui“ und „uj“.

Gruss
Mo