lično nisam video da se takav algoritam negde i pominje, a ja bih isto po logici stvari rekao da ne postoji.

tj, čak i da postoji, ne bi bio brži od najbržeg algoritma koji računa single source shortest path, a nusproizvod bi mu verovatno opet bio minimalno rastojanje između početnog i svakog drugog čvora grafa.

razlog je što uvek moraš biti siguran da između tvojih čvorova A i B, ne postoji možda kraći put preko čvora C, tako da ti treba i dužina puta od A do C..

Ima.
A*( A star ).
Ima toga na netu na tone.

ček, ček,
ne razumijem najbolje zašto ne postoji! Pa u svakom grafu
možeš da utvrdiš da li između bilo koja dva čvora postoji put!
Nađeš sve puteve između dva čvora i odabereš najkraći od njih!

Ako je to ono o čemu pričate... a ako ne explain please

Pa po tebi bi trebalo pustiti bektrek da uutvrdi svako rastojanje izmedju dva cvora, a to spooooro, a mene je zanimalo da li postoji neki brzi algoritam ( btw. nisam jos pogledao onaj A*, pogledacu ga cim budem imao malo vremena)

ok,
ali ipak to što je algoritam spor ne znači da ne postoji tj.
da ne može da se nađe rješenje!!!

Nismo se razumjeli!

Pazi, sve moze da se resi bektrekom. Pitanje je koliko je to efikasno (neefikasno).

Može da se reši bektrekom. To stoji. Naravno da se baktrek guši povećanjem broja čvorova grafa (a želimo odziv u nekom realnom vremenu...) pa je potrebno naći koje su dobre varijante za sečenje bektreka ili koje su alternative po algoritmima koji su drugačije zasnovani.

Nisam se snašao u traženju algoritma A* (DDMM tvrdi da toga na netu na tone - koja je ključna reč?) a bilo bi mi drago da se odavde može doći do neke korisne i zanimljive informacije u vezi teme.

Cini mi se da je Dijkstrin algortima medju najbrzima (ako ne i najbrzi), ne razumem zasto neces bas njega da primenis. Inace on u originalnoj varijanti ne pronalazi najkrace puteve izmedju jednog i svih ostalih cvorova vec samo najkrace puteve izmedju pocetnog i krajnjeg cvora, i izmedju pocetnog i svih drugih cvorova koji pripadaju prvom putu (sto je sasvim logicno i neminovno ako se zeli tvrditi da je pronadjen najkraci put).

http://en.wikipedia.org/wiki/A_Star_Search_Algorithm

Na kraju imas i par linkova sa opsirnijim objasnjenjima.

Hvala. Another A* Pathfinding for Beginners mi je pomogao najviše.
Menhetn heuristika je jednostavna, jedino što ne vidim kako bi se mogla primeniti pri većem broju čvorova... kao na primeru Justin Heyes-Jones' A* algorithm tutorial gde je predstavljen Nilsonov heuristički algoritam - koji ću skontati nekom drugom prilikom...

Pa nisam ni rekao da necu da ga koristim, samo me je interesovalo da li postoji neki drugi.

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..

Prvo Dijsktrin nije najbrzi nego najsporiji algoritam, ali je zato "najprecizniji". Best-First-Search je manje "precizan" (ne vraca najbolji put) ali je brzi (dosta).
Kombinacijom ta dva algoritma dobijen je a*(A-star) algoritam.
a* (tj. njegove modifikacije) se danas koristi u vecini slucajeva kada je potrebno u real time-u naci put izmedju dve tacke (Vezano za drugu temu: najcesca implementacija a* je iz rekurzivne prebacena u iterativnu).
Definisuci (i modifikujuci) skupocu i heuristiku moguce je naci najbolji put (jer najkraci nije uvek sto i najbolji) sto kod Dijsktre nije moguce