[csidc:2003] - MilanSt. by "Savic Andjelija" <andjas@EUnet.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 ). 


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. 

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.

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

    Za sada najmanje moguce.

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. 

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. 

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