欢迎来到天天文库
浏览记录
ID:50250460
大小:116.50 KB
页数:13页
时间:2020-03-07
《TSP问题算法分析.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、算法第二次大作业TSP问题算法分析021251班王昱(02125029)一.问题描述“TSP问题”常被称为“旅行商问题”,是指一名推销员要拜访多个地点时,如何找到在拜访每个地点一次后再回到起点的最短路径。TSP问题在本实验中的具体化:从A城市出发,到达每个城市并且一个城市只允许访问一次,最后又回到原来的城市,寻找一条最短距离的路径。二.算法描述2.1分支界限法2.1.1算法思想分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性
2、产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2.1.2算法设计说明设求解最大化问题,解向量为X=(x1,…,xn),xi的取值范围为Si,
3、Si
4、=ri。在使用分支限界搜索问题的解空间树时,先根据限界函数估算目标函数的界[down,up],然后从根结点出发,扩展根结点的r1个孩子结点,从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算
5、可能的目标函数bound(x1),其含义:以该结点为根的子树所有可能的取值不大于bound(x1),即:bound(x1)≥bound(x1,x2)≥…≥bound(x1,…,xn)若某孩子结点的目标函数值超出目标函数的下界,则将该孩子结点丢弃;否则,将该孩子结点保存在待处理结点表PT中。再取PT表中目标函数极大值结点作为扩展的根结点,重复上述。直到一个叶子结点时的可行解X=(x1,…,xn),及目标函数值bound(x1,…,xn)。2.2A*算法算法思想对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的
6、估价,应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s,通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值,并有f*(n)=g*(n)+h*(n)。假设f函数是对f*函数的一种估计,并有f(n)=g(n)+h(n),其中g函数是对g*的估计,h函数是对h*的一种估计。f(n)包括两个部分,其中g(n)表示到达n节点时,已付出代价的估计;而h
7、(n)表示从n节点到达目标节点ti将要付出代价的估计。按f(n)=g*(n)+h*(n)的值来排序ff表的节点,f值小者优先。通常称这种算法为A算法。在A算法的基础上,进一步限制h(n)函数,使得搜索图中的每一个节点n,能满足h(n)<=h*(n)、称h函数取h*的下界。这种算法叫A*算法。对ff里的每一个节点做评估函数F分为两部分G和H:假设从A城市走到X城市,又走到Y城市,所以G可表示为:G=A到X的距离+X到Y的距离;未走的的城市数=(总城市数+1)-目前城市的层数。为什得加1,因为最后得走回初始城市,所以总路径的城市数为总城市数
8、+1。H=未走的城市数×目前的最小距离;F=G+H;计算ff表里每个节点的F值,F值最小的节点作为活路径,把它加到bestpath中。一.算法代码3.1分支界限法#include#include#defineNoEdge1000structMinHeapNode{intlcost;//子树费用的下界intcc;//当前费用intrcost;//x[s:n-1]中顶点最小出边费用和ints;//根节点到当前节点的路径为x[0:s]int*x;//需要进一步搜索的顶点是//x[s+1:n-1]struc
9、tMinHeapNode*next;};intn;//图G的顶点数int**a;//图G的邻接矩阵//intNoEdge;//图G的无边标记intcc;//当前费用intbestc;//当前最小费用MinHeapNode*head=0;/*堆头*/MinHeapNode*lq=0;/*堆第一个元素*/MinHeapNode*fq=0;/*堆最后一个元素*/intDeleteMin(MinHeapNode*&E){MinHeapNode*tmp=NULL;tmp=fq;//w=fq->weight;E=fq;if(E==NULL)retu
10、rn0;head->next=fq->next;/*一定不能丢了链表头*/fq=fq->next;//free(tmp);return0;}intInsert(MinHeapNode*hn){if(head
此文档下载收益归作者所有