Problema Comis-Voiajorului [609988]

Problema Comis-Voiajorului

Problema Comis-Voiajorului este definit ă astfel:

Fie G = (V, E) este un graf neorientat în care oric are dou ă vârfuri diferite ale grafului
sunt unite printr-o latur ă căreia ii este asociat un cost strict pozitiv. Cerin /uni0163a este de a determina
un ciclu care începe de la un nod aleatorie a grafu lui, care trece exact o dat ă prin toate celelalte
noduri și care se întoarce la nodul ini /uni0163ial, cu condi /uni0163ia ca ciclul sa aiba un cost minim. Costul
unui ciclu este definit ca suma tuturor costurilor ata șate laturilor ciclului.

Numele problemei provine din analogia cu un vanzato r ambulant care pleac ă dintr- un
ora ș, care trebuie s ă viziteze un num ăr de ora șe dat și care apoi trebuie s ă se întoarc ă la punctul
de plecare, cu un efort minim (de exemplu timpul mi nim, caz în care costul fiec ărei laturi este
egal cu timpul necesar parcurgerii drumului).
Prin urmare, fie-G = (V, E) un graf conectat neordo nat, definit de un set de noduri V și de
un set de laturi E.
Dac ă vom marca cu V '= {vi | i =1,…, n -1} set de nod uri asociate ora șelor care trebuie s ă
fie vizitate și dac ă vom marca cu v0 nodul care este asociat cu ora șul din care vanzator ambulant
pleaca (de baz ă), vom avea V = V ' ∪{v0 }.Am marca, de obicei, lungimea laturii dintre nodurile
vi și vj cu lij și costul asociat parcurgerii laturii dintre vi si vj cu cji.

Marginile colorate în verde, ne dau un ciclu care porneste de la nodul A, având costul urm ător:
1 +4 +1 +2 +5 = 13 pe calea A-B-D-C-E-A

Marginile colorate în ro șu ne dau un ciclu care porneste de lanodul B, având costul urm ător:
1 +2 +1 +3 +3 = 10 pe calea B-A-C-D-E-B

Prin urmare, al doilea ciclu este mai bun ca prima, având în vedere costul redus.

Metode de solu /uni0163ionare

Căile principale de abordare ale problemelor de tipul « NP » sunt urm ătoarele :
o Algoritmi pentru g ăsirea solu /uni0163iilor exacte (ex. Backtracking – ace știa vor
func /uni0163iona rezonabil doar pentru problemele de dimensiuni relativi mici)
/square4 Prin metoda backtracking , orice vector solutie este construit progresiv,
incepand cu prima componenta si mergand catre ultim a, cu eventuale
reveniri asupra valorilor atribuite anterior.
/square4 Metoda backtracking urmareste sa evite generarea tu turor solutiilor
posibile, scurtandu-se astfel timpul de calcul.

o Născocirea metodelor euristice de rezolvare aproximativ ă a TSP (metode bune,
dar care nu pot fi considerate optime)
/square4 In situatiile in care pentru anumite problem comple xe, pentru a caror
rezolvare nu se cunosc algoritmi, sau acestia sunt ineficienti(timp
memorie, cost), se prefer utilizarea unor algoritmi care rezolva problema
data mult mai rapid, cu effort mic, insa nu ne va f urniza intotdeauna cea
mai buna solutie, cid oar solutii acceptabile, adic a solutii corecte care pot fi
eventual imbunatatite.
/square4 Prin algoritm euristic vom intelege un algoritm car e furnizeaza solutii bune
nu neaparat optime, care poate fi implementat rapid si furnizeaza rezultate
in timp util.
/square4 O idée frenvent ultilizata consta in descompunerea procesului de
determinare a solutiei in mai multe etape successiv e pentru care se poate
determina optimul local.

o Găsirea unor cazuri speciale pentru problem ă (Greedy )
/square4 În strategia backtracking c ăutarea solu /uni0163iei, adic ă vizitarea secven /uni0163ial ă a
nodurilor grafului solu /uni0163iilor cu revenire pe urma l ăsat ă, se face oarecum
“orbe ște” sau rigid, dup ă o regul ă simpl ă care să poat ă fi rapid aplicat ă în
momentul “p ărăsirii” unui nod vizitat. În cazul metodei (strategi ei) greedy
apare suplimentar ideea de a efectua în acel moment o alegere. Dintre toate
nodurile urm ătoare posibile de a fi vizitate sau dintre to /uni0163i pa șii urm ători
posibili, se alege acel nod sau pas care asigur ă un maximum de “cî știg”, de
unde și numele metodei: greedy = lacom .
/square4 Aparent aceast ă metod ă de căutare a solu /uni0163iei este mai eficient ă, din
moment ce la fiecare pas se trece dintr-un optim (p ar /uni0163ial) într-altul. Totu și,
ea nu poate fi aplicat ă în general ci doar în cazul în care exist ă certitudinea
alegerii optime la fiecare pas, certitudine rezulta t ă în urma etapei
anterioare de analiz ă a problemei.

Variante de rezolvare

1.Metoda backtracking

1.1 Considerente teoretice

Metoda backtracking urmareste sa evite generarea tu turor solutiilor posibile, scurtandu-se
astfel timpul de calcul.
Componentele vectorului x primesc valori in ordinea crescatoare a indicilor. Aceasta
inseamna ca lui x k nu i se atribuie valori decat dupa ce x 1, …,x k-1 au primit valori care nu contrazic
conditiile interne. Mai mult, valoarrea lui x k trebuie aleasa astfel incat x 1,…,x k sa indeplineasca si
ele anumite conditii, numite conditii de continuare , care sunt strans legate de conditiile interne.
Astfel, daca in exemplul dat componentele x 1 si x 2 au primit amandoua valoarea X, atunci
lui x 3 nu i se mai poate atribui aceasta valoare (pentru a nu incalca restrictia ca numarul maxim
de pronosticuri X sa fie cel mult 2).
Neindeplinirea conditiilor de continuare exprima fa ptul ca oricum am alege x k+1 ,…x n, nu
vom obtine o solutie (deci conditiile de continuare sunt strict necesare pentru obtinerea unei
solutii). Ca urmare se va trece la atribuirea unei valori lui x k doar cand conditiile de continuare
sunt indeplinite. In cazul neindeplinirii conditiil or de continuare, se alege o noua valoare pentru
xk sau, in cazul cand multimea finita de valori V k a fost epuizata, se incearca sa se faca o noua
alegere pentru componenta precedenta x k-1 a vectorului, micsorand pe k cu o unitate etc. Ace asta
revenire da numele metodei, exprimand faptul ca atu nci cand nu putem avansa, urmarim inapoi
secventa curenta din solutie.
Trebuie observat ca in anumite cazuri, faptul ca v 1,v 2,…,v k-1 satisfac conditiile de
continuare nu este suficient pentru a garanta ca se va obtine o solutie alei ca re prime k-1
componente coincid cu aceste valori. De pilda, chia r daca x 1 si x 2 sunt X, iar x 3 este 1 (deci aceste
valori indeplinesc conditiile de continuare curente ), totusi (X,X,1,1) nu este solutie.
Alegerea conditiilor de continuare este foarte impo rtanta, o alegere buna ducand la o
reducere substantiala a numarului de calcule. In ca zul ideal, conditiile de continuare ar trebui sa
fie nu numai necesare , dar si suficiente pentru obtinerea unei solutii. De obicei insa, ace stea
reprezinta restrictia conditiilor interne la primel e k componente ale vectorului. Evident, conditiile
de continuare in cazul k=n sunt chiar conditiile in terne.
Prin metoda backtracking , orice vector solutie este construit progresiv, incepand cu prima
componenta si mergand catre ultima, cu eventuale reveniri asupra valorilor atribuite anterior.
Reamintim ca x 1,x 2,…,x n primesc valori in multimile v 1,….,v n .

1.2 Pseudocod

Semnificatia variabilelor:
x[10]=vectorul care se prelucreaza pentru a obtine solutia
a[10][10]=matricea de adiacenta a grafului
n=numaruld e noduri
m=nr de muchii
i,j=variabile contor
k=da numarul nodului curent
ok=variabila din fct cond, ia doar valorile 0 sau 1 si are rol de adevar
b,y=varibile cu care stabilim unde se pune in matri ce.

<1> Procedure cond (int k)
| ok /barb2left1
| daca(a[x[k]][x[k-1]]=0)
| ok /barb2left0
| daca (k=n si a[x[k]][x[1]]=0)
| ok /barb4left0
| pentru i=1,n
| daca (x[k]=x[i])
| ok /barb2left 0
| return ok
|__#

<2> Procedure back ()
| pentru i=1,n
| x[i] /barb2left 0
| k /barb2left 2
| x[1] /barb2left1
| cat timp k>1
| | daca (k=n+1)
| | | pentru i=1,n
| | | | scrie x[i]
| | | |__#
| | | k /barb2leftk-1
| | |____#
| | altfel
| | | daca x[k]< n
| | | x[k] /barb2leftx[k]+1
| | | daca (cond(k))
| | | k /barb2left k++
| | | altfel
| | | |x[k] /barb2left0
| | | | k /barb2leftk-1
| | | |___#
| | |____#
| |
| |____#
|_______#

<3> Void main()
| scrie “n=”
| citeste n
| pentru i=1,n
| pentru j=1,n
| a[i][j] /barb2left0
| scrie “m=”
| citeste m
| pentru j=1,m
| | citeste b
| | citeste y
| | a[b][y] /barb2lefta[y][b] /barb2left1
| |____#
| x[n+1]=1
| back()
|_____#

<3> In functia main() se citesc datele principale, n e ste numarul de noduri ale grafului, m este
numarul de muchii ce se vor forma. Pentru fiecare m uschie formam matricea de adiacenta
inscriind 1 la intersectia coordonatelor b si y. In fapt definim daca exista drum de la b la
y.Matricea astfel formata este una simetrica. Initi alizam x[n+1] cu 1 pentru ca drumul comis
voiajorului va pleca din 1 si se va intoarce tot ai ci.. Apelam functia care foloseste metoda
backtraking ->back().

<2> In functia back() prin apeluri recursive incercam sa formam drumurile posibile. Tot aici se
apeleaza si functia cond care retine conditiile de continuare. Ea retuneaza o viatabila ok care daca
este 0 k se decrementeaza si se cauta alta solutie pentru satisfacerea cerintei.
Intai se intitializeaza intr-un for vectorul x cu 0 pentru a nu avea surprize de la solutiile
precedente,k primeste valoarea 2 pentru ca vom caut a un al doilea element iar x[1] devine 1, el
fiind si punctul de plecare. Retinem insa ca din fu nctia main avem si al n+1-elea element din
vector tot pe 1 initializat.
Cat timp k>1 testam prima data daca am ajuns la fi nal(k=n), caz in care se vor afisa
valorile vectorului, valori care reprezinta una din solutiile grafului. In caz contrar verificam daca
mai avem noduri nevizitate, daca da, incrementam pe x[k] si intram in functia cond. Daca
valoarea returnata de functia cond este una pozitiv a k va fi la randul lui incrementat si trecem pe
alta pozitie a vectorului x[k] ce trebuie completat , altfel x[k] primeste valoarea 0 si k este
decrementat.

<1> Functia cond() este compusa din 3 „if”-uri si rep rezinta conditiile de continuare. In prima
faza variabila care va fi returnata este pusa pe 1, ea putand lua valoarea 0 in cazul in care una din
cele 3 conditii este indeplinita. In cazul in care retuneaza 0 nu avem conditii de continuare.
Prima conditii face referire la testarea vecinatat ii oraselor selectate existand posibilitatea
de a nu avea muchie intre ele.
Urmatoarea conditie verfica daca primul nod este d iferit de ultimul.
Ultima conditie din functie testeaza daca nu a mai fost vizitat orasul selectat.

1.3 Exemplu detaliat

Explicatii, date Felul cum se completeaza graful.
Input:
n=4
m=5
b=1,2,4,3,1;
y=2,4,3,1,4;
Dupa care se intra in fct back

Graful creat cu datele de mai sus arata
in felul urmator:

Pas 1: se initializeaza X la 0 Nu avem graf
Pas 2. X=0,1,0,0,0,0,0,0,0

Vectorul arata ca se pleaca din 1, se va
ajung la sfarsit in 1 si ne pozitionam pe
primul element cautand un succesor.

Pas 3: x=0,1,2,0,0,0,0,0,0

Marcam primul nod ca fiind vizitat si
ne indreptam spre nodul 2 pe care il
adaugam in vector.

Pas 4: x=0,1,2,4,0,0,0,0,0

Singurul vecin a lui 2 spre care avem
legatura este cel pe care il adaugam in
vector la acest moment. Avem nodurile
1,2 vizitate.

Pas 5: x=0,1,2,4,3,1,0,0,0

Marcam nodul 4 ca vizitat si adaugam
in vector nodul 3

Pas 6: x=0,1,2,4,3,1,0,0,0

Ne intoarcel in 1, incheiem ciclul din
care am plecat, nodul 3 devine vizitat
iar graful a fost complet parcurs.

Pas 7: se tipareste vectorul x cu valorile
existente Valorile lui x sunt 1,2,4,3,1.

1.4 Complexitate
Toti algoritmii de calcul pentru problema comis voi ajorului sunt exponentiali.
Complexitatea de calcul al algoritmului este patrat ica. Totusi pentru un volum mare de date
rezolvarea prin backtraking devine intractabila.Sol utiile obtinute depasesc cu cel mult 7-25%
lungimea drumului optim dupa diversi autori.
Algoritmul backtracking pentru problema comis-voiaj orului are o punere în aplicare mai
complexa, deoarece calculeaza practic toate posibil it ă/uni0163ile de recuren /uni0163ă

2.Metoda Greedy

2.1 Considerente teoretice

În cazul metodei (strategiei) greedy apare suplimen tar ideea de a efectua în acel moment
o alegere. Dintre toate nodurile urm ătoare posibile de a fi vizitate sau dintre to /uni0163i pa șii urm ători
posibili, se alege acel nod sau pas care asigur ă un maximum de “cî știg”, de unde și numele
metodei: greedy = lacom . Evident că în acest fel poate s ă scad ă viteza de vizitare a nodurilor –
adic ă a solu /uni0163iilor ipotetice sau a solu /uni0163iilor par /uni0163iale – prin ad ăugarea duratei de execu /uni0163ie a
subalgoritmului de alegere a urm ătorului nod dup ă fiecare vizitare a unui nod. Exist ă îns ă
numero și algoritmi de tip greedy veritabili care nu con /uni0163in subalgoritmi de alegere.Asta nu
înseamn ă că au renun /uni0163at la alegerea greedy ci, datorit ă “scurt ăturii” descoperite în timpul etapei
de analiz ă a problemei, acei algoritmi efectueaz ă la fiecare pas o alegere f ără efort și în mod
optim a pasului (nodului) urm ător. Aceast ă alegere, dedus ă în etapa de analiz ă, conduce la
maximum de“profit” pentru fiecare pas și scurteaz ă la maximum drumul c ătre solu /uni0163ia căutat ă.
Dezavantajul acestei metode este c ă, la majoritatea problemelor dificile, etapa de ana liz ă
nu poate oferi o astfel de “pist ă optim ă“ către solu /uni0163ie. Un alt dezavantaj al acestei strategii este c ă
nu poate să conduc ă către toate solu /uni0163iile posibile ci doar c ătre solu /uni0163ia optim ă (din punct de vedere
al alegerii efectuate în timpul c ăut ării solu /uni0163iei), dar poate oferi toate solu /uni0163iile optime echivalente.
Conform strategiei greedy, vom construi ciclul pas cu pas, adaugand la fiecare iteratie cea mai
scurta muchie disponibila cu urmatoarele proprietat i:
� nu formeaza un ciclu cu muchiile deja selectate (exceptand pentru ultima muchie aleasa,
care completeaza ciclul)
� nu exista inca doua muchii deja selectate, astf el incat cele trei muchii sa fie incidente in
acelasi varf
La:
De la: 2 3 4 5 6
1 3 10 11 7 25
2 6 12 8 26
3 9 4 20
4 5 15
5 18

Tabelul 6.4 Matricea distantelor pentru problema co mis-voiajorului.

De exemplu, pentru sase orase a caror matrice a dis tantelor este data in Tabelul 6.4, muchiile se
aleg in ordinea: {1, 2}, {3, 5}, {4, 5}, {2, 3}, {4 , 6}, {1, 6} si se obtine ciclul (1, 2, 3, 5, 4, 6, 1)
de lungime 58. Algoritmul greedy nu a gasit ciclul optim, deoarece ciclul (1, 2, 3, 6, 4, 5, 1) are
lungimea 56.

2.2 Pseudocod

Algoritmul greedy construie ște o singur ă cale incepand de la un noddat.

În ambele abordarea lacomi și euristic ă noi trebuie să utilizeze oprocedur ă esen /uni0163ial care alege
ceea ce margine pentru a ad ăuga lacalea. Este nevoie de trei parametri:
• ultima – întreg, care ne informeaz ă în cazul în care începe de lamarginea
• min- pointer întreg – puncte de la costul de mar ginea ad ăugate prin procedura
• j_min – pointer întreg – puncte la indicele de no d sfâr șitul margineaad ăugate

procedure choose(integer last, integer ptr min, int eger ptr j_min )
for j = 0 to n
| if node j is not visited
| | if distance[last,j]<*min
| | | *min=distance[last,j]
| | | *j_min=j
| | |_______#
| |___#
|____#
Aceast ă procedur ă este utilizat ă pentru a genera calea necesare. La fiecare pas se adaug ă un alt
nod pe nod vizitat ultima dat ă, și dac ăsau nu un nod este deja în aceast ă cale.

2.3 Exemplu detaliat

Pas1.Conditii initiale
A B
D C
E 10
5 11
9
2
8 4
1 3 6

A B
D C
E 10
5 11
9
2
8 4
1 3 6 Pas2.Am ales pentru prima nodul
A (am putea alege orice alt nod
dac ă nusuntem în mod special
instruit altfel)
Pas3.Cea mai scurt ă distan /uni0163ă de
la A este de 2 (marginea A-E)
Pas4.Cea mai scurt ă distan /uni0163ă de
la E este 3 (marginea E-B) A B
D C
E 10
5 1
9
2
8 4
1 3 6
A B
D C
E 10
5 1
9
2
8 4
1 3 6

Pas5.Cea mai scurt ă distan /uni0163ă de
la B este 4 (marginea B-D)
Pas6.Cea mai scurt ă distan /uni0163ă de
la D este de 1 (marginea D-C)
Pas7.Adauga restul de marginea
C-O lungime de11

A B
D C
E 10
5 1
9
2
8 4
1 3 6
A B
D C
E 10
5 1
9
2
8 4
1 3 6
A B
D C
E 10
5 1
9
2
8 4
1 3 6

2.4 Complexitate

În teoria complexit ă/uni0163ii, versiunea finala de PCV apar /uni0163ine clasei de probleme NP-complete. Astfel,
se presupune c ă nu exist ă nici un algoritm eficient pentru rezolvarea PCV. C u alte cuvinte, este
posibil ca in cel mai r ău caz de rulare in ceea ce priveste timpul pentru o rice algoritm, pentru
PCV cre ște exponen /uni0163ial cu num ărul de ora șe.
Solu /uni0163ia cea mai direct ă ar fi să încerca /uni0163i toate permut ări ( combinatii ordonate) și sa vedeti
care este mai eficient (utilizând func /uni0163ia de căutare brute force). Timpul de rulare pentru aceast ă
abordare se afl ă într-un factor polinomial O (n!), factorialul num ărului de ora șe, astfel încât
aceast ă solu /uni0163ie devine imposibila chiar si pentru numai 20 de or a șe. Una dintre primele aplicatii
de programare dinamic ă este un algoritm care rezolv ă problema in timp O(n22n).
3.Metoda Euristica

3.1 Algoritmi euristici

În situa /uni0163iile în care pentru anumite problem complexe, pentr u a căror rezolvare nu se
cunosc algoritmi, sau ace știa sunt ineficien /uni0163i(timp, memorie, cost), se prefer utilizarea unor
algoritmi care rezolv ă problema data mult mai rapid, cu effort mic, îns ă nu ne va furniza
întotdeauna cea mai bun ă solu /uni0163ie, ci doar solu /uni0163ii acceptabile, adic ă solu /uni0163ii corecte care pot fi
eventual îmbun ătă/uni0163ite.
Prin algoritm euristic vom în /uni0163elegeun algoritm care furnizeaz ă solute bune , nu neap ărat
optime, care poate fi implementat rapid și furnizeaz ă rezultate în timp util.
O idee frecvent utilizat ă const ă în descompunerea procesului de determinare a solu /uni0163iei în
mai multe etape successive pentru care se poate det ermina optimul local .

Optimul global nu poate fi obtinut intotdeauna prin determinari successive ale optimului
local, deci nu se poate aplica metoda Greedy, doar o strategie de tip euristic.
In practica se gasesc de multe ori solutii aproxima tive, mai ales daca algoritmul se
foloseste de putine ori si efortul de determinare a l solutiei optime este mai mare decat beneficial
obtinut.
O metoda euristica poate sa imparta rezolvarea in m ai multe etape, se determina optimal
din fiecare etapa (pana in acel moment) urmarind pr in aceasta ca rezultatul final sa fie cat mai
bun. Daca este posibil sa determinam rapid mai mult e solutii, atunci rezultatul dat va fi cel mai
bun dintre acestea.
La scrierea unui algoritm euristic vom apica doar c onditiile simple dar necesare pentru o
solutie corecta, care eventual va mai fi imbunatati ta.

•Strategia : se allege întotdeauna cea mai apropiat ă localitate(dintre cele nevizitate).

•Imbun ătă/uni0163ire : deoarece un traseu este un circuit închis, putem considera ca punctde plecare
oricare dintre localit ă/uni0163i (traseul optim nu depindede localitateade start). Pentru fiecare localitate
considerate ca localitate de plecare, se determin ă traseul preferat , apoi dintre aceste k trasee
corecte se determin ă traseul cel mai bun (de lungime minim ă) daca rezultat final (care nu este
neap ărat traseul optim ). Evident că traseul final va fi ref ăcut astfel încât s ă aib ă ca localitate de

start localitatea de domiciliu a comis voiajorului (în exemplul dat am considerat toate cele n
variante, deci k = n ).

3.2 Pseudocod

Algoritmul euristic construieste n trasee (n = num ărul de noduri), și il păstreaz ă pe
cel care ofera rezultatul optim, dar cu un cost de complexitate.

for nodes = 1 to n
| call greedy subroutine
| if current_cost>best_cost
| | best_cost=current_cost
| | save current_path
| |_______#
|____#

3.3 Exemplu detaliat

Nodul de start : A

Calea construita:
A-E-B-D-C-A

Cost: 21 A B
D C
E 10
5 1
9
2
8 4
1 3 6

Nodul de start : B

Calea construita:
B-E-A-D-C-B

Cost: 20

Nodul de start : C

Calea construita:
C-D-B-E-A-C

Cost: 21

Nodul de start : D

Calea construita:
D-C-B-E-A-D

Cost: 20 A B
D C
E 10
5 11
9
2
8 4
1 3 6
A B
D C
E 10
5 1
9
2
8 4
1 3 6
A B
D C
E 10
5 11
9
2
8 4
1 3 6

Nodul de start : E

Calea construita:
E-A-D-C-B-E

Cost: 20

Cel mai bun rezultat ob /uni0163inut pornind de la nodul B (de asemenea, de la nodu rile D și E, dar
primul nod care conduce la un rezultat optim este s tocat).

3.4 Complexitate

Metoda euristica are acelasi principiu ca si metoda Greedy dar în loc sa porneasca de la un nod
dat și sa construiasca calea, începe de la fiecare dintr e noduri și preia în cele din urm ă cea mai
bun ă solu /uni0163ie.

A B
D C
E 10
5 11
9
2
8 4
1 3 6

//IMPLEMENTARE BACKTRACKING
#include<conio.h>
#include<stdio.h>
int x[10],a[10][10],n,m,i,j,k,ok,b,y;
int cond(int k) //Functia testeaza conditia de opri re
{ ok=1; //Consideram initial ok=1 si daca este cazu l il modificam ulterior
if(a[x[k]][x[k-1]]==0) //testeaza daca 2 orase se lectate sunt vecine
ok=0;
if((k==n)&&(a[x[k]][x[1]]==0)) //Testez daca pri mul oras este diferit de ultimul
ok=0;
for(i=1;i<k;i++)
if(x[k]==x[i]) //testez sa nu mai fi vizitat or asul
ok=0;
return (ok); //returnez pe k pentru a putea fi tes tat in fct back
}
void back()
{ for(i=1;i<=n;i++)
x[i]=0;
k=2;
x[1]=1;
while(k>1)
if(k==n+1) // daca am vizitat toate nodurile af isez vectorul
{
for(i=1;i<=n+1;i++) // parcurg vectorul solutie si il afisez
printf("%d", x[i]);
printf("\n");
k–;
}
else
if(x[k]<n) //daca x[k]<n inseamna ca mai sunt nodu ri nevizitate un
//merita testate conditiile de continuare
{
x[k]=x[k]+1;
if(cond(k)) //interoghez functia cond pentru a ve dea daca mai am
//solutii
k++; //daca am solutii il incrementez pe k p entru a cauta
// mai eparte
}
else //altfel decrementez pe k
{
x[k]=0;
k–;
}
}
void main()
{
printf("n="); // citesc numarul de puncte din graf

scanf("%d",&n);
//initializam matricea
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
printf("m="); //citesc numarul de muchii din graf
scanf("%d",&m);
for(j=1;j<=m;j++) // marchez in matrice arcele graf ului
{
printf("x=");
scanf("%d",&b);
printf("y=");
scanf("%d",&y);
a[b][y]=1;
a[y][b]=1;
}
x[n+1]=1; //initializez ultimul element cu 1
back();
getch();
}

//IMPLEMNTARRE GREEDY
#include <stdio.h>
#define MAXNUM 30 /* Maximum number of points */
#define MINIMUM 10000 /* Initial value when searchi ng for minimum */
int n; /* Number of points */
int d[MAXNUM][MAXNUM]; /* Distance matrix */
int path[MAXNUM]; /* Path of the traveling salesman ; contains the indexes of the visited
points*/
int visited[MAXNUM]; /* Array that contains informa tion about what points have been visited*/

/*Function that chooses which point will be visited next */
void choose(int last, int *min, int *j_min) {
int j;
/* The minimum distance to a point not yet visited is searched */
*min = MINIMUM; *j_min = -1;
for (j=0; j<n; j++)
if (!visited[ j ]) {
if (d[ last ][ j ] < *min) {
*min = d[ last ][ j ];
*j_min = j;} }
}

int main(void) {

FILE *fin;

int i, j, index, count, cost, min, j_min,save_cost =MINIMUM,save_path[MAXNUM];
fin = fopen("euristic.txt", "rt"); if (!fin) {
printf("ERROR: cannot open file.\n");
return -1; }
fscanf(fin, "%d", &n); /* Read input from file */
for (i=0; i<n; i++)
for (j=0; j<n; j++)
fscanf( fin, "%d", &(d[ i ][ j ]));
printf("%d points.\n", n);
printf("Distances between points:\n");
for (i=0; i<n; i++) {
for (j=0; j<n; j++)
printf("%d ", d[ i ][ j ]);
printf("\n"); }
printf("\n");

/* First point visited is of index 0 */
for (index=0;index<n;index++){
printf("We start at point %d\n",index+1);
min=MINIMUM;
j_min=MINIMUM;
for (i=0; i<n; i++){
visited[i] = 0; /* Initially no point is visited */
path[i]=0;
}
path[0] = index; visited[index] = 1;
count = 1; cost = 0;
/* The rest of the points are visited */
for (i=0; i<n-1; i++) {
/* We choose next point to be visited */
choose(path[count-1], &min, &j_min);
printf("Connected (%d, %d) of cost %d.\n",path[c ount-1]+1, j_min+1,
min);
path[count] = j_min;
visited [j_min ] = 1;
count++;
cost += min;
}
/* We go through the path from the last visited p oint
to the first one and we update the total cost*/
cost += d[path[n-1]][index];
/* Display chosen path */
printf("\nPath has cost %d and is:\n", cost);
for (i=0; i<n; i++)
printf("%d ", path[i]+1);
printf("%d\n\n\n\n",index+1);
if (cost<save_cost){

for(i=0;i<n;i++)
save_path[i]=path[i];
save_cost=cost;
}
}
/* Display chosen path */
printf("\nShortest path starts at point %d has cos t %d and is:\n", save_path[0],save_cost);
for (i=0; i<n; i++)
printf("%d ", save_path[i]+1);
printf("%d\n\n\n\n",save_path[0]);
return 0;

}