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

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