[csidc:2003] - Re: MilanSt. by "Milan Stanojevic" <milanst@ptt.yu>

    Formule nisam ja vadio iz glave, one su iz "Introduction to Algorithms", prema tome sigurno su tacne. Mogu da ti posaljem celu analizu, ali nema nikakve svrhe. 

Razmisli sta pises. E+NlogN je manje od (N+E)logN. Mozda tvoja anliza i jeste tacna ali onda se definitvno odnosi na ocajnu implementaciju ( konstantni clan je duplo veci ). Sad me zanima ta analiza, ne verujem da bi u literaturi napravili takav propust. Mozda ona uzima u obzir jos nesto...Mozes da je posaljes ( bar licno meni ako neces na listu ). 

Nigde nemas nikakav konstantni clan. Ta knjiga je referentna za algoritme, koristi se vec vise od 10 godina i tesko da ima ocigledne greske. Evo analize (prepricano iz knjige)
Samo vreme izvrsavanja Dajsktrinog algoritma zavisi od implementacije i odrzavanja trenutno nadjenih najkracih puteva. Ako koristis binary heap imas sledecu situaciju. (V broj cvorova, E broj ivica, lg - logaritam za osnovu 2)
Za svaki ExtractMin treba O(lg V), a takvih operacija ima |V|, ukupno vreme je O(V*lgV). U svakom koraku radis i modifikaciju heapa ako za neki cvor nadjes manje rastojanje, sto znaci da moras da ga propagiras kroz heap. Takvih operacija imas |E| a to traje O(E lgV), sve zajedno znaci O ((V+E)*lgV). 
Vreme O(E + V*lgV) moze da se postigne koriscenjem Fibonachi heapa, koji moze uradi DecreaseKey u heap-u (operacija kojom smanjis vrednost elementu i propagiras ga kroz klasicni heap) u O(1) amortizovanom vremenu. Fibonachi heap nisam nikad implementirao, mislim da nije tako jednostavno, ali ne verujem da treba. Obican binary heap ce da ti zavrsi posao. (U javi imas binarno drvo TreeSet, ne znam kako je u C#, mozda vec imaju nesto gotovo).


A zar ti i ne treba rastojanje od jedne tacke (mesta dogodjaja) do vise ostalih (vozila). Onda moras da ides u svim pravcima i da prekines pretragu cim nadjes prvo vozilo.

Procitaj specifikaciju. To bi bila varijanta da je procena na serveru. KLIJENT odredjuje najkrace rastojanje za sebe. Tako smo se dogovorili jos na samom pocetku. Nema govora o trazenju vozila. Drugo, ne kreces pretragu od mesta dogadjaja nego od svoje pozicije ( GPS ), pa do mesta intervencije. 

Izvinjavam se za to. A sta je klijent? I zasto sa klijenta (jel to zbog teme projekta, jer bi sve mnogo lakse bilo da je na serveru).

A koliko to cvorova imas pa je problem? Preko milion? 

    Jos uvek nije utvrdjeno da li je problem. Moze da bude. Pre toga mora se prebaciti mapa u graf. To je ogroman posao i bas mi treba jedan pametnjakovic, bas toliko pametan ko ti, da se pozabavi tim delom projekta. Vidim da si bas zainteresovan... Pa i da ima ispod 100 cvorova, to nije nikakvo opravdanje. Uvek treba da tezis najboljoj implementaciji.

Pitam za broj cvorova, jer Dajkstra za mali broj cvorova radi trenutno. Doduse, sad zavisi sta je klijent, ali do par hiljada cvorova, uz uslov da klijent ima memoriju za to, sve bi trebalo da bude trenutno.


Bitno je koje vreme ti je potrebno za recimo proveru da li su dva cvora susedna. 

    Za sada najmanje moguce.

Dobro, posto su u pitanju raskrsnice i ulice (pretpostavljam), svaki cvor nema puno suseda, tako da liste susednosti vrse posao.


Pretpostavljam da pod procenom podrazumevas trenutno nadjena najkraca rastojanja. Tu nema sta da se poboslja, zaista ne znam sta mozes da uradis a da dobijes dobre rezultate. Imas heap i radis ExtractMin i zatim uradis update po susednim cvorovima, a njih nema vise od 5-6. To je sve vrlo brzo.

   Update po susednim cvorovima nije problem upravo zbog nacina na koji se cuvaju info... o susedima. To sam vec negde pisala. Kad kazes ExtractMin nadam se da mislis na dohvatanje najbolje procene. E to hocu da poboljsam. Poboljsanje moze, a i ne mora da dovede do promene koriscene strukture. Ako menjas strukturu, heap je OK, ali kao sto rekoh nije implementiran ! Samo je citava ta prica izolovana od ostatka koda bas zbog promena. 

Ovo nisam shvatio. ExtractMin je operacija nad heapom (podrazumevam takvu implementaciju) kojom uzimas cvor sa trenutnim najmanjim nadjenim rastojanjem od pocetne tacke (to je onda i konacno najmanje rastojanje). Sta tu hoces da poboljsas? To ne kapiram.


Jedna heuristika je da uzmes pravougaonik koji obuhvata pocetnu i kranju tacku, malo ga prosiris (verujem da je stotinak metara po stranici i vise nego dovoljno) i pri pustanju Dajkstre koristis samo te tacke.

 Jedna od mojih ideja je slicna, samo nije pravougaonik nego kruzni isecak sa centrom na polaznom mestu ugla koji zavisi od rastojanja. Ipak, mislim da nemodifikovano nece dati savrsene rezultate. Dobre hoce, ali veruj mi, mogu da ti pronadjem slucajeve gde nece raditi. Algoritam mora da radi za svaki par tacaka. 

Ideja je da uzmes neku povrsinu koja obuhvata obe tacke, dovoljno siroko da ne izgubis najkraci put, ali i dovoljno usko da nemas previse tacaka. Neka elipsa kojoj je duz izmedju dve tacka osa ili tako nesto. Sigurno neces da zaobilazis puno po gradu (reda kilometara).

Bar me jedna stvar raduje. Ti si vrlo uporan u svojim tvrdnjama da nece biti problema sa vecim brojem cvorova. Po prvi put sam na tvojoj strani ali zasto ti toliko smeta sto razmisljam o potencijalnim problemima ? I ja mislim da ce raditi OK ( bar se nadam ) ali ako imamo bolje resenje ne vidim zasto da ga ne bi  usvojili. 

Pozdrav, Andjelija

Nisam znao da se stvar radi na klijentu. Mislio sam da je u pitanju PC, a tu nema problema sa vecim brojem cvorova jer Dajkstrin algoritam radi vrlo brzo (probao sam mali milion puta, verujte mi). Sa klijentom ne znam kako stvari stoje.

Uglavnom, ja sam samo posmatrac i vi radite kako mislite, ja sam mislio samo da dam par sugestija ako sam nesto vec radio (a ovo oko grafova jesam).

            Pozdrav,
                    Milan