您好、欢迎来到现金彩票网!
当前位置:ds视讯 > 分支限界搜索 >

分支限界法求解TSP问题程序设计说明书-Read

发布时间:2019-09-16 10:26 来源:未知 编辑:admin

  解 分支限界法求解 TSP 问题程序设计说明书 一、 TSP 问题描述: 旅行商问题,即 TSP 问题(Travelling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 现在给定 20 个城市的水平坐标信息文件:data.txt,寻求遍历这 20 个城市的最短路径的序列以及最短路程的数值。 二、 分支限界法描述: 分支与限界法的基本思想,是在分支接点上,预先分别估算沿着它的各个儿子结点向下搜索的...

  解 分支限界法求解 TSP 问题程序设计说明书 一、 TSP 问题描述: 旅行商问题,即 TSP 问题(Travelling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 现在给定 20 个城市的水平坐标信息文件:data.txt,寻求遍历这 20 个城市的最短路径的序列以及最短路程的数值。 二、 分支限界法描述: 分支与限界法的基本思想,是在分支接点上,预先分别估算沿着它的各个儿子结点向下搜索的路径中,目标函数可能取得的“界”,然后,把它的这些儿子结点和它们可能取得的“界”保存在一张结点表中,再从表中选取“界”最大或最小的结点向下搜索。常用优先队列来维护这张表,也可以使用堆结构来维护这张表。关于分支限界法的思想见参考文献[1] 需要指出的是分支限界法经过严密的推理,其寻找到的解释真正的最优解,而不是近似解。需要指出的是分支限界法经过严密的推理,其寻找到的解释真正的最优解,而不是近似解。 分支限界法求解货郎担问题的基本规律特征: 1. 费用矩阵(在此处既是距离矩阵)的特性及归约 理 引理 1:令 G=(V,E) 是一个有向赋权图,l 是图 G 的一条哈密尔顿回路,c 是图G 的费用矩阵,则回路上的边对应于费用矩阵 c 中的每行没列各一个元素。 理 定理 1:令 G=(V,E) 是一个有向赋权图,l 是图 G 的一条哈密尔顿回路,c 是图G 的费用矩阵,w(l)是以费用矩阵 c 计算的这条回路的费用。如果矩阵 c 是费用矩阵 c 的归约矩阵,归约常数为 h, ) (l w 是以费用矩阵 c 计算的这条回路的费用,则有: h l w l w + = ) ( ) ( PS:关于归约常数的定义参考[1] 定理二:令 G=(V,E) 是一个有向赋权图,l 是图 G 的一条哈密尔顿回路,c 是图G 的费用矩阵, c 是费用矩阵 c 的归约矩阵,令 c 是图 G 的邻接矩阵,则 l 也是 图 G 的一条最短的哈密尔顿回路 以上特性的证明见参考文献[1] 三、分支限界法求解货郎担问题的步骤 1、分配堆缓冲区,初始化为空堆 2、 建立父亲结点 X,令结点 X 的费用矩阵是 c X. ,把费用矩阵 c 复制到 c X. ,费用矩阵的阶数 k X. 初始化为 n,归约 c X. ,计算归约常数 h,令结点 X 的下界 h w X = . ,初始化回路的顶点邻接表 ad X. 3、由 c X. 中所有 0 =ijc 的元素 计算ijd 4、选取使ijd 达最大的元素kld 作为klD 选择边kVlV 作为分支方向 5、建立儿子结点Y 把 X 的费用矩阵 c X. 复制到 c Y. .把 X 的回路顶点邻接表 ad X.复制到 ad Y. , k X. 复制到 k Y. ;把 c Y. 中的元素klc 置为 ,归约 c Y. ;计算下界w Y. ;把结点Y 按 w Y. 插入最小堆中。 6、建立儿子结点 Y,把 X 的费用矩阵 c X. 复制到 c Y. ,把 X 的回路顶点邻接表 ad X.复制到 ad Y. , k X. 复制到 k Y. ,按回路顶点邻接表 ad Y. 把费用矩阵 c Y. 的有关元素置为 7、删去 c Y. 的第 k 行第 j 列元素,使 k Y. 减 1,从而使费用矩阵 c Y. 的阶数减 1 ,归约降阶后的费用矩阵 c Y. ,并计算结点 Y 的下界 w Y. 8、若 k Y. =2,直接判断最短回路的两条边,并登记到路线邻接表 ad Y. ,使 k Y. =0 9、把结点 Y 按 w Y. 插入最小堆中 10、取下堆顶元素作为结点 X,若 k X. =0,算法结束;否则,转向步骤 3 四、主要函数功能说明及实现: 1. float row_min(NODE *node,int row,float &second) 功能:返回由指针 node 所指向节点费用矩阵中第 row 行最小值,并把次小值回送与引用变量 second 中 2. float col_min(NODE *node,int col,float &second) 功能:返回由指针 node 所指向节点费用矩阵中第 col 列最小值,并把次小值回送与引用变量 second 中 3. float array_red(NODE *node) 功能:归约指针 node 指向的节点的费用矩阵 返回值为归约常数 4. float edge_sel (NODE *node,int &vk,int &vl) 功能:计算kld 并且搜索分支的边 返回 dkl 的值 5. void del_rowcol(NODE *node,int vk,int vl) 功能:删除费用矩阵当前kV 行 第lV 列的所有元素 6. void edge_byp(NODE *node,int vk, int vl) 功能:把 vk vl 表示的边登记到顶点邻接表 并旁路矩阵中有关的边 7. NODE *initial(float c[20][20],int n) 功能:初始化函数 8. void insert(HEAP *&heap,int &n_heap,HEAP z) 功能:向最小堆栈插入结点函数 9. HEAP delete_min(HEAP *&heap,int &n_heap) 功能:删除堆栈头结点函数 五、brandy3.cpp 程序执行流程及运行结果: 1.调用 distance.cpp 的生成文件 distance.txt, 将距离信息保存为费用矩阵 2.定义结点数据结构和堆数据结构 3.采用上述算法步骤计算最短路径 4.输出显示结果: 1.调用 distance.cpp 的生成文件 distance.txt, 将距离信息保存为费用矩阵 2.定义结点数据结构和堆数据结构 3.采用上述算法步骤计算最短路径 4.输出显示结果: The result of the path: A N K D H J O S G R P E M T F Q I B L C The total length is: 24.523 参考文献[1]:《算法设计与分析》郑宗汉 郑晓明 编著 清华大学出版社 p188

http://gamesbaby.net/fenzhixianjiesousuo/789.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有