عنوان پروژه

 پیاده سازی مسئله فروشنده دوره گرد TSP زبان سی 

نوع فایل

فرمت

سورس زبان سی

CPP , EXE

پیش نمایش از سورس کد پروژه

example:
۲
[۰]——-[۱]
| \۴ /|
| \ / |
۳| /\ |۳
| ۶/ \ |
[۳]——-[۲]
۱

inputs:
infinity:999
no. of cities: 4
no. of paths:6

S D Dist
path0:0 1 2
path0:0 2 4
path0:0 3 3
path0:1 2 3
path0:1 3 6
path0:2 3 1
*/

#include<stdio.h>
#include<conio.h>
#define ALL -1
#define MAXCITIES 10

enum BOOL{FALSE,TRUE};
long*visited;
long*min_circuit;
long*ham_circuit;
long min_circuit_length;

int n;
long matrix[MAXCITIES][MAXCITIES];

long INFI;

void reset_min_circuit(int s_v_id)
{
min_circuit[0]=s_v_id;
for(int i=1;i<n;i++) min_circuit[i]=-1;
}

void set_visited(int v_id,BOOL flag)
{
if(v_id==ALL) for(int i=0;i<n;i++) visited[i]=flag;
else visited[v_id]=flag;
}

void SET_HAM_CKT(long pl)
{
ham_circuit[0]=pl;
for(int i=0;i<n;i++) ham_circuit[i+1]=min_circuit[i];
ham_circuit[n+1]=min_circuit[0];
}

long get_valid_circuit(int s_v,int s_n_v)
{
int next_v,min,v_count=1;
long path_length=0;
min_circuit[0]=s_v;
min_circuit[1]=s_n_v;
set_visited(s_n_v,TRUE);
path_length+=matrix[s_v][s_n_v];
for(int V=s_n_v;v_count<n-1;v_count++)
{ min=INFI;
for(int i=0;i<n;i++)
if( matrix[V][i]<INFI && !visited[i]
&& matrix[V][i]<=min
)
min=matrix[V][next_v=i];
set_visited(next_v,TRUE);
V=min_circuit[v_count+1]=next_v;
path_length+=min;
}
path_length+=matrix[min_circuit[n-1]][s_v];
return(path_length);
}

void main()
{
clrscr();
printf(“Make sure that infinity value < sum of all path distances\nSet Infinity at (signed long):”);
scanf(“%ld”,&INFI);
int pathcount,i,j,source,dest;
long dist=0;
long new_circuit_length=INFI;
printf(“Enter no. of cities(MAX:%d):”,MAXCITIES);
scanf(“%d”,&n);
printf(“Enter path count:”);
scanf(“%d”,&pathcount);

printf(“Enter paths:< source_id destination_id distance >\n ids varying from 0 to %d\n”,n-1);

for(i=0;i<n;i++)
for(j=0;j<n;j++)
matrix[i][j]=INFI;

}

======