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ă ${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/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/381245?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.