[pchero]

HI
,
ich wollte mal fragen , wie man in dem Bild (Siehe Anlage), die entfernung und den schnellsten Weg berechnet, wobei X ein Hinderniss ist?

MFG

Angehängte Miniaturbilder

• 

Dieser Beitrag wurde von pchero bearbeitet: 19. November 2006 - 19:21

[telemail]

Zitat (pchero: 19.11.2006, 19:19)

HI
,
ich wollte mal fragen , wie man in dem Bild (Siehe Anlage), die entfernung und den schnellsten Weg berechnet, wobei X ein Hinderniss ist?

MFG

Ich verstehe nicht, was es da zum Berechnen gibt. Einfach alle möglichen Wege ausfindig machen und dann abzählen, welcher der Kürzeste ist, oder?

Gruß tetemail

[pchero]

hmm und wie muss man sowas schreiben hätte da zwar so ein paar ansätze aber ich weiß nicht wie man jetzt alle wege durchgehen soll man müsste doch erstmal alle kruzungen durchnummerieren oder ?

MFG

[MNG]

Berechne einfach für jedes begehbare Feld die Distanz zum Startfeld. Dazu schreibst du eine rekursive Funktion die wie folgt arbeitet:
Die Distanz vom aktuellen Feld zu A ist:
- 0, falls das aktuelle Feld A ist
- das Minimum der Distanzen aller benachbarten Felder, die kein X und noch nicht bewertet sind
- unendlich für alle anderen Fälle.
Diese Funktion bekommt als Parameter die Indizes des aktuellen Feldes. Aufgerufen wird sie mit
den Koordinaten vom Feld B.
Warum willst du das eigentlich in PHP berechnen?

[Rika]

Naja, wenn du nach Dijkstra vorgehst, dann ersparst du dir unnötige Aktualisierungen und kennst nachher auch noch den Weg.

Für große Labyrinthe würde man den Flooding-Algorithmus nehmen.

[pchero]

ähm was ist denn ein Flooding Algorithmus ? bin erst in der 10 klasse

MFG

[Witi]

Dann wollen dir mal mit ein wenig wikipedia-Lektüre aushelfen
http://de.wikipedia....ing-Algorithmus
http://en.wikipedia....stras_Algorithm

[pchero]

hmm das mit dem Flooding dachte ich mir auch schon so, bloß ich habe gehofft das sowas auch anders geht anstatt alle wege auszuprobieren^^

MFG

[Rika]

Oder halt der A*-Algorithmus, wenn du sehr viel Wegemöglichkeiten hast.

P.S.: Nein, dieser Flooding-Algorithmus ist nicht gemeint. Ich bezog mich auf den Flooding-Algorithmus für das Traveling-Salesman-Problem, d.h. wahlloses Wechseln zwischen topologisch benachbarten Wegstrecken mit paralleler Senkung der obersten Schranke.

Dieser Beitrag wurde von Rika bearbeitet: 20. November 2006 - 19:41