danielaion / stingyjoe Goto Github PK

*******************************************************************************
**************************** Stingy Joe ****************************************
*******************************************************************************
solveSimple: Determina cel mai scurt drum dintre doua orase. 

        Pentru rezolvarea acestei parti m-am folosit de algoritmul Floyd-Warshall,
    un algoritm care foloseste programare dinamica in scopul determinarii
    drumului optim intre oricare doua noduri dintr-un graf. 
        Recurenta de la care am pornit dezvoltarea solutiei cu scopul rezolvarii 
    celor doua task-uri este urmatoarea :

    d[i][j][k] 
        |daca i = j si k este 0 =0
        |daca k este 0 si exista o muchie cu nodurile i,j =costul muchiei
        |daca k este 0 infinit
        |altfel = minimul dintre d[i][j][k-1] si  (d[i][k][k-1] + d[k][j][k-1])
        
        Pentru acest task:
        La fiecare pas matricea d[i][j][k] stoca o pereche formata dintr-o lista de
    noduri (orasele prin care trecea sa ajunga de la nodul i la nodul j) si
    lungimea drumului.
        Comparatia pentru aflarea drumului optim se facea folosind lungimea
    drumului din pereche.
        Pentru reuniunea nodurilor am folosit functia 'union'  din cadrul 
    structurii Data.List.
        Pentru o implementare eficienta am folosit structura Data.Array oferita
    de haskell.

solveCosts : Joe trebuie sa isi viziteze prietenul dintr-un alt oras insa cum este 
		un tip zgarcit alege o suma (relativ mica) pe care sa o foloseasca
		in calatoria sa. Scopul este de a determina cel mai scurt traseu
		pe care Joe si-l permite.

        Am aplicat acelasi algoritm de la task-ul anterior caruia i-am adus mici 
    modificari si adaugari de noi functii. Una dintre modificari ar fi ca la fiecare
    pas matricea d[i][j][k] stocheaza acum o pereche formata dintr-o lista de 
    noduri (orasele prin care trece sa ajunga de la nodul i la nodul j) si
    o pereche in care se afla lungimea drumului si suma totala de bani 
    consumata pana in acel moment.
        Comparatia pentru aflarea drumului optim se facea folosind atat 
    lungimea drumului din pereche cat si a sumei de bani consumata.
        La sfarsit , pe baza listei de orase se construieste o lista in care 
    sunt stocati banii care raman dupa vizitarea fiecarui oras. Pe baza 
    elementelor din cele doua liste se construieste o lista de perechi. Alaturi
    de lungimea drumului se formeaza o pereche care va constitui rezultatul 
    asteptat.      


*******************************************************************************
Resurse:
[1] https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/18/Small18.pdf
[2] http://jelv.is/blog/Lazy-Dynamic-Programming/
*******************************************************************************