marți, 13 noiembrie 2012

Despre problema comis-voiajorului (TSP - Travelling Salesman Problem)

Cât de simpli (sau de puţin simpli) pot fi algoritmii?

 Să presupunem că avem de rezolvat problema ciclului hamiltonian de cost minim. Ei, ei, nici chiar aşa! Aşa se numeşte, în limbaj „oficial”, şi, prin urmare, „scorţos” această problemă, altfel ea este foarte uşor de enunţat. Iată:

Se consideră o reţea de localităţi, A, B, C, D, şi aşa mai departe. Între fiecare dintre ele există un drum, direct, sau indirect, de lungime cunoscută (de exemplu, lungimea drumului dintre A şi B este d(A,B)). Dacă există mai multe drumuri, ceea ce cunoaştem este, de fapt, lungimea celui mai scurt dintre acestea. Un comis-voiajor vrea să plece dintr-un oraş – să zicem A – să treacă prin fiecare oraş o dată şi, în plus, să se întoarcă de unde a plecat. Cum rezolvăm această problemă?

O primă ideea ar putea fi aceasta: aflându-ne într-un anumit oraş, să mergem de îndată în oraşul cel mai apropiat, dacă acesta nu a fost deja vizitat, şi tot aşa până vizităm toate oraşele, după care ne reîntoarcem în oraşul iniţial.

Pentru a verifica dacă algoritmul nostru funcţionează corect, luăm în considerare un exemplu concret. Presupunem că toate oraşele sunt situate pe o anumită magistrală rutieră, la o anumită distanţă de oraşul iniţial, care este situat la „km. 0”. Stabilim un sens de parcurgere a acelei magistrale şi asociem fiecărui oraş un anumit număr, reprezentând distanţa de la /până la oraşul A, numărul fiind pozitiv dacă, pentru a ajunge din A în oraşul respectiv mergem în sensul convenit, respectiv negativ dacă nu se întâmplă pe dos. În tabelul de mai jos am înscris aceste valori.


Altfel spus, distanţa dintre două oraşe e dată de următoarea matrice (zisă şi de adiacenţă:

După cum se observă, folosind această strategie traseul ar fi A-B-C-D-E-F-G-H-A, cu o lungime totală de 1+3+7+15+31+63+127+85 = 332 km, in timp ce un traseu A-C-E-G-H-F-D-B ar avea lungimea de 2+8+32+127+64+16+4+1 = 254 km. E clar că strategia aleasă nu e bună!

O altă idee ar fi aceea de a alege întotdeauna drumul cel mai scurt dintre două oraşe, evitând situaţiile în care o astfel de alegere ar crea un ciclu, cu excepţia cazului că e chiar ciclul căutat, care conţine toate oraşele. Corespunzător acestei idei, vom alege succesiv drumurile: 
d(A,B) = 1, 
d(A,C) = 2 (am terminat cu A, nu mai putem alege drumuri care să treacă prin A), 
d(B,D) = 4 (nu putem alege d(B,C)=3 – s-ar închide ciclul; am terminat cu B), 
d(C,E) = 8 (nu putem alege d(C,D)=7, se închide ciclul; am terminat cu C ), 
d(D,F) = 16 (nu putem alege d(D,E)=15, se inchide ciclul; am terminat cu D), 
d(E,G) = 32 (nu putem alege d(E,F) = 21, se inchide ciclul; am terminat cu E), 
d(F,H) = 64 (nu putem alege d(F,G) = 63, se închide ciclul; am terminat cu F), 
d(G,H) = 127 (singura posibilitate). 
Corespunzător, vom obţine traseul A-B-D-F-H-G-E-C-A = 254, varianta optimă! Să fie aceasta soluţia corectă? Să considerăm o reţea de drumuri asemănătoar celei de mai jos (unde diferenţele dintre lungimile drumurilor reprezentate sunt foarte mici).
În funcţie de aceste mici diferenţe, putem ajunge la următoarea soluţie:
dar şi la ceva în genul:
ceea ce, evident, nu mai este corect.

Problema enuţată mai sus nu e simplă, dar, fireşte, nici nerezolvabilă. Mai întâi de toate, pentru că este o problemă finită, şi toate problemele finite, sunt, în principiu, rezolvabile! Acest „în principiu” nu este, de fapt, ceva prea încurajator, fiindcă sugerează, de fapt, o metodă tare-tare nenorocită, şi anume metoda forţei brute. În ce constă această metodă şi de ce este ea aşa de „nenorocită”? 

După cum arată şi numele, această metodă constă, de fapt, în generarea şi evaluarea tuturor situaţiilor posibile. În cazul problemei enunţate mai sus, dacă sunt n oraşe, e vorba de generarea şi evaluarea unui număr de soluţii egal cu numărul permutărilor de n obiecte (de fapt, de n-1, deorece primul oraş, A, este fixat). Ori, numărul permutărilor de n obiecte este de n!, ceea ce este un număr foarte-foarte mare, chiar pentru valori destul de mici ale lui n (de exemplu, 5! = 120, în timp ce 10! = 29.030.400, şi 20! = 2.432.902.008.176.640.000 ... cam mult). 

Cu siguranţă, această idee este destul de proastă, iar acesta este un exemplu clar în care matematica şi informatica au abordări diferite. Pentru un matematician, care nu este foarte interesat de resursele implicate în de rezolvarea unei astfel de probleme, un astfel de algoritm poate fi acceptabil, în schimb pentru un informatician, cu siguranţă, nu este. 

O altă metodă foarte generală care poate fi folosită pentru rezolvarea unei astfel de probleme este cea denumită backtracking.Bactrackingul se aplică problemelor care solicită construirea unui şir (o variabilă indexată) care trebuie să răspundă unei anumite condiţii de optimalitate – de exemplu, în cazul nostru, „costului minim”, fiecare din cele n variabile individuale putând lua valori dintr-o mulţime determinată. Din păcate, nici backtrackingul nu este o metodă prea eficientă. Practic, în cazul nostru, backtrackingul nu reprezintă altceva decât o îmbunătăţire minoră faţă de forţa brută!

O altă strategie ar fi aceea bazată pe algoritmi genetici.

Dar, mai multe detalii despre backtracking, algoritmi genetici si altele asemenea, altădată!  

Niciun comentariu:

Trimiteți un comentariu