您的当前位置:首页正文

基于Visual C++的旅行售货员问题的分支限界算法

2020-01-10 来源:爱站旅游
导读基于Visual C++的旅行售货员问题的分支限界算法
煎~一堡……皇…一墅 jJlAN(:0MP j rE鹣 基于Visual C++的旅行售货员问题的 分支限界算法 陈自力 (福建船政交通职业学院福建福州350007) 【摘要】:旅行售货员问题是经典的NP问题。本文对旅行售货员问题的分支限界算法进行了分 析,给出了算法过程,并用Visual c++实现该算法。 【关键字】:旅行售货员问题;分支限界;c++ 1、旅行售货员问题 上述过程。当找到所求的解或活结点表为空时停止上 旅行售货员问题是一个经典的算法问题,它的描 面过程。 述如下:某个售货员打算到几个城市去销售商品,每 3、算法实现过程 个城市之间的距离已知。售货员要选择一条线路,依 旅行售货员问题的解空间是一个排序树。与在子 次经过每个城市,最后回到出发点的路线,使总的距 集树中进行最小花费和最大效益分枝定界搜索类似。 离最小。把旅行售货员问题用图来描述,设G=(v,E)是 这种问题实现的方法有两种。 一个带权无向图。V为每个顶点(城市),E为每个顶点 (1)使用一个优先队列,队列中的每个节点中都 (城市)见的距离,图中各边的费用(权)E为正数。图 包含到达根的一条线路。 的一条遍历路线是包括V中的每个顶点在内的一条 (2)保留某个优先队列和某个部分解空间树,优 回路。遍历每个顶点的费用是经过路线上所有边的费 先队列中的节点没有包含到达根的一条线路。 用E之和。针对图G,旅行售货员问题就是要找出费 最小花费的旅行路径是我们要寻找的,所以可以 用最小的遍历路[1]。 采用最小花费分枝定界法,采用最小的堆来表示活结 2、分支限界法 点的优先队列。 分支限界法【l1和回溯法相似,都是在解空间树T 首先利用蒙特卡罗f1]算法,将节点1..k随机排序, 上搜索问题解。不同之处在于,回溯法与分支限界法 同时计算此排列的哈密顿回路的长度并保存。例如1 最终的求解内容不同。分支限界法是找出T中满足要 3 2 4序列,则此排列长度为: 求的一个解,或是在满足约束条件的解中找出使某一 c(1,3)+c(3,2)+c(2,4)+c(4,1)。 目标函数值达到极大或极小的解,即在某种意义下的 然后for(int i=2;i<=k;i++) 最优解t 1。回溯法是找出T中满足要求的所有解。 for(int j=2.j<:kIj++) 分支限界法通常以最小花费也称最大收益优先 {判断交换节点i,j后哈密顿回路的长度有没有 或者广度优先的方法搜索问题的解空间树。问题的解 变短,有的话进行交换并更新最优值,否则不交换。} 空间树是一棵有序树,它用来表示问题解空间的,比 计算此随机排列哈密顿回路长度的最小值多次 较常见的是排序树和子集树。回溯法与分支1限界法 执行(执行1秒)取最小值作为最优长度。 在搜索问题的解空间树的时候对当前扩展结点所采 接着用随机穷举,产生一个序列(一般是不回路 用的扩展方式不同。在分支限界法中,每个活结点只 的1,然后再进行回路调整. 能成为扩展结点一次。我们选中某个活成为扩展结 4、使用C++实现算法 点,就一下子产生它所有的儿子结点。在它的儿子结 4.1程序结构说明 点中,舍弃那些导致非最优解或不可行解的儿子结 void Swap(int&a,int&b)// ̄j"两个数进行交换 点,剩余儿子结点加入活结点表中。接下来,继续从活 int computeO//函数用来计算排列的哈密顿回路的长度 结点表中选取下一结点成为当前扩展结点,一直重复 int valuechange(inti,intj)//' ̄数改变的值计算 2o14 ̄8期J福建电脑 ・85・ : 煎...~堡……熏… 艟 j;A CO UT蠢 void mainO//主函数 4.2程序 #include<iostream.h>// ̄入输出语句控制 #include<fstream.h>//输入输出文件控制 #include<stdlib.h>//包含exit语句头文件 #include<time.h>//用来读时间函数 intm,n;//读入M个点N条边 int**value;//用来存放每条边的权值 int temporder;//j ̄来存放临时的遍历的序列 void Swap(int&a,int&b)//两个整数进行交换 { int temp; temp a;a=b;b=temp; l int computeO//2 ̄J--个随机序列的权值进行调整 { int distance=0; f0r(int i=1;i<m+1;i++) distance+=value[temporder[i]][temporder[i+1]]; return distance; } int valuechange(int i,int j) { int change=0: change=value[temporder[i]][temporder[i+1]]一value [temporder[j]][temporder[i+1]]; change=change+value[temporder[i—1]][temporder[i]]一 value[temporder[i一1]][temporder[j]]; change=change+value[temporder[J]][temporder[j+1]]一 value[temporder[i]][temporder[j+1]]; change:change+value[temporder[j一1]][temporder[j]]一 value[temporder[j一111[temporder[i]]; retum change; ) void main0 f clock_t start,end; start=clock0; inttempresult,result=10000000; ifstream input(”input.txt”);//打开输入文件 ofstream output(”output.txt”);愉出对象定义及实例化 input>>m>>n; value=new int*[m+1]; for(int i-0;i<=m;i++) value[i]:new int[re+1]: temporder=new int[m+2];//用来存放临时的序列 int*order=new int[m+13;//用来存放最小的权值序列 for(i=0;i<m+1;i++) for(int j:0Ij<m+1.j++) f value[i][i]=500000;//对其进行权值初始化 ・86・ 福建电脑I 2014年第8期 } for(i=0;i<n;i++) { int x,y,temp; input>>x>>y>>temp; value[x][y]=temp; } for(i=1;i<m+1;i++) order[i]:i; srand((unsigned)time(NULL)); dof for(i=1;i<m+1;i++) temporder[i]=i: temporder[m+1]:l; f0 =2;i<m+1;i++),/循环用来产生一个随机的可能序列如: (1),3,1,6,7,5,4,2.第一个1是不变的,每次都是变化后面的七位 数 ( int j=rand0%(m—i+1)+i; Swap(temporder[i],temporder[j]); } tempresult:compute O;n计算序列的非回路累加权 值. f0r(i=2;i<m+1;i++),/对权值进行调整.认其成为一个回路,回 到原点 for(int j=2Ij<m+1 ++) !-j) { int changenum valuechange(i,j); if(changenum>O) { Swap(temporder[i],temporder[j]); tempresuh=tempresult—changenum; } } if(tempresult<result) { result=tempresuh; for(i=1;i<m+1;i++) order[i]=temporder[i]; } end=clock0; )while(end—start<=985);,/要在时间0.985秒内运行完成 if(resuh>500000)///是否找到解. output<<”No Solution”<<endl; output<<resuh<<endl; for(i=1;i<m+1;i++)output<<order[i]<<””; ) 5、算法分析 上述算法需要O(n3)计算时间。(下转第155页) …一一……………一…………………… |UJ tA 丽 ……………………~ 修改相应语法及结构,完成程序扩展要求,达到掌握 一2.2在趣味教学中提高学习效果 借用计算思维的思想,首先,在前面的教学改革 系列相关知识点的目的。例如,学生可以通过模拟 “统计1—50中奇数的个数”源程序,对其进行程序扩 思路中提到的在教学中要和学生进行充分的互动合 展,加上数组、求和等其它知识实现新程序:从终端读 作,具体分三步,首先:设计案例的时候尽量按照学生 入10个数据到数组中,统计其中正数的个数,并计算 兴趣,设计学生感兴趣的案例。其次:提问法进行知识 它们之和。 点和案例的讲解。具体说就是对于一个知识点,在讲 之前先提问、然后留时间思考、最后解答问题,做到每 (2)具体案例分析:背包问题。 问题描述:有n种物品,物品i的重量为wi,价格 个知识点讲解过程都有一个自我主动思考过程,加深 为pj,背包所能承受的最大重量为W,限定每种物品 这些物品的重量总和不超过背包重量限制,且价格总 和尽可能大。 印象。最后:对于抽象知识点,可以采用喜闻乐见的通 3结语 只能选择0个或1个。求解将哪些物品装入背包可使 俗比喻提高学习的趣味性,增进理解。 将计算思维理念的趣味案例教学引入C语言教 思路:采用贪婪法求解背包问题,分多步完成背 学中,培养学生运用计算思维来解决计算机程序设计 包的装入,在每一步过程中利用贪婪准则选择一个物 的能力,对当今大学教育来说是一个有力的挑战。大 品装入背包。注意:贪婪准则可按照不同的标准进行 学计算机程序设计课程的改革探索就是为此所做的 划分,这里需要学生进行模拟的为价格准则。 工作之一,实践教学也证明,课程的改革还能大幅度 价格准则:从剩余的物品中选择可以装入背包的 地提高教学质量与教学效果,对今后进一步培养学生 价格最高的物品(没有超过背包的重量限制)重量准 解决实际问题和研发创新能力有重要的理论指导作 则:从剩下的物品中选择可以装入背包的重量最小的 用。 物品。 算法文字描述: 参考文献: l 1 j Wing J M.Computational Thinking lJ j.Communicaitons of ①将背包清空。 he ACM,2006,49(3):33—35. ②如果背包中的物品重量已达到背包的重量限 t[2]王飞跃.从计算思维到计算文化[J].中国计算机学会通讯, 制,则转⑤。 ③否则(即背包中的物品重量未达到背包的重量 限制1,则按照贪婪准则从剩下的物品中选择一个加入 2007,3(1 1):78-82. [3]陈国良,董荣胜.计算思维与大学计算机基础教育[J].中国 大学教育,2011(1):7-11. 背包,转②。 ④如果找不到这样的物品,则转⑤。 ⑤结束。 [4]何钦铭,陆汉权,冯博琴.计算机基础教学的核心任务是计 算思维能力的培养:“九校联盟(C9)计算机基础教学发展战略 联合声明”解读[J].中国大学教学,2010(9):22—32. (上接第86页) 采用分支限界算法解决旅行售货员问题,并通过编程 参考文献: 社.2004 计算机算法设计与分析[MI.北京:电子工业出版 在Visual C++进行实现。但是,算法还是有缺陷的,因 [1]王晓东.为旅行售货员问题是NP问题,找到的不一定是真正 需改进。 穆艳玲,李学武.遗传算法解TSP问题的并行实现[J].北京 的最小解。当n很大时,算法需要计算的时间较多,还 [2]联合大学学报(自然科学版).2006.2 [3]刘玉娟,王相海.0—1背包2问题的两种扩展形式及其解法, [I].计算机应用研究,2006 2ol4年第8期 l福建电脑 ・155・ 

因篇幅问题不能全部显示,请点此查看更多更全内容