Problema comis-voiajorului (TSP)

Explicarea celor patru euristici, a algoritmului exact Eastman si a enumerarii exhaustive

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.

Minimizam L = d(v1,v2) + d(v2,v3) + ... + d(vn,v1)

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.

  1. Alegem nodul de pornire s.
  2. Din nodul curent cautam nodul nevizitat cu distanta minima.
  3. Il adaugam la traseu si repetam pana sunt vizitate toate nodurile.
  4. Revenim la s pentru a inchide circuitul.
U = multimea nodurilor nevizitate j* = argmin { d(i,j) : j in U }

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.

Experiment: rulati algoritmul din noduri initiale diferite. Pot aparea circuite cu lungimi diferite.

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.

  1. Pornim de la nodul initial si cel mai apropiat nod de acesta; avem un circuit cu doua noduri.
  2. Pentru fiecare nod v ramas si fiecare muchie (i,j) a circuitului, calculam costul inserarii.
  3. Alegem global perechea (nod, pozitie) cu cea mai mica crestere.
  4. Introducem nodul si repetam.
Delta(i,v,j) = d(i,v) + d(v,j) - d(i,j) Alegem inserarea cu Delta minima.

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.

Lungime veche = d(A,B) + d(C,D) Lungime noua = d(A,C) + d(B,D) Castig = Lungime veche - Lungime noua

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

  1. Construim un arbore partial de cost minim (MST) care conecteaza toate nodurile.
  2. Dublam fiecare muchie a arborelui. Fiecare nod are acum grad par.
  3. Parcurgem un circuit eulerian in multigraful rezultat.
  4. Eliminam vizitele repetate ale nodurilor prin scurtaturi, pastrand prima vizita si inchizand circuitul.
Cost(MST) <= OPT Cost(circuit eulerian) = 2 * Cost(MST) Cost(circuit final) <= 2 * OPT

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.

Minimizam SUM(i,j) d(i,j) * x(i,j) SUM(j) x(i,j) = 1, pentru fiecare i SUM(i) x(i,j) = 1, pentru fiecare j x(i,i) = 0; x(i,j) in {0,1}

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.

  1. Alegem un subcircuit, de exemplu (1,3,1).
  2. Orice circuit hamiltonian trebuie sa elimine cel putin unul dintre arcele 1->3 si 3->1.
  3. Construim doua subprobleme: in prima interzicem arcul 1->3, iar in a doua interzicem arcul 3->1.
  4. Rezolvam din nou atribuirea in fiecare subproblema si obtinem limite inferioare noi.
  5. 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.

Daca subproblema este imposibila -> eliminam ramura. Daca LB >= UB -> eliminam ramura. Daca apare un singur circuit si costul < UB -> actualizam UB. Altfel -> ramificam pe arcele unui subcircuit.

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.

Numar permutari examinate = (n-1)! Complexitate aproximativa = O(n!)

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

MetodaExacta?PrincipiulObservatie
Vecin apropiatNuAlegere localaDepinde de start
Insertie minimaNuCresterea minima a circuituluiNu revizuieste inserarile
2-optNuSchimburi de doua muchiiOptim local
Arbore dublatNuMST, Euler, scurtaturiGarantie 2*OPT pentru TSP metric
EastmanDaAtribuire + ramificareDemonstreaza optimalitatea
EnumerareDaToate permutarile relevanten <= 9 in simulator

Experiment recomandat

  1. Generati 7 noduri cu un seed fix.
  2. Rulati toate cele patru euristici si notati lungimile.
  3. Rulati Eastman si enumerarea; verificati ca obtin acelasi optim.
  4. Calculati abaterea relativa: 100 * (L_euristica - OPT) / OPT.
  5. Schimbati seed-ul si observati cum se modifica ierarhia euristicilor.

Mergi la simulator