== include(page="template/taskheader" task_id="hamilton") ==
Se dă un {"graf orientat simplu":http://en.wikipedia.org/wiki/Graph_(mathematics)#Simple_graph} cu $N$ vârfuri şi $M$ muchii, fiecare arc având asociat un cost. Un ciclu al acestui graf se numeşte hamiltonian dacă conţine fiecare nod din graf exact o singură dată. Un graf care conţine un astfel de ciclu se numeşte graf hamiltonian. Costul unui ciclu este egal cu suma arcelor aflate pe ciclu.
Se dă un graf orientat cu $N$ vârfuri şi $M$ muchii, fiecare arc având asociat un cost. Un ciclu al acestui graf se numeşte hamiltonian dacă conţine fiecare nod din graf exact o singură dată. Un graf care conţine un astfel de ciclu se numeşte graf hamiltonian. Costul unui ciclu este egal cu suma arcelor aflate pe ciclu.
h3. Cerinta
h3. Cerinţă
Fiind dat un graf orientat simplu cu costuri pe arce, să se verifice dacă acesta este hamiltonian. In caz afirmativ, să se determine ciclul hamiltonian de cost minim.
Fiind dat un graf orientat simplu cu costuri pe arce, să se verifice dacă acesta este hamiltonian. În caz afirmativ, să se determine ciclul hamiltonian de cost minim.
h2. Date de intrare
Pe prima linie a fişierului de intrare $hamilton.in$ se afla două numere întregi $N$ si $M$. Pe fiecare din următoarele $M$ linii se găseşte un triplet de forma $x y c$ cu semnificaţia că există un arc între vârfurile $x$ şi $y$ având costul $c$.
Pe prima linie a fişierului de intrare $hamilton.in$ se află două numere întregi $N$ şi $M$. Pe fiecare din următoarele $M$ linii se găseşte un triplet de forma $x y c$ cu semnificaţia că există un arc între vârfurile $x$ şi $y$ având costul $c$.
h2. Date de ieşire
!> problema/hamilton?chdcm-no.png 40%!
Ciclul hamiltonian de cost minim din exemplu este: $0 3 2 4 1 0$. Un alt ciclu hamiltonian este $0 1 4 3 2 0$, dar acesta are cost $30$.
Ciclul hamiltonian de cost minim din exemplu este: $0 3 2 4 1 0$. Un alt ciclu hamiltonian este $0 1 4 3 2 0$, dar acesta are costul $30$.
h2. Indicaţii de rezolvare
O primă soluţie se bazează pe 'generarea tuturor permutărilor':problema/permutari mulţimii ${0, ..., N-1}$. Pentru fiecare permutare generată ${p1, ..., pN}$ se verifică dacă există arcele $(p1 p2) (p2 p3) ... (pN-1 pN) (pN p1)$, iar în caz afirmativ se verifică dacă suma acestora este mai mică decât soluţia până la acest pas. Această soluţie are complexitate timp $O(N!)$ şi obţine $20$ de puncte. O sursă demonstrativă se găseşte 'aici':job_detail/381245?action=view-source.
O primă soluţie se bazează pe 'generarea tuturor permutărilor':problema/permutari mulţimii ${0, ..., N-1}$. Pentru fiecare permutare generată ${ p{~1~}, ..., p{~N~} }$ se verifică dacă există arcele $(p{~1~} p{~2~}) (p{~2~} p{~3~}) ... (p{~N-1~} p{~N~}) (p{~N~} p{~1~})$, iar în caz afirmativ se verifică dacă suma acestora este mai mică decât soluţia până la acest pas. Această soluţie are complexitate timp $O(N!)$ şi obţine $20$ de puncte. O sursă demonstrativă se găseşte 'aici':job_detail/381358?action=view-source.
Se observă că soluţia prezentată anterior nu verifică existenţa arcelor decât când întreaga permutare este generată. Această verificare se poate face în timpul generării permutării şi astfel se poate îmbunătăţi timpul de rulare. Această abordare se poate implementa şi sub forma unei 'parcurgeri în adâncime':problema/dfs care generează toate lanţurile din graf; în cazul în care se determină un lanţ cu $N$ noduri este verificată condiţia de închidere a ciclului (adică dacă există arcul dintre ultimul nod din lanţ şi nodul de start). În caz afirmativ, se verifică dacă ciclul găsit are un cost mai mic decât soluţia curentă. Acestă abordare are tot complexitate $O(N!)$, dar timpul de rulare este mai bun. O implementare a acestui algoritm se găseşte 'aici':job_detail/381246?action=view-source şi obţine $40$ de puncte.
Se observă că soluţia prezentată anterior nu verifică existenţa arcelor decât când întreaga permutare este generată. Această verificare se poate face în timpul generării permutării şi astfel se poate îmbunătăţi timpul de rulare. Această abordare se poate implementa şi sub forma unei 'parcurgeri în adâncime':problema/dfs care generează toate lanţurile din graf; în cazul în care se determină un lanţ cu $N$ noduri este verificată condiţia de închidere a ciclului (adică dacă există arcul dintre ultimul nod din lanţ şi nodul de start). În caz afirmativ, se verifică dacă ciclul găsit are un cost mai mic decât soluţia curentă. Acestă abordare are tot complexitate $O(N!)$, dar timpul de rulare este mai bun. O implementare a acestui algoritm se găseşte 'aici':job_detail/381359?action=view-source şi obţine $40$ de puncte.
O îmbunătăţire a complexităţii se poate obţine folosind metoda programării dinamice. Vom considera matricea $C$ având următoarea semnificaţie $C[i][j][k]=$ costul minim al unui lanţ ce începe în nodul $i$ se termină în nodul $k$ şi conţine toate nodurile identificate cu $1$ în configuraţia binară a lui $j$ exact o singură dată. De exemplu, pentru graful din enunţ, starea caracterizată de tripletul $(4, 23, 0)$ va avea valoarea $7$ şi va reprezenta costul minim al unui lanţ ce începe în nodul $4$, se termină în nodul $0$ şi conţine exact o singură dată nodurile ${0, 1, 2, 4}$, deoarece $23 = (10111){~2~}$ (ordinea biţilor este considerată cea inversă scrierii în baza $2$). Lanţul corespunzător acestei stări este $4 1 2 0$. Recurenţa este $C[i][j][k] = min{C[i][j xor 2^k^}][v] + Cost[v][k]}$, unde $v$ este un nod al cărui bit corespunzător din $j$ este $1$ şi care are un arc spre $k$, iar $Cost[v][k]$ reprezintă costul arcului respectiv. La început, C[i][2^i^][i] = 0, iniţilizând astfel orice lanţ format dintr-un singur nod cu costul $0$. Soluţia problemei este $min{C[i][2^N^-1][j] + Cost[j][i]}$, unde $j$ este un nod dinspre care porneşte un arc spre $i$, deoarecere $2^N^-1 = (111...11)${~2~}. Complexitatea timp a acestei rezolvări este $O(M*N*2^N^)$. Din punctul de vedere al complexităţii memorie, se observă că indicele $i$ este inutil, deoarece în recurenţă acesta nu se modifică şi poate fi fixat anterior. Astfel se poate obţine o complexite memorie $O(N*2^N^)$. O implementare a acestei idei poate fi studiată 'aici':job_detail/381247?action=view-source şi obţine $70$ de puncte.
O îmbunătăţire a complexităţii se poate obţine folosind metoda programării dinamice. Vom considera matricea $C$ având următoarea semnificaţie: $C[i][j][k]$ este costul minim al unui lanţ ce începe în nodul $i$, se termină în nodul $k$ şi conţine toate nodurile identificate cu $1$ în configuraţia binară a lui $j$ exact o singură dată. De exemplu, pentru graful din enunţ, starea caracterizată de tripletul $(4, 23, 0)$ va avea valoarea $7$ şi va reprezenta costul minim al unui lanţ ce începe în nodul $4$, se termină în nodul $0$ şi conţine exact o singură dată nodurile ${0, 1, 2, 4}$, deoarece $23 = (10111){~2~}$ (ordinea biţilor este considerată cea inversă scrierii în baza $2$). Lanţul corespunzător acestei stări este $4 1 2 0$. Recurenţa este $C[i][j][k] = min{C[i][j xor 2^k^][v] + Cost[v][k]}$, unde $v$ este un nod al cărui bit corespunzător din $j$ este $1$ şi care are un arc spre $k$, iar $Cost[v][k]$ reprezintă costul arcului respectiv. La început, $C[i][2^i^][i] = 0$, iniţilizând astfel orice lanţ format dintr-un singur nod cu costul $0$. Soluţia problemei este $min{C[i][2^N^-1][j] + Cost[j][i]}$, unde $j$ este un nod dinspre care porneşte un arc spre $i$, deoarecere $2^N^-1 = (111...11){~2~}$. Complexitatea timp a acestei rezolvări este $O(M*N*2^N^)$. Din punctul de vedere al complexităţii spaţiu, se observă că indicele $i$ este inutil, deoarece în recurenţă acesta nu se modifică şi poate fi fixat anterior. Astfel se poate obţine o complexite spaţiu $O(N*2^N^)$. O implementare a acestei idei poate fi studiată 'aici':job_detail/381360?action=view-source şi obţine $70$ de puncte.
Ideea care duce la rezolvarea ce obţine $100$ de puncte se bazează pe urmatoarea observaţie: deoarece ne propunem să obţinem un ciclu care conţine toate nodurile, nu este relevant nodul de start şi, deci, se poate fixa orice nod ca nod de început. Astfel, indicele $i$ din dinamica prezentată mai sus devine complet inutil. Complexitatea timp devine astfel $O(M*2^N^)$. Această idee poate implementată 'în mod clasic':job_detail/381244?action=view-source sau 'folosind memoizare':job_detail/381239?action=view-source. Memoizarea este o tehnică specifică programării dinamice bazată pe o funcţie recursivă cu ajutorul căreia se calculează doar stările necesare pentru obţinerea rezultatului (se ignoră astfel stările invalide sau inutile). Conceptul este simplu: în recurenţă se apelează aceeaşi funcţie pentru noua stare, iar valoarea este calculată doar dacă nu a mai fost calculată în prealabil. Această tehnică produce deseori timpi de rulare mai buni, fapt ce poate fi observat şi comparând cele două implementări exemplificate mai sus. *To do: Când dăm drumul la problemă să punem link-uri spre surse a căror timpi pot fi văzuţi şi de utilizatori.*
Ideea care duce la rezolvarea ce obţine $100$ de puncte se bazează pe următoarea observaţie: deoarece ne propunem să obţinem un ciclu care conţine toate nodurile, nu este relevant nodul de start şi, deci, se poate fixa orice nod ca nod de început. Astfel, indicele $i$ din dinamica prezentată mai sus devine complet inutil. Complexitatea timp devine astfel $O(M*2^N^)$. Această idee poate fi implementată 'în mod clasic':job_detail/381350?action=view-source sau 'folosind memoizare':job_detail/381349?action=view-source. Memoizarea este o tehnică specifică programării dinamice bazată pe o funcţie recursivă cu ajutorul căreia se calculează doar stările necesare pentru obţinerea rezultatului (se ignoră astfel stările invalide sau inutile). Conceptul este simplu: în recurenţă se apelează aceeaşi funcţie pentru noua stare, iar valoarea este calculată doar dacă nu a mai fost calculată în prealabil. Această tehnică produce deseori timpi de rulare mai buni, fapt ce poate fi observat şi comparând cele două implementări de mai sus.
Menţionăm că problema determinării unui ciclu hamiltonian este $NP$-completă şi, deci, nu se cunoaşte, până în prezent, nici un algoritm care să rezolve problema în timp polinomial. Cu toate acestea, există câteva tipuri de grafuri particulare pentru care există un astfel de algoritm polinomial. Unul dintre aceste cazuri este tratat într-un articol prezent pe infoarena, 'Ciclu hamiltonian într-un graf dens':ciclu-hamiltonian-in-graf-dens.
Menţionăm că problema determinării unui ciclu hamiltonian (de cost minim) este $NP$-completă şi, deci, nu se cunoaşte, până în prezent, nici un algoritm care să rezolve problema în timp polinomial. Cu toate acestea, există câteva tipuri de grafuri particulare pentru care există un astfel de algoritm polinomial. Unul dintre aceste cazuri este tratat într-un articol prezent pe infoarena, 'Ciclu hamiltonian într-un graf dens':ciclu-hamiltonian-in-graf-dens.
h2. Aplicaţii
