Problema Comis-Voiajorului este definită astfel: Fie G = (V, E) este un graf neorientat în care oricare două vârfuri diferite ale grafului sunt unite printr-o latură căreia ii este asociat un cost strict pozitiv. Cerinţa este de a determina un ciclu care începe de la un nod aleatorie a grafului, care trece exact o dată prin toate celelalte noduri şi care se întoarce la nodul iniţial, cu condiţia 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 vanzator 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 minim, caz în care costul fiecărei laturi este egal cu timpul necesar parcurgerii drumului).
Prin urmare, fie-G = (V, E) un graf conectat neordonat, 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 noduri 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.
#include<iostream>
#include<cmath>
int st[20],n,k,a[10][10];
void init()
{st[k]=1;}
int succesor()
{if (st[k]<n)
{st[k]++;
return 1;
}
else return 0;}
int valid()
{if( a[st[k-1]][st[k]]==0) return 0;
for(int i=1;i<k;i++)
if(st[i]==st[k] ) return 0;
if((k==n) && (a[1][st[k]]==0)) return 0;
return 1;}
int sol()
{return (k==n);}
void tipar()
{for(int i=1;i<=n;i++) cout<<st[i]<<" ";
cout<<endl;
}
void bkt()
{int as;k=2;
init();
while(k>0)
{
do {} while ((as=succesor()) && !valid());
if (as)
if (sol()) tipar();
else {k++;init();}
else k--;
}
}
void main()
{cout<<"numarul de orase=";cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>a[i][j];
st[1]=1;
bkt();
}