[Python] - Pathfinding gitt en liste over lovlige koordinater

[Yumekui]

Gitt en liste over lovlige heltallkoordinater samt nåværende posisjon, hvordan kan en finne den (en av de) korteste sekvensen av steg for å nå et gitt heltallkoordinat - Hvor ett steg er definert som en forflytning (+1 eller -1) i enten x-retning eller y-retning?

[etse]

Ja. Letteste er å se på det som en graf og søke gjennom grafen etter riktig vei.

Her kommer "Dybde først søk", "Bredde først søk", "Dijkstras algoritme" og "A* Algoritmen" veldig godt med. Om kartet ditt ikke er så veldig stort kan bredde først søk være det du trenger.

For en stund tilbake skrev jeg en introduksjons-guide til grafteori på freakforum som du kan ta en titt på; der tar jeg for meg Dybde først søk og bredde først søk, med python.

 

http://freak.no/forum/showthread.php?t=189698

 

Om du har et veldig stort kart, så vil du få problemer med at Bredde først søk tar alt for mye minne; og for lang tid på å finne korteste vei. I så fall må du kanskje se på A* algoritmen som bygger på bredde først søk og Dijkstras algoritme.

[Yumekui]

 

Det er viktig å skille mellom en rettetede og urettetede grafer; rettetede grafer er grafer hvor man kan alltid kan gå begge veier over en kant som kobler sammen 2 noder, mens i en urettet graf kan man kun gå over en kant den veien pilen viser.

 

Er dette skrivefeil? Bildet under med beskrivelse ser ut til å mene det motsatte.

[etse]

 

Det er viktig å skille mellom en rettetede og urettetede grafer; rettetede grafer er grafer hvor man kan alltid kan gå begge veier over en kant som kobler sammen 2 noder, mens i en urettet graf kan man kun gå over en kant den veien pilen viser.

 

Er dette skrivefeil? Bildet under med beskrivelse ser ut til å mene det motsatte.

Du har helt rett. Dette er et av problemene med frakforum - jeg kan ikke endre på innlegget og fikse et par av slurvefeilene som er i posten (for det meste noen enkle skrivefeil).

[Terrasque]

Min favoritt-blogpost om emnet : Solving mazes using Python: Simple recursivity and A* search

 

Har også en lignende i bookmarks: Solving Game Entity Navigation Using Python