Backtracking in plan

[•costi_.-.]

Salut.
In afara de abordarea backtracking,exista alte solutii mai eficiente pentru puncul (b) de la problema 4  .Sper sa intelegeti cerinta:
http://infoscience.3x.ro/c++/Backtracking_%20in_%20plan.htm

[•PlayLikeNeverB4]

Daca nu e nevoie sa cunosti drumul, poti face o parcurgere in latime pornind din punctul de start.

[•SpiderMan]

Da exista, poti sa vezi algoritmul lui Lee (cunoscut in termen de grafuri ca si parcurgere in latime), si diversele probleme de pe InfoArena, cu solutii oficiale.
[LE] Se pare ca am scris in acelasi timp ...

[•costi_.-.]

Stiu de algoritmul BFS si de aplicatiile lui pe o matrice .Dar, in problema drumul cel mai "consistent" inseamna (presupun) drumul cu suma maxima.
Eu ma gandeam sa memorez toate drumurile posibile de la sursa la tinta intr-o matrice,sa calculez suma pentru fiecare in parte si apoi afisez drumul cu suma cea mai mare.Binenteles, asta e abordarea Bk.Ori, eu vreau sa aflu drumul maxim direct .

[•PlayLikeNeverB4]

Poate am facut greseala sa presupun ca soricelul poate merge de doua ori pe acelasi drum. Si in acest caz, suma ar fi egala cu suma tuturor casutelor accesibile.
In cazul in care nu poate, nu cred ca ramane altceva decat backtracking 

[•darkseeker]

In cazul in care nu poti trece de 2 ori prin aceeasi celula din matrice ai urmatoarea solutie fara backtracking :
Folosesti algoritmul lui dijkstra , o stare fiind definita de ( i , j , cost ) ea reprezentand costul maxim al unui drum de la celula linieStart,coloanaStart la celula i,j . Evident vei modifica algoritmul pentru a-ti obtine costul maxim .

[•PlayLikeNeverB4]

Imi vine greu a crede ca exista o astfel de solutie. Poate vrei sa detaliezi?

[•darkseeker]

Ai dreptate . Solutia este eronata . Imi cer scuze ca nu m-am gandit mai mult ... a fost la repezeala si nu mi-am dat seama ca mai mereu in matrice ar exista un ciclu de cost pozitiv ( care ar imbunatati intr-una costul maxim al unui drum ) .