旅行商c語言

Ⅰ 可運行的c語言程序：旅行商求最短路徑問題

在無向完全圖中，對於任意兩個頂點vi和vj，我們可以在多項式時間內找到vi和vj這兩個頂點之間版的所有路徑，選擇權其中路程最短的一條，令S[i,j]表示vi和vj這兩個頂點之間最短距離的那條路徑。搜索路徑S[i,j]，找到vi到達的在S[i,j]上的第一個頂點，記該頂點為vk，將其記錄在數組中R[][]，遞歸查找vi到vk和vk到vj的最短路徑及其相應權值，最後將數組D[]中的頂點和權值之和列印出來即為所求，並用畫圖函數將行經過程畫出。

Ⅱ 旅行商問題C語言的求解

排序額外寫了一個字函數，結構清晰點。

Void change(int array[],int n) /*冒泡排序子函數，n是個數*/
{ int i, j, temp;
for(j=0;j<=(n-2);j++)
{ for(i=0;i<=(n-2-j);i++)
{ if (*(array+i)<*(array+i+1))
{temp=*array(i); /*指針操作回，效率高答*/
*array(i)=*(array+i+1) ;
*(array+i+1)=temp ;
}
}
}

} /* 排序函數結束*/

# include <stdio.h>
# define N 4
main ()
{ int a[N] , m ;
for(m=0 ; m<=N-1 ; m++)
{printf(「please give the a(%d) : 」, m ) ;
scanf(「%d」,(a+m)) ;
}
change (a, N ) ; //調用排序函數
printf(「 The array is OK : /n 」 ) ;

for (m=0 ; m<=N-1 ; m++) //由大到小排列
printf(「 %d 」, *(a+m) ) ;

} //主函數結束

Ⅲ Ubuntu系統下由gcc編譯的C語言利用蟻群演算法計算tsp（旅行商問題）的詳解和注釋

買本書看看去。

你這個只是所有代碼里的一個開頭，我只能解釋這兩句話，解釋了你又不滿意。
我只能叫你去買本書看。

Ⅳ 最短連接策略求解tsp問題的c語言

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<stdafx.h>
#include <time.h>
#define PopSize 50 /*種群類DNA個數 */
#define MaxGens 200 /* 最大代數 */
#define N 10 /* 問題規模 */
#define PC 0.8 /* 交叉概率 */
#define PM 0.01 /* 突變概率 */
#define RAND_MAX 10
int city[N];
int begin_city=0; /*出發城市*/
double r[N][N]={
0, 1, 4, 6, 8, 1, 3, 7, 2, 9,
1, 0, 7, 5, 3, 8, 3, 4, 2, 4,
4, 7, 0, 3, 8, 3, 7, 9, 1, 2,
6, 5, 3, 0, 3, 1, 5, 2, 9, 1,
8, 3, 8, 3, 0, 2, 3, 1, 4, 6,
1, 8, 3, 1, 2, 0, 3, 3, 9, 5,
3, 3, 7, 5, 3, 3, 0, 7, 5, 9,
7, 4, 9, 2, 1, 3, 7, 0, 1, 3,
2, 2, 1, 9, 4, 9, 5, 1, 0, 1,
9, 4, 2, 1, 6, 5, 9, 3, 1, 0
} ;
int generation; /*當前代數 */
int CurBest; /*最優個體 */
struct GenoType
{
int gene[N]; /* 城市序列 */
double fitness; /* 當前城市序列對應的適應值 */
double rfitness; /* 適應率 */
double cfitness; /* 輪盤對應的起始區間值 */
};
struct ResultType
{
double best_val; /*最佳適應度 */
double avg; /*平均適應度 */
double stddev; /*標准差 */
};
GenoType population[PopSize+1]; /* 種群 */
GenoType newpopulation[PopSize+1]; /*新種群 */
ResultType result[MaxGens];/*種群換代記錄 */
/*函數聲明 */
void initialize();/*初始化 */
void evaluate();/*評價函數 */
void Find_the_best();/*找出最優 */
void elitist();/*擇優函數*/
void select();/*選擇 */
void crossover();/*交叉 */
void mutate();/*變異 */
void report();/*報告輸出 */
int IntGenerate();/*產生一個城市節點 */
void swap(int *,int *);/*交換兩值 */
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
/* 產生一個0到10的數，作為城市編號*/
int IntGenerate()
{
int RANGE_MIN = 0;
int RANGE_MAX = N;
int rand_10;
rand_10=(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
return rand_10;
}
/*初始化種群*/
void initialize()
{
int matrix[N];
int x1,x2;
int i,j;
/*生成一個定值序列 ，0點為開始點 */
for(i=1; i<N; i++)
matrix[i]=i;
for(j=0;j<PopSize;j++)
{
population[i].gene[0]=begin_city; /*gene[0]表示出發城市，i表示城市次序 */
for( i=0;i<N;i++) /*N次交換足以產生各種結果了 */
{
x1=0; x2=0;
while(x1==0)
x1=IntGenerate();
while(x2==0)
x2=IntGenerate();
swap(&matrix[x1],&matrix[x2]);
}
for(int i=1;i<N;i++)
population[j].gene[i]=matrix[i];
}

Ⅳ TSP問題 用C語言解決

#include<stdio.h>
#define N 100
void show(int cur,int n);
int a[N];
int main()
{
int cs[N];
int n,i;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
權cs[i]=i+1;
show(0,n);

}
return 0;
}
void show(int cur,int n)
{
int i,j,ok;
if(n==cur)
{
for(i=0;i<n;i++)
printf("%d",a[i]);
printf("\n");
}
else
{
for(i=1;i<=n;i++)
{
for(j=0;j<=cur;j++)
{
ok=1;
if(a[j]==i)
{
ok=0;
break;
}
}
if(ok)
{
a[cur]=i;
show(cur+1,n);
}
}
}
}
。。就是這么個全排列問題嗎？

Ⅵ 急！C語言TSP(旅行推銷員)問題（用C不用C++）

這個簡單很願意協助你完成任務朋友

Ⅶ 哪位大神有蜂群演算法求解tsp問題的代碼啊（c語言）

您好，有，來了：
#include "stdio.h"
#include "math.h"
void main()
{
long x[21]={0},y[21]={0},d[191]={0},e[191]={0},g[41]={0},s[42]={0};
int i,j,h=1,k,l,o,m,n=0,p,q=3,r=0;
int flag;
double a[21]={0},b[21][21]={0},c[21][21]={0},f[191]={0};
char ch;

printf(" C-W演算法求解TSP問題 \n\n\n");
printf("請輸入坐標（20個以內），坐標之間用空格隔開，按回車鍵結束輸入：\n");

re:scanf("%d,%d",&x[h],&y[h]);
ch=getchar();
if(ch!='\n')
{ h++;
goto re;
}

for(i=1;i<h+1;i++)
a[i]=sqrt(x[i]*x[i]+y[i]*y[i]);

for(i=1;i<h;i++)
{
for(j=i+1;j<h+1;j++)
{ n++;
b[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
c[i][j]=a[i]+a[j]-b[i][j];
d[n]=i;
e[n]=j;
f[n]=c[i][j];
}
}

for(i=1;i<n;i++)
{ flag=0;
for(j=1;j<n+1-i;j++)
if(f[j]>f[j+1])
{ k=f[j];f[j]=f[j+1];f[j+1]=k;
l=d[j];d[j]=d[j+1];d[j+1]=l;
o=e[j];e[j]=e[j+1];e[j+1]=o;
flag=1;
}
if(flag==0)
break;
}

printf("\n");
printf("節約值排序：\n");
for(i=n;i>0;i--)
{ if(f[i]!=0)
printf("%lf(%ld,%ld)--(%ld,%ld)\n",f[i],x[d[i]],y[d[i]],x[e[i]],y[e[i]]);
}

g[1]=d[n];
g[2]=e[n];

for(m=1;m<h;m++)
{
for(j=n-1;j>0;j--)
{ p=0;
for(i=1;i<41;i++)
{
if(d[j]==g[i])
p=p+1;
if(e[j]==g[i])
p=p+1;
}
if(p==1)
{ g[q]=d[j];
g[q+1]=e[j];
}
if(p==1)
break;
}
q=q+2;
}

printf("\n選出連接點：\n");
for(i=1;i<41;i=i+2)
{ if(g[i]!=0)
{
printf("(%ld,%ld)--(%ld,%ld)\n",x[g[i]],y[g[i]],x[g[i+1]],y[g[i+1]]);
r=r+2;
}
}

s[21]=g[1];
s[22]=g[2];

for(i=3;i<r;i=i+2)
for(j=1;j<42;j++)
{
if(g[i]==s[j])
{
if(s[j-1]==0)
s[j-1]=g[i+1];
else
s[j+1]=g[i+1];
break;
}

if(g[i+1]==s[j])
{
if(s[j-1]==0)
s[j-1]=g[i];
else
s[j+1]=g[i];
break;
}
}

printf("\n旅行商路線：\n");
printf("(0,0)--");
for(i=1;i<42;i++)
{
if(s[i]!=0)
printf("(%ld,%ld)--",x[s[i]],y[s[i]]);
}
printf("(0,0)");
getch();
}

Ⅷ 遺傳演算法求解對稱旅行商問題的C語言源代碼

一個遺傳演算法 50分

Ⅸ TSP（旅行商問題）用分支限界法。用c語言寫

#include <bits/stdc++.h>
using namespace std;
double graph[25][25];
int vis[25];
double a[25];
double ub;
double ans;
struct point {
int x;
int y;
}p[25];
double dis(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void dfs(int n, int x, double temp, int cnt)
{
// printf("%.2lf\n", temp);
if(cnt == n-2)
{
ub = min(ub, temp+graph[x][n-1]);
return ;
}
vis[x]=1;
for(int i=0; i<n-1; i++)
{
if(graph[x][i] && ![i])
{
temp += graph[x][i];
if(temp < ub)
dfs(n, i, temp, cnt+1);
temp -= graph[x][i];
vis[i]=0;

}
}

}
int main()
{
int t, n, x, y;
scanf("%d", &t);
while(t--)
{
int cnt=0;
ub=0x3f3f3f3f;
double temp=0;
memset(graph, 0, sizeof(graph));
memset(vis, 0, sizeof(vis));

scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
graph[i][j] = dis(p[i], p[j]);

vis[0]=1;
dfs(n,0,temp,0);
printf("%.2lf\n", ub);
}
return 0;
}

Ⅹ 急求一TSP問題程序(用C語言描述)

tsproblem.h
class tsproblem
{
private:
int *parrayc;
int *parrayj;
int icost;
int icurpoint, isize;
unsigned long ls;
unsigned long power(int i, int j);
int g(int i, unsigned long s);
public:
tsproblem(int size, int point);
tsproblem(int size, int point, int *array);
void calculate();
void display();
~tsproblem();
};

#include "tsproblem.h"
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
//採用動態規劃方法,用c(i, j)表示邊v(i, j)的長度,g(i, s)表
//示從結點i開始,經過s中的每一結點一次且僅一次到達i的最短路
//徑長度,則有如下遞推式:
// g(i, s)=min{c(i, j)+g(j, s-{j})} (j在s集合中)
//為實現集合s的表示,採用如下方法:
//把s定義為unsigned long型數,設其二進製表示為:bn....b2b1b0
//則當b0為1時表示0在集合s中,b0為0時表示0不在集合s中,余類推
tsproblem::tsproblem(int size, int point)
{
int i, j;
isize=size;
icurpoint=point;
if(icurpoint>=isize){
cout<<"the curpoint is out of range!\n";
return;
}
parrayc=new int[isize*isize];
for(i=0; i<isize; i++)
for(j=0; j<isize; j++){
if(i==j)
parrayc[i*isize+j]=0;
else
parrayc[i*isize+j]=rand()*isize/18000+1;
}
parrayj=new int[isize*power(2, isize)];
}

void tsproblem::calculate()
{
ls=0;
ls=~ls;
ls=ls<<isize;
ls=~ls;
ls-=power(2, icurpoint);
icost=g(icurpoint, ls);
}

int tsproblem::g(int i, unsigned long s)
{
int j, k, t, temp=32767;
if(s==0)
return parrayc[i*isize+icurpoint];
for(j=0; j<isize; j++){
if((s>>j)%2==0) continue;
else{
t=parrayc[i*isize+j]+g(j, s-power(2, j));
if(temp>t){
temp=t;
k=j;
}
}
}
parrayj[i*power(2, isize)+s]=k;
return temp;
}

unsigned long tsproblem::power(int i, int j)
{
unsigned long t=1;
for(int k=0; k<j; k++)
t=t*i;
return t;
}

void tsproblem::display()
{
int temp, i, j, n=power(2, isize);
unsigned long s=ls;
temp=icurpoint;
cout<<" the array of cost is:\n\t";
for(i=0; i<isize; i++){
for(j=0; j<isize; j++)
cout<<setw(4)<<parrayc[i*isize+j];
cout<<endl<<"\t";
}
cout<<"\n the shortest path is:\n\t";
cout<<" "<<icurpoint;
while(s){
temp=parrayj[temp*n+s];
s-=power(2, temp);
cout<<" "<<temp;
}
cout<<" "<<icurpoint<<endl<<" the min cost is:"
<<icost<<endl;
}

tsproblem::~tsproblem()
{
if(parrayc)delete parrayc;
if(parrayj)delete parrayj;
}