旅行商售货员问题的分支限界算法
姓名: 学号:
一、实验目的与要求
1、掌握旅行商售货员问题的分支限界算法;
2、区分分支限界算法与回溯算法的区别,加深对分支限界法的理解。
二、实验题:
编程实现:某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他
要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅
费)最小。
三、实验提示
旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列,
队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队
列,优先队列中 的元素并不包含到达根的路径。以下为第一种方法。
由于我们要寻找的是最小耗费的旅行路径,因此可以使用最小耗费分枝定界法。在实现过
程中,使用一个最小优先队列来记录活节点,队列中每个节点的类型为 。
每个节点包括如下区域: (从 到 的整数排列,其中 ),(一个整数,使
得从排列树的根节点到当前节点的路径定义了旅行路径的前缀 而剩余待访问的节
点是 ), (旅行路径前缀,即解空间树中从根节点到当前节点的耗
费),(该节点子树中任意叶节点中的最小耗费), (从顶点 出发
的所有边的最小耗费之和)。当类型为 的数据被转换成为类型 时,
其结果即为 的值。
代码:
!"#
$#
%$&
''宏定义
()*+,-.+/012''城市最大数目
()*+,34''两个城市之间费用的最大值
''全局变量
,5+6")*+,-.+/012)*+,-.+/012&
''表示城市间边权重的数组
,5+47&''表示实际输入的城市数目
0+,&''最小费用
0+,+8")*+,-.+/012&
''最小费用时的路径
''定义结点
59:
&''优先级
&''当前费用
&''剩余所有结点的最小出边费用的和