h2(#tramvai). 'Tramvai':problema/tramvai
Se construieste un graf al punctelor de intersectie dintre oricare $2$ drepte. Acest graf are $O(N^2^)$ noduri, insa fiecare nod are cel mult $4$ vecini (cate $2$ pe fiecare din cele $2$ drepte care il determina). Problema se reduce acum la determinarea drumului minim intre $2$ puncte in acest graf. Algoritmul folosit de solutia oficiala este 'Dijkstra':http://en.wikipedia.org/wiki/Dijkstra's_algorithm cu heap, care are complexitatea $O(N^2^*logN)$, insa se poate folosi cu succes si algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, implementat folosind o coada (aceasta varianta, cunoscuta ca algoritmul Bellman-Ford-Moore, are o complexitate teoretica mare, dar, in practica, merge foare bine; este, posibil, insa, ca, in cazul acestei probleme, sa fie necesare unele optimizari pentru a se incadra in limita de timp - de exemplu, folosirea euristicii "parent checking").
Se construieste un graf al punctelor de intersectie dintre oricare $2$ drepte. Acest graf are $O(N^2^)$ noduri, insa fiecare nod are cel mult $4$ vecini (cate $2$ pe fiecare din cele $2$ drepte care il determina). Problema se reduce acum la determinarea drumului minim intre $2$ puncte in acest graf. Algoritmul folosit de solutia oficiala este 'Dijkstra':http://en.wikipedia.org/wiki/Dijkstra's_algorithm cu heap, care are complexitatea $O(N^2^*logN)$, insa se poate folosi cu succes si algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, implementat folosind o coada. Aceasta varianta, cunoscuta ca algoritmul Bellman-Ford-Moore, are o complexitate teoretica mare, dar, in practica, merge foare bine; este, posibil, insa, ca, in cazul acestei probleme, sa fie necesare unele optimizari pentru a se incadra in limita de timp - de exemplu, folosirea euristicii "parent checking". Aceasta euristica se refera la urmatoarea situatie: Sa presupunem ca am extras din coada nodul $X$ (primul nod din coada) si urmeaza sa incercam sa facem update-uri la distantele tuturor vecinilor nodului $X$, folosind distanta calculata pana acum pentru $X$. De asemenea, sa presupunem ca nodul care i-a facut update la distanta minima nodului $X$ este $T$ ($T$ mai este numit si parintele lui $X$, deoarece este nodul chiar dinaintea lui $X$ de pe drumul minim pana la $X$). Inainte sa incercam sa facem update pentru toti vecinii lui $X$, verificam daca nodul $T$ se afla in coada. Daca se afla in coada, atunci nu mai facem update folosind nodul $X$ si trecem la urmatorul nod din coada. Motivul este urmatorul: Daca nodul $T$ se afla in coada, el a fost introdus acolo dupa ce i-a facut update distantei pana la nodul $X$; noua valoarea a distantei minime pana la $T$ este mai mica decat in momentul cand s-a calculat distanta minima pana la $X$, astfel ca, atunci cand vom extrage din coada nodul $T$, se va micsora in mod sigur si distanta pana la $X$. Prin urmare, nu are rost sa facem acum update-uri folosind nodul $X$, deoarece acesta are calculata o distanta despre care stim sigur ca va fi micsorata in curand.
h2(#biti3). 'Biti3':problema/biti3
