Zatarra Posted November 24, 2011 Report Share Posted November 24, 2011 Se dau urmatoarele puncte:As dori sa veniti cu idei pentru aflarea distantei optime de a parcurge toate cele 5 puncte A,B,C,D,E.Se stie ca plecarea e din start.. graful e bidirectional in toate nodurile mai putin START (deoarece acesta este punctul de plecare), se stiu distantele intre noduri (d(A,!=d(B,A) - un exemplu).As dori o solutie in pseudocod daca se poate, o transpun eu in java, respectiv php.Multumesc anticipat.P.S. Nu veniti cu idei de genul aplica Greedy, aplica Dijkstra, aplica Floyd aplica nu stiu ce. Am nevoie strict pe exemplul acesta.P.P.S. Eu m-am gandit la un backtrackig cu suma minima a distantelor. Quote Link to comment Share on other sites More sharing options...
Xander Posted November 25, 2011 Report Share Posted November 25, 2011 la puncte asa putine nici nu se simte backtracku btw faza cu trecutul o singura data prin s poate sa fie ceva de genul shoot yourself in the legexemplu:d(*,*) = 5d(s,a) = 1d(d|c,a) = 200 cel mai scurt ar fi s,a,s,...ca sa scoti si cazul asta iti ti o matrice si marchezi arcele prin care ai trecutm: s a b c d es 1a 0bcdepas1: m[s,a] = 1pas2: m[a,s] = 1pas3: ... etcsi faci backtrack tratand toate arcele ca bidirectionale... sa poti sa mergi si s-> si a->s 1 Quote Link to comment Share on other sites More sharing options...
Zatarra Posted November 25, 2011 Author Report Share Posted November 25, 2011 Am gasit solutia, trebuie folosit algoritmul A* deoarece functia h am si e precisa (indeplineste toate conditiile pentru A*).Mai ramane sa implementez.Ms de raspuns Xander. Quote Link to comment Share on other sites More sharing options...