Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Minimalno rastojanje izmedju dva cvora!

[es] :: Art of Programming :: Minimalno rastojanje izmedju dva cvora!

[ Pregleda: 5790 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.



Profil

icon Minimalno rastojanje izmedju dva cvora!18.04.2004. u 14:13 - pre 196 meseci
Da li postoji neki algoritam koji pronalazi minimalno rstojanje izmedju dva cvora u grafu ? Znaci ne izmedju jednog i svih ostalih (Dijsktrin), vec samo izmedju neka dva. (u stvari, meni se cini i logicno mi izgleda da ne postoji, ali eto,cisto da pitam)
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
195.252.85.*

Sajt: localhost


+4 Profil

icon Re: Minimalno rastojanje izmedju dva cvora!18.04.2004. u 21:16 - pre 196 meseci
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..
 
Odgovor na temu

DDMM
Dejan D. M. Milosavljevic
Danguba
Gajba, ali ne piva.

Član broj: 2544
Poruke: 89
*.sbb.co.yu

Sajt: www.ddmrm.com


Profil

icon Re: Minimalno rastojanje izmedju dva cvora!07.05.2004. u 12:22 - pre 195 meseci
Ima.
A*( A star ).
Ima toga na netu na tone.

X
 
Odgovor na temu

antix

Član broj: 8388
Poruke: 265
*.mobtel.co.yu

Jabber: antix@elitesecurity.org


Profil

icon Re: Minimalno rastojanje izmedju dva cvora!18.05.2004. u 01:40 - pre 195 meseci
č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
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.



Profil

icon Re: Minimalno rastojanje izmedju dva cvora!18.05.2004. u 10:59 - pre 195 meseci
Citat:
antix:
č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)
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

antix

Član broj: 8388
Poruke: 265
*.mobtel.co.yu

Jabber: antix@elitesecurity.org


Profil

icon Re: Minimalno rastojanje izmedju dva cvora!18.05.2004. u 16:37 - pre 195 meseci
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!
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.



Profil

icon Re: Minimalno rastojanje izmedju dva cvora!18.05.2004. u 22:58 - pre 195 meseci
Pazi, sve moze da se resi bektrekom. Pitanje je koliko je to efikasno (neefikasno).
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
*.dialup.neobee.net.

Sajt: www.novikorisnik.net


+5 Profil

icon Re: Minimalno rastojanje izmedju dva cvora!18.05.2004. u 23:16 - pre 195 meseci
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.
 
Odgovor na temu

_owl_

Član broj: 318
Poruke: 1042
*.verat.net



+3 Profil

icon Re: Minimalno rastojanje izmedju dva cvora!19.05.2004. u 01:11 - pre 195 meseci
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).
Owl
 
Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.reverse.qsc.de



+1 Profil

icon Re: Minimalno rastojanje izmedju dva cvora!19.05.2004. u 08:33 - pre 195 meseci
Citat:

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


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

Na kraju imas i par linkova sa opsirnijim objasnjenjima.
 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
194.247.222.*

Sajt: www.novikorisnik.net


+5 Profil

icon Re: Minimalno rastojanje izmedju dva cvora!19.05.2004. u 09:36 - pre 195 meseci
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...
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.



Profil

icon Re: Minimalno rastojanje izmedju dva cvora!19.05.2004. u 10:23 - pre 195 meseci
Citat:
_owl_:
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).



Pa nisam ni rekao da necu da ga koristim, samo me je interesovalo da li postoji neki drugi.
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
195.252.85.*

Sajt: localhost


+4 Profil

icon Re: Minimalno rastojanje izmedju dva cvora!02.06.2004. u 07:34 - pre 194 meseci
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..
 
Odgovor na temu

masetrt
Marko Djurovic
Programer, Omni-Explorer
Beograd

Član broj: 3129
Poruke: 228
*.nat-pool.bgd.sbb.co.yu

Sajt: www.vast.com


+2 Profil

icon Re: Minimalno rastojanje izmedju dva cvora!11.08.2004. u 10:08 - pre 192 meseci
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
His majesty Grand Duke of Shumadija and Western Pomoravlje
 
Odgovor na temu

[es] :: Art of Programming :: Minimalno rastojanje izmedju dva cvora!

[ Pregleda: 5790 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.