Pagini: [1] 2 3 ... 8   În jos
  Imprimă  
Ajutor Subiect: 009 Algoritmul lui Dijkstra  (Citit de 117464 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« : Februarie 27, 2008, 23:01:42 »

Aici puteţi discuta despre problema Algoritmul lui Dijkstra.
Memorat
byndrsn
Client obisnuit
**

Karma: 19
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #1 : Februarie 27, 2008, 23:39:26 »

O varianta dragutza a algoritmului lui Dijkstra foloseste "buckets" in loc de heaps si merge foarte bine in practica. Nu imi amintesc exact daca are un nume, cred ca e cunoscut ca Dial's implementation of Dijkstra's algorithm. Algoritmul e foarte simplu si foloseste cateva idei dragutze care s-ar putea sa fie utile.

Pot sa schitzez algoritmul daca starneste interesul cuiva Smile.

Later edit:

Dial's algorithm - varianta naiva:

Algoritmul lui Dial difera de algoritmul lui Dijkstra prin metoda in care selecteaza nodul cu distantza temporara minima la fiecare pas. Fie C lungimea maxima a unei muchii in G. Algoritmul mentine nC + 1 buckets numerotate de la 0 la nC: in bucket k se afla toate nodurile cu distantza temporara egala cu k (orice distantza temporara finita este cel mult nC). 

Pentru a selecta nodul cu distantza temporara minima, scanam buckets 0, 1, ... pana intalnim primul bucket k care nu e gol (fiecare nod din bucket k este un nod cu distanza temporara minima). Pentru fiecare nod v din bucket k, stergem v din bucket, marcam distantza lui v ca permanenta si modificam distantele vecinilor lui v (daca e necesar). Cand distantza unui nod v este schimbata de la d_1 la d_2, mutam v din bucket d_1 in bucket d_2 (daca d_1 este infinit, v intra in bucket d_2). La urmatorul pas, vom rezuma scanarea incepand de la bucket k + 1. Algoritmul merge pentru ca distantzele marcate ca permanente in algoritmul lui Dijkstra sunt non-decreasing. Buckets pot fi implementate folosind liste dublu inlantuite (ca sa obtinem O(1) pentru fiecare operatie necesara: verifica daca un bucket e gol, sterge un element din bucket, adauga un element in bucket).

Worst-case running time e O(m + nC) care e nu e polinomial, dar algoritmul e foarte rapid in practica.  Spatiul necesar e O(nC), dar se poate mult mai bine. E suficient sa mentinem doar C + 1 buckets. Buckets sunt numerotate de la 0 la C si un nod v cu distantza finita d(v) este in bucket d(v) mod(C + 1). Aceasta varianta se bazeaza pe urmatoarea observatie: daca un nod u a primit o distantza permanenta la inceputul unei iteratii a algoritmului lui Dijkstra, toate nodurile v cu distantza temporara finita satisfac d(v) <= d(u) + C la sfarsitul iteratiei. Asa ca in orice moment un anumit bucket contine doar noduri cu aceeasi distantza (in plus, daca un nod cu distantza minima e in bucket k, buckets k + 1, k + 2,  ..., C, 0, 1, ..., k - 1 contin noduri cu distantza din ce in ce mai mare).

Mai sunt doua idei dragutze (Dial's implementation cu "bounded-width buckets" si "multi-level buckets") pe care poate o sa le scriu in curand.

Se pare ca ia 100 (cam la limita pe ultimul test) (http://infoarena.ro/job_detail/144869)

Un mic articol despre Dial's algorithm and variations o sa apara aici: http://infoarena.ro/dijkstra-buckets
 
« Ultima modificare: Martie 17, 2008, 20:32:43 de către Alina Ene » Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #2 : Februarie 28, 2008, 00:42:23 »

Posteaza-l te rog. M-ai facut curios.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #3 : Februarie 28, 2008, 01:50:43 »

wefgef: nu mai stii problema car? exact chestia asta faci: tii liste pentru costuri fixate.

La asta ma refeream cand am pus in training-path (http://infoarena.ro/training-path) dijkstra cu costuri mici.
Memorat
byndrsn
Client obisnuit
**

Karma: 19
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #4 : Februarie 28, 2008, 02:31:40 »

Era postat pe site deja? Oops, ar trebui sa ma uit mai atent in viitor  Whistle .
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #5 : Februarie 28, 2008, 03:08:40 »

E doar o solutie a unei probleme din concurs unde costurile sunt 0, 1, 2, 3, nu o explicatie detaliata a algoritmului general.

Uite un articol in ginfo despre acelasi algoritm: http://www.ginfo.ro/revista/13_6/focus2.pdf
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #6 : Februarie 28, 2008, 09:06:52 »

wefgef: nu mai stii problema car? exact chestia asta faci: tii liste pentru costuri fixate.

La asta ma refeream cand am pus in training-path (http://infoarena.ro/training-path) dijkstra cu costuri mici.

Nu stiam ca asta e numele algoritmului Smile.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #7 : Februarie 28, 2008, 09:41:49 »

@byndsr poti baga descrierea ce ai facut-o in un articol scurt si cu link spre problema asta si implementarea ta si spre problema car. Infoarena e wiki deci poti sa contribui usor si algoritmul e misto sa fie mentionat.
Memorat
Prostu
Nu mai tace
*****

Karma: 134
Deconectat Deconectat

Mesaje: 323



Vezi Profilul
« Răspunde #8 : Martie 01, 2008, 10:20:42 »

O alta implementare care ia 100 de puncte este folosind priority_queue din STL. Daca imi amintesc bine, Cosmin ii spunea lazy detection.
La problema asta am observat din nou, cat de rapide sunt streamurile din g++ 4.2. Folosind functiile standard iau 90 de puncte, pentru ca ultimul test iese din timp. Folosind insa streamurile, ultimul test intra in aprox 450 ms.

Nu stiu ce nume are. Bellman-Ford cu coada, din cate stiu se numeste Bellman-Kalaba. Poate are si el un nume de care nu am auzit inca. Nu auzisem nici numele de Dial, desi am folosit in mai multe probleme BFS/Bellman-Ford cu cozi pentru fiecare cost.
« Ultima modificare: Martie 01, 2008, 10:36:59 de către Filip Stefan A. » Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #9 : Martie 01, 2008, 10:23:46 »

Eu as spune ca e un Bellman-Ford cu priority_queue :-"... e exact ca bellman-ford cu coada numai ca in loc de coada e folosit un heap
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #10 : Martie 01, 2008, 10:30:09 »

Pai atunci Dijkstra in sine e Bellman-Ford cu Set / Heap... Dijkstra se bazeaza pe ideea de a extrage minimul la fiecare pas si a scoate nodul acela din graf... Bellman-Ford cu sau fara coada se bazeaza pe faptul ca dupa N relaxari a tuturor muchiilor distantele minime sunt calculate...
« Ultima modificare: Martie 01, 2008, 10:37:05 de către Bogdan Tataroiu » Memorat
the1dragon
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #11 : Martie 05, 2008, 21:40:22 »

o alta varianta de implementare: in loc de heap folosim un arbore de intervale. mi se pare putin mai scurta implementarea.
Memorat
cosser
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« Răspunde #12 : Martie 10, 2008, 17:37:29 »

 ce face un heap in algoritmul lui dijkstra? e o coada cu prioritate? apropo credeti ca e mai bun un heapsort decat un quicksort?
Memorat
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #13 : Martie 10, 2008, 17:43:52 »

Algoritmul lui Dijkstra alege la fiecare pas nodul inca neales de cost minim. Daca tu mentii un vector, va trebui de fiecare data sa parcurgi tot vectorul pentru a vedea care este acest nod, si asta se poate dovedi ineficient. Daca vrei sa faci mai bine, trebuie sa gasesti o structura de date care sa poata extrage minimul si modifica valoarea unui element/sterge un element in O(1) sau O(logN). Aceasta structura poate fi un heap.
Astfel, cand aplici algoritmul lui dijkstra, ca sa afli care este nodul de cost minim inca neales interoghezi heapul in complexitate O(1). Ai aflat acest nod si il stergi din heap, cu complexitate O(logN). Apoi relaxezi toate muchiile din nodul curent, care inseamna sa modifici valoarea costului unui nod in heap, care se realizeaza tot cu complexitate O(logN).
Complexitatea finala va fi O(M log N), care, daca graful este rar, este mult mai buna decat O(N^2).
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #14 : Martie 10, 2008, 17:46:44 »

ce face un heap in algoritmul lui dijkstra? e o coada cu prioritate? apropo credeti ca e mai bun un heapsort decat un quicksort?

Un heap este intr-adevar o coada de prioritate.

Quicksort e mai bun decat heapsort si e si mai scurta implementarea.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
hitmann
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 14



Vezi Profilul
« Răspunde #15 : Martie 10, 2008, 18:19:30 »

cred ca s-au reavaluat sursele aveam 100 si acum vad ca am 90, oricum m-am chinuit si prima oara sa obtin 100, acuma nu am idei inafara faptul ca eu cred ca folosesc prea mult memorie fapt ce imi incetineste executia.
am declarat :
Cod:
const
pinfinit=maxlongint;
type long=1..50000;
     pnod=^nod;
     nod=record
         nod:long;
         i:0..1000;
         urm:pnod;
         end;
     cheie=record
           val:longint;
           poz:long;
           end;
     vec=array[1..50000]of long;
var a:array[1..50000]of pnod;
    d:array[1..50000]of record
                        d:longint;
                        s:0..1;
                        end;
    id:^vec;
    h:array[1..50000]of cheie;
    i,poz,n,m,dheap,he,min:longint;
    p:pnod;
    ok:boolean;
    g:text;
 

 A - lista muchiilor
 D- distanta minima pana la fiecare nod si un alt camp care retine daca nodul mai este sau nu in coada ( initial aveam 2 vectori distincti dar am constatat cu uimire ca daca declar un singur vector de inregistrari cu 2 campuri, programul ruleaza mai repede desi nu inteleg de ce)
 H - heapul
 ID - vector auxiliar pt operatiile in heap
Cu ce ma complic ca nu imi dau seama ? (ies din timp la ultimul test)
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #16 : Martie 10, 2008, 18:53:49 »

ce face un heap in algoritmul lui dijkstra? e o coada cu prioritate? apropo credeti ca e mai bun un heapsort decat un quicksort?

Un heap este intr-adevar o coada de prioritate.

Quicksort e mai bun decat heapsort si e si mai scurta implementarea.

Un heap nu este o coada de prioritate. Poti implementa o coada de prioritate folosind un heap, dar o coada de prioritate este o structura de date abstracta (http://en.wikipedia.org/wiki/Abstract_data_type).
Memorat
cosser
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« Răspunde #17 : Martie 11, 2008, 14:59:13 »

dijkstra cu heap e mai bun intr-un graf cu costuri pozitive,decat bellman ford cu coada?
 iar oftopic, pentru arborele partial de cost minim, algoritmul lui prim este mai eficient decat altii?
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #18 : Martie 11, 2008, 15:06:13 »

Dijkstra cu heapuri are complexitatea mai buna, deci ar trebui sa fie mai rapid, insa bellman ford se implementeaza mai rapid Smile.

Pentru APM, eu folosesc Kruskal, tot datorita implementarii mult mai simple. Teoretic, Prim este mai bun.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
cosser
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« Răspunde #19 : Martie 11, 2008, 17:32:02 »

OK mersi
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #20 : Martie 17, 2008, 22:21:06 »

Kruskal e O(m log m + m log* n) daca folosesti structuri de multimi disjuncte. Daca il implementezi tzaraneste are O(m log m + n^2).

Algoritmul lui Prim daca il implementezi ca in manual are complexitate O(n^3), daca il implementezi dupa cum se sugereaza in cormen ajungi la O(n^2) sau O(m log n) daca folosesti heapuri.

Se merita sa folosesti Prim in loc de Kruskal cand graful e dens. Eu am primit la o finala agora o problema unde trebuia sa determini arborele partial de cost minim pentru un graf dat de niste puncte in plan. In cazul asta algoritmul lui Prim are complexitate O(n^2) pe cand cel a lui Kruskal are O(n^2 log n), si asta era diferenta intre 100 si 40 de puncte.

Pentru curiosi, arborele partial de cost minm intr-un graf de genul asta se poate determina in complexitate O(n) dar acest rezultat este unul teoretic. Alta observatie misto este ca muchiile din arborele partial de cost minim in graful de care am vorbit apartin triangularizarii Delaunay care se poate determina in timp O(n log n) si are cel mult 3n - 6 muchii.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #21 : Martie 18, 2008, 11:24:20 »

http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree

S-a gasit O(N)?
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #22 : Martie 18, 2008, 18:46:12 »

Vorbeam prostii, dar exista un algoritm randomizat ce gaseste arborele partial de cost minim al unui graf in O(m). Pentru grafuri planare intr-adevar algoritmul e O(n log n).
Memorat
byndrsn
Client obisnuit
**

Karma: 19
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #23 : Martie 18, 2008, 19:46:34 »

Pentru grafuri planare, cel mai bun algoritm deterministic e O(n) (Cheriton-Tarjan). Pentru grafuri generale, cel mai bun algoritm deterministic e O(m alpha(n, m)) (alpha -- inverse Ackerman function) (Chazelle).
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #24 : Aprilie 07, 2008, 19:11:52 »

eu cu Bellman Ford iau doar 40 (3 TLE si 3 SIGSEGV) se poate implementa BF pt 100 ?
Memorat
Pagini: [1] 2 3 ... 8   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines