A* und Nächster Nachbar Verfahren

Eric,

Nearest Neighbor von A beginnend ergibt Rundreise ADCBEA, mit Länge 47.

Es gilt: f= g + h, mit:
g:bereits gegangen, also am Startpunkt A gleich 0
h: 0,8 * "Nearest Neighbor", von A, also 47*0,8 = 37,6

Analog für den Rest.

Grüße
Martin

super schnelle Antwort und ich habe es gleich gerafft.

Vielen Dank und viele Grüße

Eric

leider habe ich noch weitere Fragen. Wie kommt man bei AB auf 41,6 bzw. AC auf 41,8 usw.?

Mit steht einer auf dem Schlauch.

Viele Grüße
Sandra

besser spät als nie:
zur Expansion AB: nach Aufnahme des Ortes B ergibt sich eine verbleibende "nächste Nachbar"folge von
B-->C-->D-->E-->A mit der Gesamtlänge von 37. Die Schätzfunktion ergibt dann 37*0,8 = 29,6 mit einer Gesamtbewertungsfunktion f(x) = 29,6 + 12 (-->Distanz A-->B) = 41,6
Analog dann Expansion AC, AD und AE. Die Expansion mit minimaler Bewertungsfunktion wird weiter betrachtet....

MfG
Viktor

viktor schrieb:

...
zur Expansion AB: nach Aufnahme des Ortes B ergibt sich eine verbleibende "nächste Nachbar"folge von
B-->C-->D-->A mit der Gesamtlänge von 37. ...

Zum Vergrößern anklicken....

Fehlt da nicht E zwischen D und A?

stimmt

viktor schrieb:

besser spät als nie:
zur Expansion AB: nach Aufnahme des Ortes B ergibt sich eine verbleibende "nächste Nachbar"folge von
B-->C-->D-->E-->A mit der Gesamtlänge von 37. Die Schätzfunktion ergibt dann 37*0,8 = 29,6 mit einer Gesamtbewertungsfunktion f(x) = 29,6 + 12 (-->Distanz A-->B) = 41,6
Analog dann Expansion AC, AD und AE. Die Expansion mit minimaler Bewertungsfunktion wird weiter betrachtet....

MfG
Viktor

Zum Vergrößern anklicken....

Hallo,

und warum wird in derselben Aufgabe (KE 3, S. 25) sowohl der Knoten ADE als auch der Knoten ADC weiterverzweigt?
Man sieht doch, daß der kleinste f(k)-Wert der des Knotens ADE ist (38.8 (ADE) < 40.2 (ADC) < 44.2 (ADB) und dementsprechend ADE weiter zu verzweigen ist.

Sollte die Antwort darauf sein, daß eine der beiden Verzweigungen von ADC, nämlich ADCB (41.2) denselben f(k)-Wert wie eine der Verzweigungen von ADE, nämlich ADEB (41.2) ergibt?
Das weiß man aber vorher nicht.
Wenn man es also vorher nicht weiß und deswegen die beiden Knoten (ADC und ADE) weiterverzweigt, warum dann nicht auch den Knoten ADB?

Gruß.

Es wird immer der Knoten verzweigt, der aktuell den niedrigsten Zielfunktionswert von allen bisher untersuchten hat. Von den drei Verzweigungen ADC, ADB und ADE hat letzterer den niedrigsten Wert mit 38,8, weshalb dort weiter verzweigt wird. Die sich daraus ergebenden Wege ADEB und ADEC haben die beiden Zielfunktionswerte 41,2 und 43,6 Vergleicht man die Werte mit den bisher untersuchten, stellt man fest, dass ADC mit 40,2 einen niedrigeren Wert hat. Deshalb wird zunächst ADC wieder verzweigt, um möglicherweise eine optimalere Lösung zu finden!

vg,
viktor

und danke.

Bei der Verzweigung von ADC (40,2) ergeben sich ja dann die Wege ADCB (41,2) und ADCE (44,2).
Müßte man dann nicht neben dem Knoten des erstgenannten Zweiges, also ADEB (41,2), nicht auch den Knoten des zweitgenannten Zweiges, also ADCB (41,2) weiterverzweigen und dürfte man nicht erst danach vergleichen, welcher der beiden Wege besser ist?
Oder führt 41,2 (ADCB) = 41,2 (ADEB) dazu, daß wieder eine Ebene höher gegangen, dort verglichen und dann doch ADE (38,8) usw. gewählt wird, weil dies der niedrigste Zielfunktionswert der Ebene ist?

Mir fehlt die Quintessenz ... Man weiß doch immer erst am Ende eines Weges, ob er wirklich einen höheren Zielfunktionswert hat, als die anderen Wege? Oder ist das zu grob formuliert?

Gruß.

Wie sieht es mit dem Expansionspfad in der 3. und 4. Ebene aus?

viktor schrieb:

besser spät als nie:
zur Expansion AB: nach Aufnahme des Ortes B ergibt sich eine verbleibende "nächste Nachbar"folge von
B-->C-->D-->E-->A mit der Gesamtlänge von 37. Die Schätzfunktion ergibt dann 37*0,8 = 29,6 mit einer Gesamtbewertungsfunktion f(x) = 29,6 + 12 (-->Distanz A-->B) = 41,6
Analog dann Expansion AC, AD und AE. Die Expansion mit minimaler Bewertungsfunktion wird weiter betrachtet....

MfG
Viktor

Zum Vergrößern anklicken....

Guten Morgen,
und das nächste Fragezeichen.
ich denke, ich verstehe alles außer: wie erhalten ich die Gesamtlänge von 37 ???
B--C--D--E--A
ich fände es logisch, wenn man bei B weiter macht, dann erhalte ich aber
5+9+12+12=38
oder ich bleibe in der ersten Zeile und ziehe das B einfach von meinen 47 ab --> 35

🙁😕😡🤔

kann bitte jemand helfen? Wahrscheinlich ist es wieder total einfach.

Wie sieht der Expansionspfad in der 3. und 4. Ebene aus?

hat sich erledigt, habs selbst raus gefunden ...

kann mir jemand erklären wie man auf h(k) in den Ebenen 3-5 kommt?