Iterationsfrage (kürzester Weg) |
| 29.10.2008, 21:50 | Iterationsfrage | Auf diesen Beitrag antworten » |
| Iterationsfrage (kürzester Weg) ich muss hier den kürzesten Weg von P1 zu P7 suchen. Ich fange an: l*(p1)=0, alle anderen Längen (p2, p3 etc.) setze ich T 1. Schritt: p=p5, Nachbarn von p1 sind p2, p3, p4, p5: l(p2)=min(T, 0+3)=3 l(p3)=min(T, 0+6)=6 l(p4)=min(T, 0+10)=10 l(p5)=min(T, 0+1)= 1 1 ist der geringste Wert, also mach ich mit dem weiter (p5). Da ich noch nicht bei p7 bin, folgt eine zweite Iteration: p=p5, Nachbarn sind p4 und p9 l(p4)=min(10, 1+10)=10 l(p9)=min(T, 1+10)=11 10 ist der geringste Wert, also mach ich damit weiter (=p4). Wieder bin ich noch nicht bei p7, also nächste Iteration: p=p4, Nachbarn sind p3, p7, p8, p9 l(p3)=min(6, 10+4)=6 l(p7)=min(T, 10+1)=11 l(p8)=min(T, 10+4)=14 l(p9)=min(11, 10+1)=11 6 (=p3) ist der geringste Wert, also mach ich damit weiter. p=p3, Nachbarn von p3 sind p2, p7 l(p2)=min(3, 6+2)=3 l(p7)=min (11, 6+3)=9 -> ich nehme p2, da geringster Wert (3). Nachbarn sind p6 und p7 l(p6)=min(T, 3+8)=11 l(p7)=min(9, 3+6)=9 So, der geringste Wert ist nun 9, und das ist p7. Eigentlich müsste ich fertig sein, da p7 ja mein Endpunkt sein soll. Wenn ich mir die Grafik anschau, dann ist der kleinste Weg aber p1->p2->p3->p7 (0 nur ACHT!). Was habe ich in der Iteration falsch gemacht? Ich habe überlegt, ob ich z.B. in der letzten Iteration von p2 auch wieder p3 als Nachbar ansehen müsste (obwohl ich ja von p3 erst auf p2 kam!). Dann würde es aufgehen. Wenn ich aber den vorherigen Punkt immer als Nachbar mitbetrachte, dann bleib ich schon am Anfang bei p4 und p5 hängen (das springt dann dauernd hin und her). Wer weiß Rat? 
Danke |
||
| 29.10.2008, 22:44 | kiste | Auf diesen Beitrag antworten » |
Warum schreibst du nicht mal hin welchen Algorithmus du benutzt? Als ob es nur eine Möglichkeit gibt den kürzesten Weg zu finden 
|
||
| 29.10.2008, 23:28 | Iterationsfrage | Auf diesen Beitrag antworten » |
Hm, Dijistra oder so glaube ich. Keine Ahnung, hab von Algorithmen keinen Plan, bin kein Informatiker.
ABER: Habs nun verstanden glaub ich. 
Ich darf als Nachbarn NICHT die Punkte betrachten, die ich davor schon analysiert hab. (Als "einen Punkt analysiert" definiere ich, wenn ich durch die Minimumsuche auf diesen Punkt komme und dessen Nachbarn betrachte.)Allerdings muss ich, wenn ich z.B. von irgendeinem Punkt die Nachbarn betrachte, auch andere, nicht explizit betrachtete Punkte dazunehmen und dann DAVON das Minimum nehmen. D.h., wenn ich bspw. Punkt 5 betrachte, muss ich das Minimun nicht nur unter den Nachbarn suchen, sondern unter allen schon ermittelten Längen (bis auf die Längen zu den Punkten, die schon genau betrachtet wurden). (Sorry für die laienhafte Ausdrucksweise - ich weiß nicht, wie ich es sonst hätte ausdrücken können.
Oder? Zumindest komm ich damit auf die Lösung in diversen Aufgaben. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
