| Fişierul intrare/ieşire: | hamilton.in, hamilton.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.375 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Ciclu hamiltonian de cost minim
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.
Cerinţă
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.
Date de intrare
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.
Date de ieşire
Pe prima linie a fişierului de ieşire hamilton.out se va afla costul ciclului cerut. În cazul în care graful nu este hamiltonian, atunci în fişierul de ieşire se va afişa "Nu exista solutie".
Restricţii
- 1 ≤ N ≤ 18.
- 1 ≤ M ≤ N*(N-1).
- Nodurile sunt numerotate de la 0 la N-1.
- Costurile arcelor sunt numere întregi cuprinse în intervalul [1, 1 000 000].
- Nu există arc de la un nod la el însuşi.
- De la orice vârf x la orice vârf y există maxim un arc.
Exemplu
| hamilton.in | hamilton.out |
|---|---|
| 5 10 0 1 9 0 3 8 1 0 7 1 2 1 1 4 3 2 0 5 2 4 4 3 2 6 4 3 7 4 1 1 | 26 |
Explicaţie
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.
Indicaţii de rezolvare
O primă soluţie se bazează pe generarea tuturor permutărilor 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.
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 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 ş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] 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 2k][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][2i][i] = 0, iniţilizând astfel orice lanţ format dintr-un singur nod cu costul 0. Soluţia problemei este min{C[i][2N-1][j] + Cost[j][i]}, unde j este un nod dinspre care porneşte un arc spre i, deoarecere 2N-1 = (111...11)2. Complexitatea timp a acestei rezolvări este O(M*N*2N). 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*2N). O implementare a acestei idei poate fi studiată aici şi obţine 70 de puncte.
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*2N). Această idee poate fi implementată în mod clasic sau folosind memoizare. 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 (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.
Aplicaţii
Pentru a vă consolida cunoştinţele privind algoritmul prezentat in această problemă, vă recomandăm să rezolvaţi următoarele probleme:
Dacă doriţi să vă consolidaţi cunoştinţele privind programarea dinamică cu număr exponenţial de stări, puteţi încerca să rezolvaţi una din problemele următoare:
