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

    O ( (N+E)log N) ne pali. Mislim da je pre u pitanju O ( E + NlogN ). E je broj svih ivica i do toga dolazi ako koristis liste suseda. Najgori slucaj, "raspakujes" sve cvorove. Po jednoj iteraciji imas slozenost, na primer neko K, neka je to broj izlaznih grana cvora. U zbiru po iteracijama to daje E ( sve izlazne grane, sve grane grafa ). NlogN - iteracija ima N ( najgori slucaj svih cvorova ), a po iteraciji mnozis sa logN sto je slozenost pronalazenja najbolje procene, zapravo pre mislim da je slozenost odrzavanja sortiranosti, posto ako su stvarno sortirani nema slozenosti pretrage, to je prvi element. U svakom slucaju, E jeste reda N pa formula na kraju ispadne dobro. 

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. 

"Ne znam zasto ti je Dajkstrin algoritam problem."
Zato sto moze bolje od tog O (N logN ) ako ne trazis pravolinijski. Zamisli da kreces od sredine mape i treba da dostignes gornji desni ugao. Dijkstra bira uvek cvor sa najboljom procenom. Mozda se ti u pocetku i kreces ka odredistu 
ali to ce vrlo brzo prestati, jer se tako udaljavas od izvora, procena tih cvorova je sve losija sto su dalje i ispituju se drugi, blizi cvorovi sto te usporava. Zasto bi ispitivao cvorove koji te udaljavaju od odredista ? Zato ti treba heuristika, da pametno koristis DIjkstru. Na internetu sam nasla nesto radjeno u Javi ( sto je prakticno isto sto i C# ), 

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. 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.
A koliko to cvorova imas pa je problem? Preko milion? 


ali nisam jos skinula posto implementacija nije nikakav problem. Srz koda zauzima ne vise od jednog ekrana. Graf se ne cuva ni kao lista ni kao matrica, to je objekat, ali ti verovatno mislis na informacije o susedima, one su sastavni deo tog objekta, zapravo objekta unutar objekta ( cvora ) i mozes da ih cuvas i kao niz i kao listu. Nemoj da mislis da bas mnogo dobijas time sto ih cuvas listom. Gubitak prostora nije veliki, a stedis vreme prolazaka kroz listu. Ako se vreme ipak pokaze kao nekriticno, bice normalno usvojena lista. Sad je niz. Tacka. Nisu to nizovi koji imaju 1 na poziciji koja 

Nisam ja pao sa Marsa, da se razumemo. Grafovi se generalno cuvaju ili kao matrice susednosti ili kao liste suseda. E da li je ta lista ono sto je u strukturama podataka poznato kao ulancana lista ili je niz, nije bitno. Bitno je koje vreme ti je potrebno za recimo proveru da li su dva cvora susedna. Matrice susednosti su retko bolje resenje, Flojdov algoritam jedan primer, skoro svi algoritmi podrazumevaju da je graf dat kao u obliku lista susednosti. Znaci, pricam o principijelnim stvarima, ne o konkretnoj implementaciji. Normalno je da je niz brzi.

odgovara susednom cvoru, to je kratki niz indeksa suseda, zapravo, ako bas hoces teorijskim terminima, to je lista 
susednosti sacuvana kao niz. Znaci, ono sto dovodi pojave O ( E ) u tvojoj formuli slozenosti je implementirano. Ono sto 
dovodi do pojave O ( log N ) nije ali je to ( trazenje najbolje procene ) upravo zato odvojeno u poseban metod klase, da bi se moglo odvojeno menjati radi poboljsanja.

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.

Kako se sami cvorovi cuvaju ? E tu bi vec lista bila promasaj. Jako je bitno da imas mogucnost direktnog pristupa, 

Kakva sad lista? To nigde nisam spomenuo. 


                    Milan