[csidc:2003] - Re: cetvrtak by "Savic Andjelija" <andjas@EUnet.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. 
"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# ), 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 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.Kako se sami cvorovi cuvaju ? E tu bi vec lista bila promasaj. Jako je bitno da imas mogucnost direktnog pristupa, razmisli koliko bi te to usporilo pri radu... Drugi razlog, odluka o tome kako se cuvaju cvorovi nije jos definitivno pala. Kada konverujem celu mapu videcu kakvi su memorijski zahtevi, mozda necu cuvati sve odjednom, ako je tako isparcacu graf na delice velicine koja odgovara najbrzoj implementaciji. Hocu da kazem, ako vec budem morala da "cepam" graf onda cu bar za te delove prostor da koristim bezobzirno. Sto se tice jednosmernih ulica i prohodnosti, tu si potpuno u pravu, o tome sam vec razmisljala i dosla sam do iste ideje sa koeficijentima ( cuvali bi se kao dodatni atributi informacija o susedima ) ali bih za pocetak bila srecna da proradi i verzija bez tih detalja. Problem jednosmernih ulica resen je samom prirodom grafa, samo sto ih trenutno ne uzimam u obzir ( ne znam jos ni tacan spisak ).  
Pozdrav, Andjelija
  ----- Original Message ----- 
  From: Milan Stanojevic 
  To: csidc@titan.etf.bg.ac.yu 
  Sent: Thursday, January 09, 2003 7:27 PM
  Subject: Re: [csidc] cetvrtak


  Ne znam zasto ti je Dajkstrin algoritam problem. 
  Njegova slozenost u najboljoj implementaciji je O(N logN)(N - broj cvorova), ali moras da koristis neke egzoticne strukture (Fibonaci hip), inace moze da se implementira pomocu jednostavnog binarnog hipa u O((N+E) logN) (E broj ivica). Kako ti je ovde broj ivica reda velicine broja cvorova (planaran graf, sa maksimalno 4-5 ivica u jednom cvoru) znaci da ti je slozenost O(N log N). Graf moras da cuvas kao listu suseda, a ne kao matricu. 
  Drugo, u konkretnom problemu nije potrebno naci bas najkraci put u smislu duzine vec vremena, sto znaci da mora da se zna prohodnost ulica, jer guzva, semafori, jednosmerne ulice uticu na rezultat. Mozda mozes da uvedes neki varijabilni koeficijent kojim bi se mnozila duzina ulice a koji bi simulirao trenutno stanje ulice (beskonacno za zastoj, ili 1 ako je cista ulica).
  Mozes da nadjes na internetu optimizovane implementacije Dajkstrinog algoritma, doduse ne u C# (jel to koristite zato sto je M$ sponzor) ali verovatno nije problem da se konvertuje.

      Pozdrav,
          Milan

    ----- Original Message ----- 
    From: Savic Andjelija 
    To: csidc@titan.etf.bg.ac.yu 
    Sent: Thursday, January 09, 2003 4:48 PM
    Subject: [csidc] cetvrtak


    Uporedila sam algoritme. Radili su na grafu od 135 cvorova koji predstavlja deo grada oko Cubure ( prilicno je gusto ). Poredjenje je izvrseno za skup parova izvor - odrediste, ukupno 1764. Dijsktra uvek daje najkrace rastojanje. Prvi algoritam od njega odstupa za 4.684%, a drugi za 3.109%. Procenti nisu veliki ali dosta ih spustaju parovi izvor - odr. koji su jako blizu, pa se sva tri algoritma dobro snadju. Drugo, to su samo procenti, i to srednja vrednost procentualnog odstupanja, ja ovde vidim sta se dogadja na ekranu i nekad je odstupanje  od Dijkstre bas katastrofalno. Druga dva algoritma zasnovana su na heuristickoj proceni. Oni imaju dobre osobine kada razgovaramo o velikom broju cvorova, ALI ne mogu da garantuju najkraci put, sto je nedopustivo ( bez obzira na poklapanje u procentima ). Njih bi odmah odbacila, ali me brine kako ce Dijkstra da se ponasa na ogromnim grafovima ( on se prakticno kao talas siri oko izvorisnog cvora i to me nervira ). Ako bude davao lose rezultate, moracu da kombinujem. Zadrzacu njegovu osnovnu ideju, a koristicu heuristiku da ga ubrza i usmeri. To je jedan nacin. Drugi bi bio da podelim ogroman graf na segmente, da primenim Dijkstru u okviru segmenata, pa posle da povezem segmente. Treci nacin i najgori i poslednja solucija bio bi da se Dijkstra ne koristi "live", vec da se koristi samo jednom, da izgenerise najkrace puteve za sve moguce parove cvorova, da se to zapamti trajno u nekoj hijerarhijski organizovanoj strukturi, sa mogucnoscu direktnog pristupa... ali ovo je stvarno poslednja opcija. Ako ovo primenimo stvarno treba da se stidimo. Pokusavala sam rezulate druga dva algoritma da priblizim Dijkstri ali sto se vise priblize, njihovi zahtevi po pitanju memorije i vremena su veci i postaje sve besmisleno. Imam sa njima jos jedan problem. Kada ih zustaviti ? Ja dostignem odrediste, ali ne smatram odmah da je to najkraca putanja, pustim jos nekim putanjama da probaju da dostignu cilj da bi uporedila rastojanje. Neke putanje koje su mozda bolje, su mozda i "sporije" i mozda ih nikad necu ni uzeti u obzir...
    Sada mi predstoji ono sto me najvise mrzi, moram da konvertujem veliki deo mape, da ga povezem i da probam Dijkstru. Ako upali, upalilo je. Ako ne, ? 
    Pozdrav, Andjelija