Citat:
DDMM:Ima.
A*( A star ).
Ima toga na netu na tone.
kasnim malo, ali..
tačno, delimično sam zaboravio na A*, ali ga verovatno nisam imao u vidu zato što je to više heuristika nego klasičan algoritam, tj oslanja se na neka svojstva grafa da bi garantovao uspeh. u opštem slučaju se nije pokazao tako dobro..
recimo, u prostom lavirintu sa malo prepreka, deluje baš impresivno, ali u nekim komplikovanijim postavkama se vrlo lako može desiti da i A* mora da pregleda većinu, ili čak sve puteve u grafu da bi bio siguran da je nađeni put baš najkraći.. (ima primera, a ako ne možete da ih nađete, recite, potražiću).
e sad, kada se to desi, onda A* vrši isti broj provera kao i dijkstra, ali pošto on nije predviđen za to, na kraju ispadne sporiji od dijkstre koji je optimizovan da radi tako kako radi (npr, A* mora da koristi neke kolekcije koje koštaju ili pri ubacivanju, ili pri traženju najbolje ocenjenog kandidata, ili pri nekoj trećoj operaciji).
e sada, to je bilo čisto sa teoriske strane. u stvarnosti, kada rešavamo neki problem, uglavnom znamo i kakav graf možemo da očekujemo (slabo povezan, razređen, sa puno prepreka, itd), tako da A* definitivno ima primena..