برنامه TSP

[milad7091]

سلام به همه دوستان.
من برنامه TSP را با کمک یکی از دوستام نوشتم. گفتم بزارم اینجا شاید کسی نیاز داشته باشه.
این برنامه به صورت پویا حل شده. اساس کار این این است که نام فایل رو از ورودی میگیره و مسئله رو حل میکنه.

---------- Post added at 06:49 AM ---------- Previous post was at 06:46 AM ----------

//
#include <stdio.h> //جهت خواندن و نوشتن در فایل
#include <conio.h> //برای استفاده از تابع _getch
#include <math.h> //برای استفاده از تابع توان pow
#include <stdlib.h> //جهت تخصیص حافظه پویا

const int INIF = 999; //ثابتی که برای عدم وجود مسیر بین دو راس بکار می رود


int **w; //نگهدارنده وزن لبه ها
int **D; //نگهدارنده طول مسیرها
int **P; //آرایه نگهدارنده رئوس مسیرها

int *s; //نگهدارنده زیر مجموعه جاری
int *v; //مجموعه راسهای اصلی
long *T2; // مجموعه اعداد مبنای دو که با شماره راس ها متناظرند

long A; // نگهدارنده آدرس زیر مجموعه
long n; // نگهدارنده تعداد رئوس
long k; // تعیین تعداد اعضای زیر مجموعه


// این تابع اولین زیرمجموعه کا عضوی را ایجاد کرده
// و در مجموعه زیر مجموعه ها قرار می دهد
void F1_Subset(int u)
{
long n1;
A = 0;
for(n1=1; n1<=u; n1++)
{
s[n1] = v[n1+1]; // ان یک بعلاوه یک چون طبق الگوریتم پویا عضو اول نباید به شمار بیاید
A = A + T2[s[n1]];
}
}

// این تابع زیر مجموعه تعیین شده در تمپ آرر را به اندازه یک افراز به جلو می برد
int F1_Roll(int n2) //ان دو متغییر نگهدارنده رقم انتقالی می باشد
{
long A_indx = k-n2;

int t = s[A_indx];
if ( t < v[n-n2])
{
s[A_indx] = t + 1; //افزایش یک واحدی رقم سمت راست
}
else
{
if (n2+1 >= k)
{
return(1);
}
else
{
int r = F1_Roll(n2+1);
if (r==1){ return(1);}
s[k-n2]=s[k-(n2+1)] + 1; //افزایش یک واحدی ارقام سمت راست بخاطر اینکه از شمارش ترکیبی استفاده می شود
}
}
return(0);
}

// این تابع زیرمجموعه بعدی را در مجموعه زیرمجموعه ها قرار می دهد
// و آدرس آنرا نیز در آ قرار می دهد
int F1_NextSubset()
{
int r = F1_Roll(0); //بدست آوردن زیرمجموعه بعدی

if (r==0)
{
long n1;
A = 0; //محاسبه عدد منتاظر با زیر مجموعه بدست آمده
for(n1=1; n1<=k; n1++)
A = A + T2[s[n1]];
}
return(r);
}


// این تابع کوتاه ترین مسیر موجود در زیر مجموعه آ را برمیگرداند
// برای این کار یکی یکی اعضای آ را نادیده می گیرد و طول مسیر را بدون
// عضو نادیده گرفته شده محاسبه می کند و اگر از بقیه کوچکتر بود
// آنرا یاداشت می کند
int F2_Minimum(int i)
{
int j ,n2 ,tmp1 ,tmp2;
long IA;

tmp2 = INIF;
for (n2=1; n2<=k; n2++)
{
j=s[n2];
//
IA = A - T2[j]; // کسر عضو جی از آ به عبارت دیگر عضو جی را نادیده می گیرد
if (IA<0){IA=0;}
//
tmp1 = w[i][j]+D[j][IA]; // محاسبه طول مسیر با کسر جی

if (tmp1 < tmp2)
{
tmp2 = tmp1;
P[i][A] = j;
}
}
return (tmp2);
}

// این تابع مطابق با الگویتم برنامه نویسی پویا کوتاه ترین مسیر موجود در یک مجموعه ان عضوی
// را کشف و مقدار بهینه مسیر را برمی گرداند
long F2_DP() //Dynamic Programming
{
int i, n1, found;
A = 0;

//کپی کردن ستون اول ماتریس مجاور در ماتریس هزینه مسیر
//این عمل برای مجموعه آ هنگامی که تهی است انجام می شود
for(i=2;i<=n;i++)
D[i][A]=w[i][1];


//شروع الگوریتم اصلی
for (k=1; k<=n-2 ; k++)
{
//For All Subsets A C V-{1} Containing k Vertices.-----------------
F1_Subset(k); //بدست آوردن اولین زیر مجموعه با کا راس

do
{
for (i=2; i<=n; i++)
{
//------------- Found i
found = 0;
for (n1=1; n1<=k; n1++)
if (v[i]==s[n1]){found = 1; break;}
//---------------------
if (found==0)
D[i][A] = F2_Minimum(i);
}
} while (F1_NextSubset() == 0); // بدست آوردن زیر مجموعه بعذی
//------------------------------------------------------------------
}

F1_Subset(n-1); // V-{v1} بدست آوردن آخرین زیر مجموعه با ان منهی یک راس که برابر همان وی بجز یک است
D[1][A] = F2_Minimum(1);
return (D[1][A]);
}


// این تابع آرایه های مورد نیاز برنامه را ایجاد می کند
int F3_AllocArray()
{
int twoN=0; // نگهدارنده تعداد زیر مجموعه های مجموعه وی
int i, j, Ptr; // نگهدارنده اشاره گر آرایه پویای ایجاد شده

//v=new int[n]; //V Set ایجاد مجموعه راس ها
v = (int *) calloc(n,sizeof(int)); if (!v) return (1);

//T2=new long[n]; // ایجاد آرایه کد کننده مجموعه اصلی
T2 = (long *) calloc(n,sizeof(long)); if (!T2) return (1);


//s=new int[n]; // ایجاد آرایه زیر جموعه جاری
s = (int *) calloc(n,sizeof(int)); if (!s) return (1);


//w=new int*[n]; // ایجاد بعد اول ماتریس مجاور
w = (int *) calloc(n ,sizeof(int)); if (!w) return (1);

//D=new int*[n]; //ایجاد بعد اول برای ماتریس هزینه مجموعه ها
D = (int *) calloc(n ,sizeof(int)); if (!D) return (1);

//P=new int*[n]; //ایجاد بعد اول آرایه مسیرهای گذرانده شده
P = (int *) calloc(n ,sizeof(int)); if (!P) return (1);

twoN = pow(2,n); // محاسبه تعداد زیر مجموعه های مجموعه وی

for(i=1;i<=n;i++)
{
v[i]=i; //ایجاد مجموعه اصلی و شماره گذاری راس ها در آن
T2[i]=pow(2,i-1); //ایجاد مجموعه توان دوم جهت کد گذاری اعضای مجموعه
//
//w[i]=new int[n]; //ایجاد بعد دوم ماتریس مجاور
w[i] = (int *) calloc(n ,sizeof(int)); if (!w) return (1);

//D[i]=new int[twoN-1]; //ایجاد بعد دوم ماتریس هزینه مجموعه ها
D[i] = (int *) calloc(twoN-1 ,sizeof(int)); if (!D) return (1);

//P[i]=new int[twoN-1]; //ایجاد بعد دوم ماتریس مسیرهای گذرانده شده
P[i] = (int *) calloc(twoN-1 ,sizeof(int)); if (!P) return (1);
}
}

void F3_FreeArray()
{
//آزاد سازی حافظه استفاده شده
_freea(v);
_freea(s);
_freea(T2);
_freea(w);
_freea(D);
_freea(P);
}

// این تابع ماتریس مجاور را ار فایلی که تعیین می کنید می خواند و در ماتریس دابلیو قرار می دهد
int F3_ReadFile()
{
FILE *infile;
int i ,j ,vw ,r=0;
char strFName[10];

//گرفتن تعداد راس ها از کاربر
printf("\n\rSpecify Name: ");
scanf("%10s",strFName);

strcat(strFName,".txt");
//
if ((infile = fopen(strFName, "r")) == NULL)
{
printf("Error File '%s'\n\r", strFName);
r=1; goto Err1;
}
//
printf("Wait... Reading W Matrix...\n\r");

i = 1; j=1; vw = 0;
fscanf(infile,"%d",&n);

if (n<=1) //بررسی مقدار برای تعداد وارد شده
{
printf("W Not Valid, Must 2<n<999\n\r");
r=1; goto Err1;
}

if (F3_AllocArray()==1) {r=1; goto Err1;}

for (i=1; i<=n; i++) //تعیین وزن لبه ها برای رئوس دلخواه
for(j=1; j<=n; j++)
{
fscanf(infile,"%d",&vw);
if (vw == -1){vw = INIF;}
w[i][j]=vw; //قرار دهی وزن در ماتریس مجاورت
}


Err1:
if( infile) {fclose(infile);}
return(r);
}
//ذخیره آرایه مسیر های گذرانده شده و آرایه هزینه ها در فایل
void F3_WriteMatrixs()
{
//------------------------------------------
FILE *pathsfile ,*Dfile;
int i , j;
long allSubSet;

if ((pathsfile = fopen("P.txt", "w")) == NULL)
{
printf("Error With P.txt\n\r");
goto Errf;
}
if ((Dfile = fopen("D.txt", "w")) == NULL)
{
printf("Error With D.txt\n\r");
if( pathsfile) {fclose(pathsfile);}
goto Errf;
}
//----

allSubSet = pow(2,n);

for(j=1;j<allSubSet;j++)
{
for(i=1;i<=n;i++)
{
if(D[i][j]>=INIF || D[i][j]<=0)
fprintf(Dfile, ".\t");
else
fprintf(Dfile, "%d\t", D[i][j]);
//----
if(P[i][j]>=INIF || P[i][j]<=0)
fprintf(pathsfile, ".\t");
else
fprintf(pathsfile, "%d\t", P[i][j]);
}
fprintf(Dfile, "\n\r");
fprintf(pathsfile, "\n\r");
}
//----
if( pathsfile) fclose(pathsfile);
if( Dfile) fclose(Dfile);
//------------------------------------------
Errf:
;// به دلیل استفاده از دستور برچسب خالی این سیمی کلن لازم است
}
// این تابع کوتاه ترین مسیر را از ماتریس پی استخراج کرده و در کنسول چاپ می کند
void F3_ShowOptimalTour()
{
if (D[1][A]>=INIF)
{
printf("\n\rNo Tour.");
}
else{
int jx;
long n1;

printf("\n\rOptimal Tour = ");

jx = P[1][A];

printf("{v1,");
for (n1=1;n1<n;n1++)
{
printf("v%d," , jx);
//
A = A - T2[jx]; // کسر عضو جی از آ به عبارت دیگر عضو جی را نادیده می گیرد
if (A<0){A=0;}
//
k--;
jx = P[jx][A];
}
printf("v1}");
}
F3_WriteMatrixs();
}

// تابع اصلی برنامه
int main()
{
long minlen; char ch;

cn:
A = 0; n = 0;

if (F3_ReadFile()==1) goto cn;

system("cls");//clrscr();
printf("In Process...");

minlen = F2_DP(); // فراخوانی تابع اجرا کننده الگوریتم پویا

system("cls");//clrscr();
printf("\n\n\rMinimum Tour: ");

if (minlen<INIF)
printf("%d",minlen);
else
printf("*****");

F3_ShowOptimalTour();

F3_FreeArray();

ch = _getch(); // اگر کاربر کیلید اینتر را فشار دهد برنامه تکرار می شود و در غیر این صورت پایان می پذیرد و
return 0;
}

---------- Post added at 06:52 AM ---------- Previous post was at 06:49 AM ----------

3
0 1 4
3 0 999
999 3 0

---------- Post added at 06:53 AM ---------- Previous post was at 06:52 AM ----------

مثال برای 4 شهر


4
0 2 9 999
1 0 6 4
999 7 0 8
6 3 999 0

[sin2x=2sinxcosx]

یعنی خودتون براش الگوریتم طراحی کردین ؟
بهترین الگوریتمی که برای این مسئله طراحی شده به صورت داینامیک از مرتبه n^2*2^n هستش که برا تعداد شهرهای حدود 40 یا 50 تا چند هزار سال طول می کشه تا جواب بده . از اون مسئله های لاینحل هست .

[milad7091]

ببخشید که دیر جواب دادم.
این یک الگوریتمه که استادا از دانشجو ها می خوان. روش پویا توی درس طراحی الگوریتم فصل سوم.
منم به کمک یکی از دوستان نوشتمش و دادم به دوستام.
گفتم شاید کسی بخواد اینو گذاشتمش تو فورم.

[sare_poozi]

درود بر شما
من خود برنامه رو میخوام
اگه دارین ممنون میشم بزارین