Znajdowanie najkrótszej drogi

[Qbi Wan]

Hejka wszystkim.

Czy jeżeli mam planszę złożoną z kwadratów, i występują na niej 3 rodzaje dróg: piaszczysta, asfaltowa i autostrada i przydzieliłbym im wartość odpowiednio 3; 2 i 1 punktów to byłbym w stanie nakazać systemowi odszukanie takiej drogi z pkt A do pkt B by na koniec drogi zgromadził jak najmniej punktów??

 

(Temat poprawiony, dzięki za uwagę ;P)

[Jakim]

Oczywiście. Przestudiuj algorytm A*.

 

PS ZnajdOwanie, razi ten błąd.

[Platyna]

Lepiej algorytm Dijkstry jeśli zależy Ci na stuprocentowej poprawności. A* jest heurystyczny.

[adam014]

Link do implementacji Dijkstry w GM : https://forum.gmclan.org/index.php?showtopic=13186

[Qbi Wan]

A czy da się też znaleźć tymi sposobami najszybszą drogę? Jeżeli tak to który lepszy? Czy ten drugi (ten gotowy) jest w wersji na najnowszy GM?

[Platyna]

A czy da się też znaleźć tymi sposobami najszybszą drogę?

A o co wcześniej pytałeś jak nie o najszybszą?

[Qbi Wan]

Bo temat zatytułowałem "Znajdowanie najkrótszej drogi", a w sumie chodziło mi o najszybszą ;P Istotna różnica, wolałem uściślić.

[Sernat]

t ~ s

[Jakim]

Przecież podał współczynniki prędkości dla różnych nawierzchni, co dyskwalifikuje Twoje ukryte założenie o stałej prędkości.

[Sernat]

Ciekawe :rolleyes: ...

 

Gdzie Ty widzisz współczynniki prędkości, jeśli k(autostrada) = 1, a k(piasek) = 3.

 

t ~ s