求最优算法--旅行路线选择?????????????

hua_zhixing_ 2009-07-25 10:23:23
旅行路线选择：
设有 n 个城市（或景点），今从某市出发遍历各城市，使之旅费最少（即找出一条旅
费最少的路径）。

各城市之间的旅费如下：
0 17 13 24 10
10 0 20 9 6
17 29 0 21 28
12 10 22 0 19
12 18 31 20 0

最小生成树与最短路径都不是其解吧。有什么好算法吗？？？？
...全文
712 22 打赏 收藏 转发到动态 举报
写回复
用AI写文章
22 条回复
切换为时间正序
请发表友善的回复…
发表回复
丈八涯 2009-08-18
  • 打赏
  • 举报
 回复
嘿嘿,程序不是俺写的.一个商用程序,比这效果好的程序应该还有很多.
不要使用穷举了,这个现在的解法有很多,最优解有几种方法,非最优的往往用于速度或计算量有要求的情况.
[Quote=引用 18 楼 linren 的回复:]
引用 16 楼 g_idea 的回复:
运行结果为:0 11 19 14 9 10 22 16 13 5 18 4 8 2 23 17 20 3 15 1 7 6 21 12 所走圆周路程长为:334
此程序的运行时间为1.234秒！
Press any key to continue

太厉害了……
是怎么办到的？
[/Quote]
linren 2009-08-18
  • 打赏
  • 举报
 回复
[Quote=引用 20 楼 g_idea 的回复:]
嘿嘿,程序不是俺写的.一个商用程序,比这效果好的程序应该还有很多.
不要使用穷举了,这个现在的解法有很多,最优解有几种方法,非最优的往往用于速度或计算量有要求的情况.

[/Quote]
恩
还是得继续学习^_^……
linren 2009-08-18
  • 打赏
  • 举报
 回复
【程序】
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <windows.h>



/**只用修改这里*****************/

#define SIZE 5

int list[SIZE][SIZE]={

     0, 17, 13, 24, 10,

    10,  0, 20,  9,  6,

    17, 29,  0, 21, 28,

    12, 10, 22,  0, 19,

    12, 18, 31, 20, 0

};

/*****************只用修改这里**/



void travel(int *a,int len){

	int *ta,*tb;

	int *p,*path;

	int flg;

	int i,j,k,t;

	int x,y,z;

	ta=(int*)malloc(sizeof(int)*(len-1)*len);

	tb=(int*)malloc(sizeof(int)*(len-1)*len);

	path=(int*)malloc(sizeof(int)*(len-1));

	memset(ta,0,sizeof(int)*(len-1)*len);

	memset(tb,0,sizeof(int)*(len-1)*len);

	memset(path,0,sizeof(int)*(len-1));



	for(k=1;k<len;k++){

		*(ta+len*(k-1))=*(a+k*len);

		*(ta+len*(k-1)+k)=1;

	}

	flg=1;

	for(z=2;z<len;z++){

		for(i=1;i<len;i++){

			y=-1;

			for(k=1;k<len;k++){

				if(flg==1){

					if(*(ta+len*(k-1))==-1) continue;

					if(*(ta+len*(k-1)+i)!=0) continue;

					x=*(a+len*i+k)+*(ta+len*(k-1));

				}else{

					if(*(tb+len*(k-1))==-1) continue;

					if(*(tb+len*(k-1)+i)!=0) continue;

					x=*(a+i*len+k)+*(tb+len*(k-1));

				}

				if(y==-1||x<y){

					j=k;y=x;

				}

			}

			if(y==-1){

				if(flg==1) *(tb+len*(i-1))=y;

				else *(ta+len*(i-1))=y;

				continue;

			}

			if(flg==1){

				*(tb+len*(i-1))=y;

				for(k=1;k<len;k++){

					if(*(ta+len*(j-1)+k)==0) *(tb+len*(i-1)+k)=0;

					else *(tb+len*(i-1)+k)=*(ta+len*(j-1)+k)+1;

				}

				*(tb+len*(i-1)+i)=1;

			}else{

				*(ta+len*(i-1))=y;

				for(k=1;k<len;k++){

					if(*(tb+len*(j-1)+k)==0) *(ta+len*(i-1)+k)=0;

					else *(ta+len*(i-1)+k)=*(tb+len*(j-1)+k)+1;

				}

				*(ta+len*(i-1)+i)=1;

			}

		}

		if(flg==1) flg=0;

		else flg=1;

	}

	

	y=-1;

	for(i=1;i<len;i++){

		if(flg==1){

			if(*(ta+len*(i-1))==-1) continue;

			x=*(ta+len*(i-1))+*(a+i);

		}else{

			if(*(tb+len*(i-1))==-1) continue;

			x=*(tb+len*(i-1))+*(a+i);

		}

		if(y==-1||x<y){

			y=x;t=i;

		}

	}



	/**打印结果************************/

	if(flg==1) p=ta+len*(t-1);

	else p=tb+len*(t-1);

	for(i=1;i<len;i++){

		path[p[i]-1]=i;

	}

	printf("path: 0 ");

	for(i=0;i<len-1;i++) printf("-> %d ",path[i]);

	printf("-> 0\n");

	printf("cost: %d\n",y);

	/************************打印结果**/



	free(ta);free(tb);free(path);

}



class CTimer

{

public:

    __forceinline CTimer( void ) {

        QueryPerformanceFrequency( (PLARGE_INTEGER)&m_nFreq );

        QueryPerformanceCounter( (PLARGE_INTEGER)&m_nStart ); }

    __forceinline void Reset( void ) {

        QueryPerformanceCounter( (PLARGE_INTEGER)&m_nStart ); }

    __forceinline double Stop( void ) {

        QueryPerformanceCounter( (PLARGE_INTEGER)&m_nCur );

        return double( m_nCur - m_nStart ) / double( m_nFreq ); }

    __forceinline bool SelfTest( void ){

        return ( 0 != QueryPerformanceFrequency( (PLARGE_INTEGER)&m_nFreq ) ); }

private:

    __int64 m_nCur;

    __int64 m_nFreq;

    __int64 m_nStart;

};



int main(){

	CTimer tmr;

	travel(&list[0][0],SIZE);

	printf("use time: %f s\n",tmr.Stop());

	return 0;

}

【用例1】 0楼的数据
【结果1】
path: 0 -> 2 -> 3 -> 1 -> 4 -> 0
cost: 62
use time: 0.000488 s
Press any key to continue

【用例2】 13楼的数据
【结果2】
path: 0 -> 5 -> 7 -> 6 -> 2 -> 3 -> 1 -> 4 -> 0
cost: 125
use time: 0.002713 s
Press any key to continue

【用例3】 16楼的用例
【结果3】
path: 0 -> 7 -> 6 -> 21 -> 10 -> 22 -> 16 -> 19 -> 14 -> 9 -> 15 -> 1 -> 2 -> 23
-> 11 -> 17 -> 20 -> 3 -> 13 -> 5 -> 18 -> 4 -> 8 -> 12 -> 0
cost: 377
use time: 0.003080 s
Press any key to continue

【说明】
用例3没有能够找到最佳解……
果然是NP难问题……
linren 2009-08-17
  • 打赏
  • 举报
 回复
（上接12楼）
12楼的程序有些地方忘记是要符合任意大小的list了
比如说加法和打印……
下面的程序应该是能满足任意大小的list的了……

【程序】
#include <stdio.h>

#include <stdlib.h>

#include <string.h>



/**只用修改这里*****************/

#define SIZE 8

int list[SIZE][SIZE]={

	0, 17, 13, 24, 10, 12, 34, 45,

    10, 0, 20, 9, 6, 34, 13, 39,

    17, 29, 0, 21, 28, 24, 27, 19,

    12, 10, 22, 0, 19, 21, 22, 23,

    12, 18, 31, 20, 0, 24, 25, 26,

	45, 43, 41, 39, 36, 0, 31, 25,

	14, 15, 16, 17, 18, 19, 0, 25,

	51, 52, 53, 54, 55, 25, 23, 0

};

/*****************只用修改这里**/



void travel(int *a,int len){

	int *p,*c,*tmp;

	int i,j,k,flg;

	int b=-1,d;

	if(len<1){

		printf("error: len<1\n");return;

	}



	p=(int*)malloc(sizeof(int)*len);

	c=(int*)malloc(sizeof(int)*len);

	tmp=(int*)malloc(sizeof(int)*len);

	memset(p,0,sizeof(int)*len);

	memset(c,0,sizeof(int)*len);

	

	k=0;flg=1;

	while(flg){

		for(p[k]=0;p[k]<len;p[k]++){

			for(i=0;i<k;i++){

				if(p[i]==p[k]) break;

			}

			if(i!=k) continue;

			c[k]++;

			if(k==len-1){

				///////////////////////////////////////

				d=0;

				for(i=0;i<len-1;i++) d+=*(a+p[i]*len+p[i+1]);

				if(b==-1||d<b){

					b=d;

					memcpy(tmp,p,sizeof(int)*len);

				}

				///////////////////////////////////////

				for(i=len-1,j=1;c[i]==j&&i>=0;i--,j++);

				if(j==len+1){

					flg=0;break;

				}

				k=i;

				if(k<len-1){

					memset(c+k+1,0,sizeof(int)*(len-k-1));

				}

			}

			else k++;

		}

	}



	printf("path: ");

	for(i=0;i<len-1;i++) printf("%d -> ",tmp[i]);

	printf("%d\n",tmp[i]);

	printf("cost: %d\n",b);

	free(p);free(c);free(tmp);

}



int main(){

	travel(&list[0][0],SIZE);

	return 0;

}

【运行结果】
path: 2 -> 7 -> 6 -> 3 -> 1 -> 4 -> 0 -> 5
cost: 99
Press any key to continue
linren 2009-08-17
  • 打赏
  • 举报
 回复
【程序】
#include <stdio.h>

#include <stdlib.h>

#include <string.h>



/**只用修改这里*****************/

#define SIZE 5

int list[SIZE][SIZE]={

     0, 17, 13, 24, 10,

    10,  0, 20,  9,  6,

    17, 29,  0, 21, 28,

    12, 10, 22,  0, 19,

    12, 18, 31, 20, 0};

/*****************只用修改这里**/



void travel(int *a,int len){

	int *p,*c,*tmp;

	int i,j,k,flg;

	int b=-1,d;

	if(len<1){

		printf("error: len<1\n");return;

	}



	p=(int*)malloc(sizeof(int)*len);

	c=(int*)malloc(sizeof(int)*len);

	tmp=(int*)malloc(sizeof(int)*len);

	memset(p,0,sizeof(int)*len);

	memset(c,0,sizeof(int)*len);

	

	k=0;flg=1;

	while(flg){

		for(p[k]=0;p[k]<len;p[k]++){

			for(i=0;i<k;i++){

				if(p[i]==p[k]) break;

			}

			if(i!=k) continue;

			c[k]++;

			if(k==len-1){

				///////////////////////////////////////

				d=*(a+p[0]*len+p[1])+*(a+p[1]*len+p[2])+*(a+p[2]*len+p[3])+*(a+p[3]*len+p[4]);

				if(b==-1||d<b){

					b=d;

					memcpy(tmp,p,sizeof(int)*len);

				}

				///////////////////////////////////////

				for(i=len-1,j=1;c[i]==j&&i>=0;i--,j++);

				if(j==len+1){

					flg=0;break;

				}

				k=i;

				if(k<len-1){

					memset(c+k+1,0,sizeof(int)*(len-k-1));

				}

			}

			else k++;

		}

	}



	printf("path: %d -> %d -> %d -> %d -> %d\n",tmp[0],tmp[1],tmp[2],tmp[3],tmp[4]);

	printf("cost: %d\n",b);

	free(p);free(c);free(tmp);

}



int main(){

	travel(&list[0][0],SIZE);

	return 0;

}

【运行结果】
path: 3 -> 1 -> 4 -> 0 -> 2
cost: 41
Press any key to continue

【说明】
修改了一下8楼的程序……
适合任意大小的list
linren 2009-08-17
  • 打赏
  • 举报
 回复
好像可以用动态规划来解决这个问题……
状态变量为：
U1={0}
U2={1,2,...,n-1}
U3={1,2,...,n-1}
...
Un={1,2,...,n-1}
U(n+1)={0}
linren 2009-08-17
  • 打赏
  • 举报
 回复
[Quote=引用 16 楼 g_idea 的回复:]
运行结果为:0 11 19 14 9 10 22 16 13 5 18 4 8 2 23 17 20 3 15 1 7 6 21 12 所走圆周路程长为:334
此程序的运行时间为1.234秒！
Press any key to continue
[/Quote]
太厉害了……
是怎么办到的？
daniao57 2009-08-17
  • 打赏
  • 举报
 回复
就5个节点，可以穷举了，因为总共的线路才 （5 - 1）！/ 2 = 12个
多的话用遗传算法比较好，当然这个算法不是一两天就能学明白的
交叉方法，变异方法，交叉率，变异率，迭代次数等等都要细心设计
丈八涯 2009-08-17
  • 打赏
  • 举报
 回复
0,123,59,100,95,53,169,53,74,11,148,11,2,54,188,143,141,142,195,130,113,108,144,192,
64,0,20,95,154,61,92,24,169,27,174,197,27,94,47,196,59,76,196,179,97,189,143,44,
115,166,0,147,172,32,78,78,173,41,117,132,17,100,89,185,117,125,170,57,55,127,152,18,
182,89,120,0,170,14,160,91,70,20,198,147,179,16,115,15,151,191,62,26,14,152,119,103,
127,169,16,95,0,79,91,89,1,26,152,33,166,23,101,51,27,32,188,49,103,186,31,100,
70,125,111,200,130,0,29,123,122,95,168,104,80,110,145,62,175,47,3,102,36,50,32,117,
172,178,39,182,151,135,0,85,3,27,135,23,124,16,141,117,179,151,2,179,133,11,162,20,
117,192,179,48,180,190,23,0,112,147,73,178,147,23,187,177,45,97,168,134,164,19,173,44,
108,169,14,193,90,176,158,33,0,85,198,63,7,171,146,54,23,145,161,180,91,107,164,144,
189,183,88,14,35,187,119,57,12,0,19,89,143,60,157,29,22,198,37,82,139,89,147,60,
106,29,62,36,96,41,91,44,90,182,0,119,64,129,137,132,123,100,154,188,157,87,46,161,
24,51,56,114,43,168,169,12,56,104,153,0,17,51,161,154,28,4,48,8,188,187,92,100,
2,21,171,81,11,177,123,5,12,84,103,6,0,168,27,22,129,88,34,9,22,87,69,117,
115,178,183,154,125,3,119,185,136,87,14,137,98,0,82,128,9,82,177,151,184,113,42,89,
46,151,57,94,24,71,81,59,88,16,63,132,69,152,0,36,141,44,11,164,16,195,92,154,
168,11,168,76,78,59,134,142,86,44,157,169,181,90,99,0,114,111,134,158,27,137,137,189,
162,51,41,177,48,194,120,133,135,25,114,55,190,31,62,197,0,134,96,18,96,192,28,185,
153,69,197,194,184,200,111,107,102,147,73,129,151,64,144,135,120,0,8,197,9,179,188,61,
96,71,80,34,14,128,108,114,62,116,4,134,35,76,190,143,65,158,0,19,95,189,170,56,
27,112,66,56,70,160,142,30,66,118,110,16,97,116,19,110,192,122,163,0,188,69,190,72,
43,123,47,16,127,186,111,185,118,33,151,192,53,159,61,97,95,123,34,142,0,67,73,158,
87,113,65,31,59,179,62,63,29,162,21,31,7,165,151,129,187,95,17,36,183,0,113,38,
135,150,123,121,44,165,189,129,188,56,191,189,49,110,32,139,6,147,133,17,72,144,0,194,
57,161,38,165,195,79,106,156,171,175,67,11,116,186,120,120,198,7,5,19,165,126,154,0,

运行结果为:0 11 19 14 9 10 22 16 13 5 18 4 8 2 23 17 20 3 15 1 7 6 21 12 所走圆周路程长为:334
此程序的运行时间为1.234秒！
Press any key to continue
丈八涯 2009-08-17
  • 打赏
  • 举报
 回复
0,17,13,24,10,12,34,45,
10,0,20,9,6,34,13,39,
17,29,0,21,28,24,27,19,
12,10,22,0,19,21,22,23,
12,18,31,20,0,24,25,26,
45,43,41,39,36,0,31,25,
14,15,16,17,18,19,0,25,
51,52,53,54,55,25,23,0,
运行结果为:0 5 7 6 2 3 1 4 所走圆周路程长为:125
此程序的运行时间为0.015秒！
Press any key to continue
super_chris 2009-08-17
  • 打赏
  • 举报
 回复
城市这么少 穷举
？
linren 2009-08-11
  • 打赏
  • 举报
 回复
[Quote=引用 10 楼 chiwenzi 的回复:]
4L的答案是正确的
[/Quote]
恩
旅行结束后回到出发点
这个之前没有考虑到……

下面的程序可以指定起始和结束的城市：

【程序】
#include <stdio.h>



int list[5][5]={

	 0, 17, 13, 24, 10,

	10,  0, 20,  9,  6,

	17, 29,  0, 21, 28,

	12, 10, 22,  0, 19,

	12, 18, 31, 20,  0};



void travel(int start,int end){

	int p[5]={0};

	int tmp[5]={0};

	int a,b=-1;

	p[0]=start;

	if(start==end){

		for(p[1]=0;p[1]<5;p[1]++){

			if(p[0]==p[1]) continue;

			for(p[2]=0;p[2]<5;p[2]++){

				if(p[0]==p[2]||p[1]==p[2]) continue;

				for(p[3]=0;p[3]<5;p[3]++){

					if(p[0]==p[3]||p[1]==p[3]||p[2]==p[3]) continue;

					for(p[4]=0;p[4]<5;p[4]++){

						if(p[0]==p[4]||p[1]==p[4]||p[2]==p[4]||p[3]==p[4]) continue;

						a=list[p[0]][p[1]]+list[p[1]][p[2]]+list[p[2]][p[3]]+list[p[3]][p[4]]+list[p[4]][p[0]];

						if(b==-1||a<b){

							b=a;tmp[0]=p[0];tmp[1]=p[1];tmp[2]=p[2];tmp[3]=p[3];tmp[4]=p[4];

						}

					}

				}

			}

		}

		printf("path: %d -> %d -> %d -> %d -> %d -> %d\t",tmp[0],tmp[1],tmp[2],tmp[3],tmp[4],tmp[0]);

		printf("cost: %d\n",b);

	}else{

		p[4]=end;

		for(p[1]=0;p[1]<5;p[1]++){

			if(p[0]==p[1]||p[4]==p[1]) continue;

			for(p[2]=0;p[2]<5;p[2]++){

				if(p[0]==p[2]||p[1]==p[2]||p[4]==p[2]) continue;

				for(p[3]=0;p[3]<5;p[3]++){

					if(p[0]==p[3]||p[1]==p[3]||p[2]==p[3]||p[4]==p[3]) continue;

					a=list[p[0]][p[1]]+list[p[1]][p[2]]+list[p[2]][p[3]]+list[p[3]][p[4]];

					if(b==-1||a<b){

						b=a;tmp[0]=p[0];tmp[1]=p[1];tmp[2]=p[2];tmp[3]=p[3];tmp[4]=p[4];

					}

				}

			}

		}

		printf("path: %d -> %d -> %d -> %d -> %d\t\t",tmp[0],tmp[1],tmp[2],tmp[3],tmp[4]);

		printf("cost: %d\n",b);

	}

}



int main(){

	int i,j;

	for(i=0;i<5;i++) for(j=0;j<5;j++) travel(i,j);

	return 0;

}

【运行结果】
path: 0 -> 2 -> 3 -> 1 -> 4 -> 0 cost: 62
path: 0 -> 2 -> 3 -> 4 -> 1 cost: 71
path: 0 -> 4 -> 1 -> 3 -> 2 cost: 59
path: 0 -> 2 -> 1 -> 4 -> 3 cost: 68
path: 0 -> 2 -> 3 -> 1 -> 4 cost: 50
path: 1 -> 4 -> 3 -> 2 -> 0 cost: 65
path: 1 -> 4 -> 0 -> 2 -> 3 -> 1 cost: 62
path: 1 -> 4 -> 3 -> 0 -> 2 cost: 51
path: 1 -> 4 -> 0 -> 2 -> 3 cost: 52
path: 1 -> 3 -> 2 -> 0 -> 4 cost: 58
path: 2 -> 3 -> 1 -> 4 -> 0 cost: 49
path: 2 -> 0 -> 4 -> 3 -> 1 cost: 57
path: 2 -> 3 -> 1 -> 4 -> 0 -> 2 cost: 62
path: 2 -> 0 -> 4 -> 1 -> 3 cost: 54
path: 2 -> 3 -> 1 -> 0 -> 4 cost: 51
path: 3 -> 1 -> 4 -> 2 -> 0 cost: 64
path: 3 -> 2 -> 0 -> 4 -> 1 cost: 67
path: 3 -> 1 -> 4 -> 0 -> 2 cost: 41
path: 3 -> 1 -> 4 -> 0 -> 2 -> 3 cost: 62
path: 3 -> 1 -> 2 -> 0 -> 4 cost: 57
path: 4 -> 1 -> 3 -> 2 -> 0 cost: 66
path: 4 -> 0 -> 2 -> 3 -> 1 cost: 56
path: 4 -> 1 -> 3 -> 0 -> 2 cost: 52
path: 4 -> 1 -> 0 -> 2 -> 3 cost: 62
path: 4 -> 0 -> 2 -> 3 -> 1 -> 4 cost: 62
Press any key to continue
chiwenzi 2009-08-11
  • 打赏
  • 举报
 回复
4L的答案是正确的
hua_zhixing_ 2009-08-10
  • 打赏
  • 举报
 回复
[Quote=引用 3 楼 fireseed 的回复:]
非常经典的旅行商问题，请看链接：

http://zh.wikipedia.org/wiki/旅行推销员问题

另外对楼主提出批评，您在提问前应该先用google，这样会更有效率，更节省资源！
[/Quote]
接受批评，就是因为那些看得糊涂，所以想在这儿得到通俗的解答。
linren 2009-08-10
  • 打赏
  • 举报
 回复
如果指定起始地点的话
可以把程序修改成为这样：

【程序】
#include <stdio.h>



int list[5][5]={

	 0, 17, 13, 24, 10,

	10,  0, 20,  9,  6,

	17, 29,  0, 21, 28,

	12, 10, 22,  0, 19,

	12, 18, 31, 20, 0};



void start(int s){

	int p[5]={0};

	int tmp[5]={0};

	int i=0,a,b=-1;

	p[0]=s;

	for(p[1]=0;p[1]<5;p[1]++){

		if(p[0]==p[1]) continue;

	for(p[2]=0;p[2]<5;p[2]++){

		if(p[0]==p[2]||p[1]==p[2]) continue;

	for(p[3]=0;p[3]<5;p[3]++){

		if(p[0]==p[3]||p[1]==p[3]||p[2]==p[3]) continue;

	for(p[4]=0;p[4]<5;p[4]++){

		if(p[0]==p[4]||p[1]==p[4]||p[2]==p[4]||p[3]==p[4]) continue;\

		a=list[p[0]][p[1]]+list[p[1]][p[2]]+list[p[2]][p[3]]+list[p[3]][p[4]];

		if(b==-1||a<b){

			b=a;

			tmp[0]=p[0];tmp[1]=p[1];tmp[2]=p[2];tmp[3]=p[3];tmp[4]=p[4];

		}

	}

	}

	}

	}

	printf("path: %d -> %d -> %d -> %d -> %d\n",tmp[0],tmp[1],tmp[2],tmp[3],tmp[4]);

	printf("cost: %d\n",b);

}



int main(){

	int i;

	for(i=0;i<5;i++) start(i);

	return 0;

}

【运行结果】
path: 0 -> 2 -> 3 -> 1 -> 4
cost: 50
path: 1 -> 4 -> 3 -> 0 -> 2
cost: 51
path: 2 -> 3 -> 1 -> 4 -> 0
cost: 49
path: 3 -> 1 -> 4 -> 0 -> 2
cost: 41
path: 4 -> 1 -> 3 -> 0 -> 2
cost: 52
Press any key to continue
linren 2009-08-10
  • 打赏
  • 举报
 回复
【程序】
#include <stdio.h>

#include <stdlib.h>



int list[5][5]={

	 0, 17, 13, 24, 10,

	10,  0, 20,  9,  6,

	17, 29,  0, 21, 28,

	12, 10, 22,  0, 19,

	12, 18, 31, 20, 0};



int main(){

	int p[5]={0};

	int tmp[5]={0};

	int i=0,a,b=-1;

	for(p[0]=0;p[0]<5;p[0]++){

	for(p[1]=0;p[1]<5;p[1]++){

		if(p[0]==p[1]) continue;

	for(p[2]=0;p[2]<5;p[2]++){

		if(p[0]==p[2]||p[1]==p[2]) continue;

	for(p[3]=0;p[3]<5;p[3]++){

		if(p[0]==p[3]||p[1]==p[3]||p[2]==p[3]) continue;

	for(p[4]=0;p[4]<5;p[4]++){

		if(p[0]==p[4]||p[1]==p[4]||p[2]==p[4]||p[3]==p[4]) continue;\

		a=list[p[0]][p[1]]+list[p[1]][p[2]]+list[p[2]][p[3]]+list[p[3]][p[4]];

		if(b==-1||a<b){

			b=a;

			tmp[0]=p[0];tmp[1]=p[1];tmp[2]=p[2];tmp[3]=p[3];tmp[4]=p[4];

		}

	}

	}

	}

	}

	}

	printf("path: %d -> %d -> %d -> %d -> %d\n",tmp[0],tmp[1],tmp[2],tmp[3],tmp[4]);

	printf("cost: %d\n",b);

    return 0;

}

【结果】
path: 3 -> 1 -> 4 -> 0 -> 2
cost: 41
Press any key to continue
linren 2009-08-10
  • 打赏
  • 举报
 回复
如果用枚举的方法……
可能需要进行全排序
因为A->B的旅费和B->A的旅费好像是不一样的……

时间复杂度为n!
oyzdz1988 2009-08-10
  • 打赏
  • 举报
 回复
ＴＳＰ问题用遗传算法求解效果很不错的~
丈八涯 2009-08-04
  • 打赏
  • 举报
 回复
0,17,13,24,10,
10,0,20,9,6,
17,29,0,21,28,
12,10,22,0,19,
12,18,31,20,0,

运行结果为:0 2 3 1 4 所走圆周路程长为:62
此程序的运行时间为0秒！
Press any key to continue
fireseed 2009-08-02
  • 打赏
  • 举报
 回复
非常经典的旅行商问题，请看链接：

http://zh.wikipedia.org/wiki/旅行推销员问题

另外对楼主提出批评，您在提问前应该先用google，这样会更有效率，更节省资源！
加载更多回复（2）
基于蚁群优化算法的最优旅游路线优化模型
针对原有最优旅游路线优化模型关于最短路线的获取性能较差的问题，构建基于蚁群优化算法的最优旅游路线优化模型，设定旅游景点地理信息格式，完成地理信息抽取。设定路线选取流程，引用蚁群算法完成最优路线选取工作...
基于遗传算法的TSP算法-河北省旅游景点最优路线.zip
通过本实验的学习，使学生了解基于遗传算法的TSP算法，掌握并且熟练运用TSP算法求解旅游最短路线问题。...选择相关数据，利用TSP算法通过适应度选择，交叉，变异以及逆转操作，得出最终的旅游优化路线及其迭代图。
基于模拟退火算法算法计算中国地图旅游最优路线规划效果-源码
基于模拟退火算法算法计算中国地图旅游最优路线规划效果_源码
旅游线路优化问题 旅行商问题 遗传算法 C++求解 MATLAB拟合 加权求最优
旅游线路优化问题,旅游大陆是一个旅行商问题，我们通过c++,matlab等多种软件对于初始数据进行分析运算，并将其合理运用以建立模型，最后采用遗传算法对数据进行运算。
基于模拟退火算法算法计算中国地图旅游最优路线规划效果，matlab2021a仿真测试。
基于模拟退火算法算法计算中国地图旅游最优路线规划效果，matlab2021a仿真测试。
数据结构与算法

33,008

社区成员

35,326

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章