Algoritm graf interesant ( ajutor )

[•AndreiGrigoras]

Problema este simpla : Dandu-se N puncte si M legaturi intre puncte ( avand fiecare un cost ) , aflati costul drumului minim ce porneste dintr-un nod X ( din cele N ) , trece prin toate celelalte puncte , si se intoarce inapoi in X ( un fel de circuit ) . Ai voie sa treci prin orice punct de oricate ori vrei , dar se cere costul minim ;

[•AlexandruValeanu]

Daca ai un ciclu de cost negativ nu ai solutie.
Altfel, problema se reduce la problema ciclului hamiltonian de cost minim.

[•AndreiGrigoras]

Costurile sunt toate pozitive , ideea este ca pot parcurge un nod / muchie de mai multe ori . Problema este ca se poate sa nu fie nici un ciclu in graf . Este o problema la cazul general ( graful poate fi arbore sau nu ) si trebuie gasita solutia optima

[•klamathix]

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Problema e NP-Hard în multe dintre variante, inclusiv dacă ai voie să repeți noduri. Găsești acolo mai multe detalii.

[•AndreiGrigoras]

Interesant , ea este trecuta ca si problema cu operatii pe biti . Problema este "excursie" de pe campion . In principiu se dau niste nume de localitati , distantele si se cere un drum minim din nodul X care sa treaca prin toate nodurile si sa se intoarca in X . Am reusit sa evit operatiile pe biti folodind map < string , int > . Dar am dat de subproblema cu drumul minim.

[•klamathix]

Mda, e cam amuzant să pui tag de "operații pe biți" la travelling salesman. Ideea este că una dintre soluțiile eficiente la problema asta se folosește de programare dinamică cu număr exponențial de stări, fiecare stare fiind formată dintr-o submulțime de noduri deja atinsă și nodul în care te afli în prezent. În mod tradițional submulțimea de noduri se codifică printr-o mască de biți (un număr natural care are biți de 1 doar pe biții corespunzători orașelor parcurse). De asta zic ei că e problemă cu operații pe biți.

Ai aici mai multe detalii despre soluție.

http://www.infoarena.ro/problema/hamilton