Problema Comis Voiajorului

Problemă:

Un comis voiajor pleacă din oraşul 1 să prezinte produsele unei firme în toate oraşele din regiunea sa. El are la dispoziţie harta regiunii, pe care sunt marcate legăturile directe dintre oraşe şi distanţele dintre acestea. Se cere realizarea unui program prin care să se determine un traseu cât mai scurt, astfel încât comis-voiajorul să viziteze toate oraşele din regiune, să nu treacă de mai multe ori prin acelaşi oraş şi să se întoarcă în oraşul 1.

Indicație de rezolvare:

Numărul oraşelor pe care trebuie să le viziteze comis-voiajorul se stochează în variabila nroraşe. Informaţiile despre legăturile dintre oraşe se stochează în variabila nrmuchii (care conţine numărul legăturilor directe între oraşe) şi în tabloul a, care este o matrice simetrică cu 2*nrmuchii elemente nenule. Toate aceste date se citesc din fişierul oraşe.in, în funcţia citire(). Traseul, adică succesiunea oraşelor prin care trece comis-voiajorul, se va reţine în vectorul t. Pentru a nu trece de mai multe ori prin acelaşi oraş, vom utiliza un vector vizitat, cu nroraşe componente, în care vizitat de i este 1 dacă oraşul i a fost vizitat şi 0 în caz contrar. Când obţinem un traseu, îl comparăm cu traseul de lungime minimă obţinut până la momentul respectiv. Acest traseu de lungime minimă se va păstra în vectorul tmin. Variabila globală lgmin reţine lungimea traseului curent. Când ne deplasăm într-un oraş adunăm distanţa până la oraşul respectiv la lg, când eliminăm un oraş de pe traseu scădem distanţa până la acesta din lg. Dacă la un moment dat lg>lgmin nu mai continuăm generarea traseului curent.
Condiţiile interne sunt următoarele :
 t[i] є {1,2, …, n } pentru orice i = 1, 2, .., n (traseul conţine cele n oraşe)
 t[1]=1 (comis-voiajorul pleacă din oraşul 1)
 a[t[i] ,t[i+1]] ≠ 0 pentru orice i = 1, 2, …, n-1 (între două oraşe vizitate
succesiv trebuie să existe legătură directă)
 t[i] ≠ t[j], pentru orice i ≠j, i, j=1, 2, …, n (comis-voiajorul nu trece de două
ori prin acelaşi oraş)
 a[1, t[n]] ≠ 0 (trebuie să existe legătură directă între oraşul de plecare şi
ultimul oraş vizitat).

Implementare:

 

Cod Sursa C++

// ComisVoiajorCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int nrorase, nrmuchii, k, i, j;
//nrorase = numarul de orase pe care trebuie sa le viziteze comis-voiajorul
//numarul legaturilor directe intre orase
//k,i,j sunt variabile de lucru
float a[50][50], lg, lgmin, lginf, d, s;
//a este matricea de adiacenta a grafului;
int t[50], tmin[50], vizitat[50];
//vectorul t pastreaza ordinea in care comis-voiajorul viziteaza orasele
//vectorul tmin va retine traseul de lungime minima
//vizitat[i] va fi: 0 daca orasul i nu a fost vizitat si 1 in caz contrar
void citire()
//citirea datelor de intrare
{
	cout << "numar de orase: ";
	cin >> nrorase;
	cout << "numar de muchii: ";
	cin >> nrmuchii;
	//la prima citire se preiau valorile pentru nrorase si nrmuchii
	for (k = 1; k <= nrmuchii; k++) 
	{ 
		cout << "primul oras: ";
		cin >> i;
		cout << "al doilea oras: ";
		cin >> j;
		cout << "distanta dintre cele doua orase: ";
		cin >> d;
		a[i][j] = d; 
		a[j][i] = d; 
	}
	//urmatoarele nrmuchii citiri preiau distanta dintre orasele i si j
	//si o plaseaza in a[i,j] si a[j,i]
}
void init1()
//in matricea de adiacenta se pune 1.0 pe toate pozitiile
{
	for (i = 1; i <= nrorase; i++)
	for (j = 1; j <= nrorase; i++)
		a[i][j] = 0.;
}
float infinit()
//functia intoarce suma lungimilor muchiilor efective + 1
//
{
	s = 0;
	for (i = 1; i <= nrorase; i++)
	for (j = 1; j <= nrorase; j++) 
		s += a[i][j]; 
	s++;
	return s;
}
void afisare()
//afisarea rezultatelor
{
	if (lgmin == lginf) 
		printf("Nu exista solutii pentru acest caz!\n");
	else
		
	{
		printf("\nCircuitul cel mai scurt are lungimea %.0f \n", lgmin);
		printf("si este format din orasele: \n\n");
		for (i = 1; i <= nrorase; i++)
			printf("%d ", tmin[i]);
		printf("%d\n", tmin[1]); 
	}
	// se revine in orasul cu numarul 1
}
void copiere_traseu()
{
	for (i = 1; i <= nrorase; i++) 
		tmin[i] = t[i];
	//circuitul din t se pastreaza in tmin
}
void constr_traseu(int k)
// construirea traseului, pasul k
{
	if ((k - 1 == nrorase) && (a[1][t[nrorase]] != 0) && (lg + a[1][t[nrorase]]<lgmin))
		// prima conditie: traseul este complet
		// a doua conditie: se poate reveni in orasul 1 (exista muchie nenula)
		// a treia conditie: lungimea curenta este mai mica decat valoarea stocata in lgmin
	{
		copiere_traseu();
		//noul traseu devine cel minim
		lgmin = lg + a[1][t[nrorase]];
	}
	//noua lungime minima
	else
		//nu suntem la final; se construieste in continuare traseul
	for (i = 2; i <= nrorase; i++) if ((a[i][t[k - 1]] != 0) && (vizitat[i] == 0))
		//conditia verifica daca este posibila deplasarea in orasul i (care nu a fost inca vizitat)
	{
		t[k] = i; vizitat[i] = 1; lg += a[i][t[k - 1]];
		//se actualizeaza variabilele in cauza
		if (lg <= lgmin) constr_traseu(k + 1);
		vizitat[i] = 0; lg -= a[i][t[k - 1]];
	}
	//pasul de backtracking !!
}
void main()
{
	init1();
	citire();
	printf("PROBLEMA COMIS_VOIAJORULUI\n\n");
	printf("numar de orase =%d ", nrorase); printf("numare de muchii =%d \n\n", nrmuchii);
	printf("\nOrasele intre care exista legatura directa \nprecum si lungimile corespunzatoare sunt:\n\n");
	for (i = 1; i <= nrorase; i++){ for (j = 1; j <= nrorase; j++)printf("(%d,%d)=%3.0f ", i, j, a[i][j]); printf("\n"); }
	t[1] = 1;
	//se pleaca din orasul cu numarul 1
	vizitat[1] = 1;
	//acesta se marcheaza ca fiind vizitat
	lginf = infinit();
	//lginf contine o valoare foarte mare (comparativ cu lungimile muchiilor)
	lgmin = lginf;
	constr_traseu(2);
	//construirea traseului, incepand cu pozitia 2
	afisare();
	system("pause");
}
 

Rezultat: