程序说明 - search read.pudn.com.doc_第1页
程序说明 - search read.pudn.com.doc_第2页
程序说明 - search read.pudn.com.doc_第3页
程序说明 - search read.pudn.com.doc_第4页
程序说明 - search read.pudn.com.doc_第5页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

分支定界算法和程序运行结果的说明程序思想:注：用记事本阅读程序源代码时，请将“格式”“自动换行”去掉。本程序用C语言实现，故依据C语言的语法，数字0表示甲城市，数字49表示乙城市。矩阵m1和m2分别代表了50个城市中任意两个城市的距离和代价，而弗洛伊德算法可求出任意两个城市之间的最短距离和最小代价，我们分别用矩阵mindist5050和mincost5050来存储。假设当前我们位于第cur号城市（cur）,从0号城市（甲城市）到cur号城市的距离和代价分别用currentDist和currentCost来表示，那么就可以得到以下剪枝策略：如果currentDist + mindistcur49 = distBound 和currentCost + mincostcur49 = 1500两个条件中有一个满足，则进行剪枝，然后回溯。在上述的剪枝策略中，distBound表示剪枝的距离边界。我们可以把distBound的初始值设置为很大，当找到第一条可行通路后，就把该通路的路径总长赋值给distBound，这样当我们以后找到更小的通路时，再把更小的通路的路径总长赋值给distBound。如此循环，就逐渐缩短了所找到的通路的路径总长。至于对路径的搜索则采用深度优先搜索策略，用栈实现。当我们访问到某个城市cur，这把该城市入栈，并把该城市的访问标志visitedcur设置为1；当被访问到的城市不是乙城市且无满足条件的下一个相邻城市时，把当前城市出栈，并将visitedcur设置为0。依次寻找所有节点，直到访问到乙城市，此时就获得了一条可行通路。根据以上思想，得到以下的程序流程说明：1. 将m1.txt,m2.txt的数据读入两个5050的数组；2. 用弗洛伊德算法求出所有点对之间的最短距离和最小代价；3. 建立一个栈并初始化。首先把0结点（甲城市）入栈，然后每次取出栈顶的结点进行扩展，检查它的相邻结点并确定下一个当前最优路径上的结点，当确定扩展的结点后，将其入栈，更新distBound。如果发现超出当前的distBound或者费用的界（1500）,则进行剪枝，然后回溯；4. 当找到一个解后，则进行输出，然后回溯，栈指针回退两步，抛弃当前所找到的可扩展节点，继续搜寻新的路径上的节点；5. 如此进行，直到栈空，则得到了所有的满足条件的可行通路。输出中的最后一条就是满足条件的最小通路。可执行文件运行及结果说明：本程序用C语言编写实现，程序源代码文件为“分支定界实现源程序.c” ，在windows XP下用VC+6.0上编译运行通过，生成可执行文件“分支定界实现程序.exe” 。运行程序时，请将题目中所给的文件“m1.txt” 和“m2.txt”与可执行文件“分支定界实现程序.exe”放在同一个文件夹下，然后双击打开“分支定界实现程序.exe”即可运行程序。运行结果如下面的3个图所示：
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论