 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
TSP问题的最优化研究及求解实例
下载积分：1800
内容提示：TSP问题的最优化研究及求解实例
文档格式：PDF|
浏览次数：22|
上传日期： 20:10:57|
文档星级：
该用户还上传了这些文档
TSP问题的最优化研究及求解实例
官方公共微信       售前                       售后
工作时间周一至周五：9：00~23：00周六至周日：9：00~18：00咨询电话1工作时间周一至周日：9：00~18：00TSP问题的一种快速求解算法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
TSP问题的一种快速求解算法
上传于||暂无简介
阅读已结束，如果下载本文需要使用3下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩1页未读，继续阅读
你可能喜欢利用动态规划法求解旅行商问题（TSP）的C语言实现（一）
某推销员要从城市 出发，访问其它城市，，，各一次且仅一次，最后返回。为各城市间的距离矩阵。
问：该推销员应如何选择路线，才能使总的行程最短？
问题分析：记n个城市为1，2，，n.
对于给定的集合S属于{2,3,4,...n}
和元素k属于S，记C（S，k）是由城市1出发，遍历S中每个城市恰好一次，最后终止在城市k的最优费用.
则当S中只有一个元素k时，C（S，k）= D[1][k];
当S中有多于一个元素时， C（S，k）=
这一方程的求解要求对一切给定大小的集合S及S中的每个可能的元素k，计算 C（S，k）的值.
当S等于{2,3,4,...n}时，如果C（S，k）的值对任意属于S的元素k都已经通过计算得到，则最优环游的最费用为
算法复杂度分析：计算中所需的加法和比较的次数等于O(n^2*2^n)
空间复杂度：O(n*2^n)
算法改进：通过改进集合操作降低比较次数，利用二进制表示集合。确定元素k是否在集合S中的比较次数为1，从而降低了时间复杂度到O(n2^n)
#define MAX_N 10
(int)pow((double)x,(double)y);
//2 bits for vector
//struct path *lastN
path *lastN
struct path
struct path
*D[MAX_N];
if((mypow(2,i-1)&set)&0)
insertSet(int
if(inSet(i,set)==0)
set|mypow(2,i-1);
deleteSet(int
if(inSet(i,set))
~(mypow(2,i-1))&
print_path(struct path *p)
if(p==NULL)
printf("1");
print_path(p-&lastNode);
printf("-&%d",p-&current+1);
tsp(int n,
(*a)[MAX_N])
struct path
path *lastN
D[1] = NULL;
//当S中只有一个元素k时，C(S，k)=
temp = malloc(sizeof(struct path));
temp-&current =
temp-&cost = a[0][i];
temp-&lastNode = NULL;
temp-&next = D[1];
temp-&set = mypow(2,i-1);
//循环n-2遍,每次构造集合包含J个元素的子集
D[j] = NULL;//子集元素个数为J个的所有C(S,k)的链表的头
//利用address保存C(S,K)的信息。即保存相应struct
path结构的地址
address = malloc(sizeof(struct path
*)*mypow(2,n-1));
bzero(address,sizeof(&address));
p = D[j-1];
while(p!=NULL)
//判断元素i是否已经在p-&set集合中
//如果在这个集合中了不能利用元素i和p-&set构建新的子集了。
//因为每个子集中的元素是唯一
if(inSet(i,p-&set)==0)
//当S中有多于一个元素时,C(S，k)等于任意一个属于S-k集合的子集m，C(s-k,m)+d(m,k)中最小的一个，
set = insertSet(i,p-&set);
//判断C(S,k)是否已经计算过
//如果计算过，比较cost值，取小的
//不存在的话，就创建一个结构体struct
path保存C(S,k)的信息
if(address[set]!=NULL&&address[set]-&current==i)
cost = p-&cost + a[p-&current][i];
address[set]-&cost)
address[set]-&cost =
address[set]-&lastNode =
temp = malloc(sizeof(struct path));
temp-&current =
temp-&cost = p-&cost +
a[p-&current][i];
temp-&set =
temp-&lastNode =
temp-&next = D[j];
address[set]=
free(address);
//这一方程的求解要求对一切给定大小的集合S及S中的每个可能的元素k，计算 C(S，k）的值
//当S等于{2,3,...n}时，如果C(S，k)的值对k属于S都已经通过计算得到，则最优环游的最小费用为
//C(S,k)+d(k,1)中最小的一个。
mincost = -1;
p = D[n-1];
if(mincost==-1 ||
mincost & p-&cost + a[p-&current][0])
mincost = p-&cost + a[p-&current][0];
lastNode =
//打印计算结果
printf("mincost=%d\n",mincost);
//打印路径
print_path(lastNode);
printf("-&1\n");
argc, char
a[MAX_N][MAX_N]=
{ { 0, 10, 20, 30, 40, 50},
{12, 0, 18, 30, 25, 21},
{23, 19, 0, 5, 10, 15},
{34, 32, 4, 0, 8, 16},
{45, 27, 11, 10, 0, 18},
{56, 22, 16, 20, 12, 0}
EXIT_SUCCESS;
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。您现在的位置：&&>>&&>>&&>>&&>>&正文
c++使用蚁群算法解决TSP问题
　　TSP问题，旅行商问题：假如一个旅行商人要拜访n个城市，他必须选择所有要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。选择全部路径中的最小值。TSP具有NP计算复杂度（NP是指在非确定性图灵机上有多项式时间算法的问题）。TSP问题是数图论中重要的一个问题，即"已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路".
　　蚁群算法：蚁群算法是一种基于种群，通过模拟蚁群采集食物的过程的启发式搜索算法。蚂蚁通过释放信息素来记录路径，并趋向于走信息素量较多的路径来寻找最佳路径。其中一些限制的参数。
　　1.信息素的总量：蚂蚁拥有的信息素是有一定总量的，则在出发出信息素量较多，在一定距离后信息素会用尽，以防止其越走越远。
　　2.观测范围：蚂蚁有一定的观测范围，会选择信息素较多的路径。
　　3.出错概率：蚂蚁有一定的出错概率，会不往信息素最多的区域走。这使算法不过早的收敛。
　　4.信息素的消减速度：信息素以一定的速度消减，使一些不合适的路径上的信息素能消失，以减少对蚂蚁的干扰。
　　5.记忆能力：蚂蚁应该记住之前总过的路径，以防止回头，但是这个值较大时，会较低效率。
　　结合TSP问题，应做的一些改进：
　　蚂蚁数量为m,城市数量为n,城市间的距离为D[ i ] [ j ].蚂蚁行走的过程不应该是以一定速度行走，而是以 一个时间段进行行走，在这个时间段内，每个蚂蚁都能完整的从一个城市走到另一个城市。则在n个时间段后，蚂蚁完成了一次回路，则n个时间段合起来为一次循环，计循环次数为K.每只蚂蚁在一个循环中走过的城市编号，保存在 Path [m] [n];中，对于Path[m][0]]默认为出发点，则蚂蚁无法走路径中的点，则最后一个点不是初始点，但之后要回到初始点，要注意一下。
　　对于这个系统，应该选择标记的是点还是边，即蚂蚁留下信息素的地方是边还是点。暂时使用边，以方便之后的信息素消散的操作。虽然对于一个点去选取其下一个路径来说，下一个点上的信息素浓度与下一条边上的浓度效果是相同的，但由于这是完全图，对于其他点在选取边时，会被其他点的最佳选取所增加的信息素所干扰。
　　对于信息素，在蚁群算法中有两种信息素，一种是找到食物的蚂蚁留下的信息素，一种是找到家的蚂蚁留下的信息素。而在TSP中，蚂蚁肯定会找到家，则只有一种信息素。则每完成一次循环后，进行信息素的更新。信息素的更新公式：
　　Phe [ i ][ j ] = Dis* Phe[i][j] + DPhe[i][j]
　　Phe 表示 每条边上的信息素浓度，Dis为信息素消逝的速率，DPhe为本次循环内的边ij的信息素增加量。DPhe的值为 每个蚂蚁在本次循环留在路径ij上的信息素量KDPhe的总和，对于KDPhe有三种模型，Ant-Circle System , Ant-Quantity System 和 Ant-Density System.效果最好的为第一种。具体为
　　Ant-Circle System : KDPhe = Q / LK 或0（当蚂蚁未经过此路径时。Q为一个常量，LK为这个循环中，此蚂蚁的总路程）
　　Ant-Quantity System : KDPhe = Q / D[i][j] 或0
　　Ant-Density System .: KDPhe = Q 或 0
　　显然，第一种的效果更好，当蚂蚁的总路程越短，使其留下来的信息素量越高。
　　代码如下：
　　//使用10个蚂蚁，进行10个城市的TSP问题求解。
　　const int MMax = 9999;//蚂蚁数量，蚂蚁数量根据城市数量决定。
　　const int NMax = 500;//城市数量最大数量，超过出错
　　int m,n;//蚂蚁数量与城市数量
　　const double Q = 999 ;//常量
　　const int K = 1000;//循环总次数
　　int D[NMax][NMax];//路径长度
　　double Phe[NMax][NMax];//边对应的信息素浓度
　　int LK;//蚂蚁此循环中的总路径长度
　　int Path[MMax][NMax];//记录蚂蚁的路径，用于防止走重复的路。记录的是点
　　//蚂蚁当前所在点
　　int i,j,k,p;//循环使用
　　double Dis = 0.1;//每次信息素 消失的速率
　　int sameNum,samePhe[NMax];//每次去寻找信息素最多的边，如初始情况，信息素量都相同时，要
　　//随机的去从中选取边。
　　int bugNum,bugTry[NMax];//出错情况下进行的选择
　　double bugP = 0.90;//每一次操作的出错概率
　　//后来发现，出错概率要结合蚂蚁数与城市数进行判断，而定值Q为估计距离
　　//出发点，城市编号从0 - n-1.
　　double M//用来选取最多信息素的边
　　bool Passed[NMax];//用来判断城市是否已经经过，是否可以选取
　　int main（）
　　//载入数据
　　fstream f（"data.txt",ios::in）；
　　if（ n & NMax）//本来想直接赋值，后来又决定从文件中读入。
　　return 0;
　　for（i = 0;i&N;I++） f !="i）" if（j++） for（j="0;j&n"》D[i][j];
　　for（i = 0;i &i++）
　　D[i][i] = 0;
　　if（start & n-1）return 0;//没必要的检测，如果文件未正确书写，发生意外的错误，概不负责。
　　f.close（）；
　　for（i = 0;i &i++）
　　for（j = 0; j &j++）
　　Phe[i][j] = 1;//初始化每条边上的信息素浓度
　　for（i = 0;i&i++）
　　Path[i][0] =//每只蚂蚁的出发点都固定
　　m = 999;//蚂蚁数为城市数的2倍，后来发现不够
　　for（k = 0;k & K;k++）{
　　for（i = 0;i &i++）
　　for（j = 0; j &j++）
　　Phe[i][j] *= D//每次循环后，进行信息素的消逝
　　srand（（unsigned）time（NULL））；
　　for（i = 0;i &i++）{//对于每只蚂蚁，进行一次循环
　　for（j = 0;j &j++）
　　Passed[j] =
　　Passed[ant] =
　　for（j = 1;j &j++）{//每只蚂蚁选n-1次边
　　Max = 0;
　　sameNum& = 0 ;
　　bugNum = 0;
　　for（p = 0;p &p++）
　　if（！Passed[p]）
　　Max = Max & Phe[ant][p] ? Max : Phe[ant][p] ;//寻找周围边上信息素的最大值
　　for（p = 0;p &p++）
　　if（Max == Phe[ant][p]）
【责编:ivy】
?&[]?&[]?&[]?&[]?&[]?&[]?&[]?&[]?&[]?&[]
相关产品和培训
　友情推荐链接
　认证培训
　专题推荐
　?　?　?　?　?　?　?　?　?　?
　今日更新
?&?&?&?&?&?&?&?&?&?&
　社区讨论
　博客论点
　频道精选
　C/C++频道相关导航}