danielaion / stingyjoe Goto Github PK
View Code? Open in Web Editor NEWFunctional implementation of a shortest path in a graph algorithm
Functional implementation of a shortest path in a graph algorithm
******************************************************************************* **************************** 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/ *******************************************************************************
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.