1. Formularea problemei
Avem n noduri si distante d(i,j). Cautam un circuit care viziteaza fiecare nod exact o data si revine la nodul initial, cu lungime totala minima.
In simulator, distantele sunt euclidiene si simetrice: d(i,j) = d(j,i). Metodele euristice produc rapid un circuit, dar nu garanteaza optimul. Metodele exacte garanteaza optimul, insa pot necesita mult mai multe calcule.
2. Cel mai apropiat vecin Euristica
Ideea
La fiecare pas alegem cel mai apropiat nod care nu a fost vizitat.
- Alegem nodul de pornire s.
- Din nodul curent cautam nodul nevizitat cu distanta minima.
- Il adaugam la traseu si repetam pana sunt vizitate toate nodurile.
- Revenim la s pentru a inchide circuitul.
Avantaj: foarte simpla si rapida, aproximativ O(n^2). Dezavantaj: o alegere locala buna poate impune o muchie foarte lunga la final. Rezultatul depinde de nodul initial.
3. Circuite din ce in ce mai mari Euristica
Ideea
Construim un circuit mic, apoi introducem pe rand cate un nod astfel incat cresterea lungimii sa fie minima.
- Pornim de la nodul initial si cel mai apropiat nod de acesta; avem un circuit cu doua noduri.
- Pentru fiecare nod v ramas si fiecare muchie (i,j) a circuitului, calculam costul inserarii.
- Alegem global perechea (nod, pozitie) cu cea mai mica crestere.
- Introducem nodul si repetam.
Exemplu: daca d(A,B)=10, d(A,C)=6 si d(C,B)=7, inserarea lui C intre A si B creste circuitul cu 6+7-10=3.
Avantaj: tine seama de intregul circuit construit. Limita: inserarile anterioare nu sunt revizuite; solutia poate ramane suboptimala. Implementarea directa are complexitate O(n^3).
4. Inlocuirea diagonalelor cu laturi opuse (2-opt) Imbunatatire locala
Ideea
Pornim de la un circuit deja construit. Alegem doua muchii neadiacente (A,B) si (C,D), le eliminam si le inlocuim cu (A,C) si (B,D), inversand ordinea nodurilor din segmentul intermediar.
Daca castigul este pozitiv, acceptam modificarea si reluam cautarea. Ne oprim cand nu mai exista nicio astfel de schimbare avantajoasa.
In planul euclidian, eliminarea intersectiilor dintre muchii este un exemplu intuitiv de imbunatatire 2-opt. Totusi, 2-opt poate imbunatati si circuite fara intersectii.
Avantaj: imbunatateste adesea substantial un circuit initial. Limita: ajunge la un optim local 2-opt, nu neaparat la optimul global. In simulator, circuitul initial poate proveni din vecinul apropiat, insertie sau arborele dublat.
5. Dublarea muchiilor arborelui minim Euristica cu garantie
Ideea
- Construim un arbore partial de cost minim (MST) care conecteaza toate nodurile.
- Dublam fiecare muchie a arborelui. Fiecare nod are acum grad par.
- Parcurgem un circuit eulerian in multigraful rezultat.
- Eliminam vizitele repetate ale nodurilor prin scurtaturi, pastrand prima vizita si inchizand circuitul.
Ultima inegalitate este valabila daca distantele respecta inegalitatea triunghiului, asa cum se intampla pentru distantele euclidiene.
Avantaj: obtinem un circuit de cel mult doua ori mai lung decat optimul. Limita: garantia este o limita teoretica, nu o promisiune ca rezultatul va fi aproape de 2*OPT; adesea este mult mai bun.
6. Algoritmul exact Eastman Exact
6.1. Relaxarea prin problema de atribuire
Reprezentam traseul prin variabile binare x(i,j), egale cu 1 daca plecam direct din nodul i in nodul j. Fiecare nod trebuie sa aiba exact un succesor si exact un predecesor.
Aceste conditii definesc o problema de atribuire, echivalenta cu un cuplaj perfect de cost minim intre doua copii ale multimii nodurilor: noduri de plecare si noduri de sosire.
Solutia poate contine mai multe circuite disjuncte (subcircuite). Prin urmare, costul atribuirii reprezinta o limita inferioara pentru TSP.
6.2. Eliminarea subcircuitelor prin ramificare
Presupunem ca relaxarea produce doua subcircuite, de exemplu (1,3,1) si (2,4,5,2). Nu avem inca un circuit hamiltonian.
- Alegem un subcircuit, de exemplu (1,3,1).
- Orice circuit hamiltonian trebuie sa elimine cel putin unul dintre arcele 1->3 si 3->1.
- Construim doua subprobleme: in prima interzicem arcul 1->3, iar in a doua interzicem arcul 3->1.
- Rezolvam din nou atribuirea in fiecare subproblema si obtinem limite inferioare noi.
- Continuam ramificarea acolo unde apar subcircuite.
6.3. Cand eliminam o ramura?
Mentinem o limita superioara UB, adica lungimea celui mai bun circuit hamiltonian cunoscut, initial obtinut printr-o euristica. Pentru fiecare subproblema avem limita inferioara LB.
Cand toate ramurile sunt rezolvate sau eliminate, cel mai bun circuit gasit este optim global. Nu este suficient sa eliminam arbitrar cate un arc pana apare un circuit: trebuie explorate ramurile relevante pentru a pastra garantia de optimalitate.
6.4. Ce face concret simulatorul?
Rezolva exact fiecare problema de atribuire prin programare dinamica pe submultimi, nu prin algoritmul ungar. Apoi foloseste ramificarea si limitarea (branch-and-bound) pentru eliminarea subcircuitelor. Inregistreaza limitele, subcircuitele si interzicerile de arce.
Cost de calcul: rezolvarea unei atribuiri prin programare dinamica necesita O(n * 2^n) timp si O(2^n) memorie, iar numarul subproblemelor din ramificare poate creste exponential. Metoda este exacta, dar poate deveni lenta.
De ce atribuirea este doar o relaxare?
Pentru ca restrictiile de intrare si iesire garanteaza o acoperire a nodurilor prin circuite disjuncte, nu neaparat printr-un singur circuit. TSP impune suplimentar conectivitatea intregului traseu.
7. Enumerarea exhaustiva Exact
Fixam nodul initial si generam toate permutarile celorlalte n-1 noduri. Pentru fiecare permutare inchidem circuitul si calculam lungimea. Pastram minimul.
Pentru 9 noduri sunt 8! = 40 320 permutari cu nodul initial fixat. Daca am enumera toate cele n! ordonari, am numara de n ori aceleasi circuite prin schimbarea punctului de pornire. Pentru distante simetrice, si inversarea ordinii descrie acelasi circuit neorientat.
In simulator enumerarea este limitata la n <= 9, pentru a permite verificarea directa a optimului obtinut prin Eastman.
8. Compararea algoritmilor
| Metoda | Exacta? | Principiul | Observatie |
|---|---|---|---|
| Vecin apropiat | Nu | Alegere locala | Depinde de start |
| Insertie minima | Nu | Cresterea minima a circuitului | Nu revizuieste inserarile |
| 2-opt | Nu | Schimburi de doua muchii | Optim local |
| Arbore dublat | Nu | MST, Euler, scurtaturi | Garantie 2*OPT pentru TSP metric |
| Eastman | Da | Atribuire + ramificare | Demonstreaza optimalitatea |
| Enumerare | Da | Toate permutarile relevante | n <= 9 in simulator |
Experiment recomandat
- Generati 7 noduri cu un seed fix.
- Rulati toate cele patru euristici si notati lungimile.
- Rulati Eastman si enumerarea; verificati ca obtin acelasi optim.
- Calculati abaterea relativa: 100 * (L_euristica - OPT) / OPT.
- Schimbati seed-ul si observati cum se modifica ierarhia euristicilor.