分支界限算法解决旅行商问题

《分支界限算法解决旅行商问题》由会员分享，可在线阅读，更多相关《分支界限算法解决旅行商问题（10页珍藏版）》请在金锄头文库上搜索。

1、11S103001 郝亚峰郝亚峰 2 班班 第十次算法作业第十次算法作业 1、 完成旅行商问题。 解：旅行商问题的求解方案如下： a) 对代价矩阵进行预处理，处理的目的是为了使每行每列都至少有一个 0，若果该行 没有 0 元素，则该行的元素都减去该行中最小的那一个元素，列也同样处理。把所 有可能的解作为根节点，把代价矩阵中减去的所有值加起来构成旅行商问题最优解 代价的下界，同时该下界作为根节点的代价。 b) 分支的策略采用爬山法，选择所有子节点中代价最小的进行进一步分支，产生分支 的方法如下： a) 选择边(i, j)，产生“包含边(i, j)”和“不包含边(i, j)”的左右两个子节点。选择

2、 边(i, j)要满足条件 cost(i, j)=0 and (i,j)=arg maxmincost(i, k)+mincost(h, j)，即 使得左子节点的代价下界不变，使右子节点的代价下界增加最大，增加为根节 点的代价加上 mincost(i, k)+mincost(h, j)。 b) 修改代价矩阵，对于左子节点，因为其中已经包含了(i, j)，所以把第 i 行和第 j 列的元素都删掉，把(j,i)的代价改为；然后对新的代价矩阵进行 1)中那样预 处理，把所有减掉的值加到左子节点的代价上。对于右子节点，将(i, j)在代价 矩阵中值置为，然后进行与 1)中相同的处理，把所有的减掉的值加

3、到右子节 点的代价上(对于右子节点代价是否要加上这部分值， 我们后面会讨论， 对于这 个例子我们先按加上算，但是个人觉得是不合理的)。 c) 不断的进行步骤 2)，但是要避免产生局部回路，直到找到一个可能的解，记录该解 的代价，把树中所有代价大于该值的节点全剪掉，对于剩下的节点再进行分支，找 到一个可能的解，若其代价小于之前的代价，则记录该代价，并用这个代价进行之 后的剪枝，直到遍历所有的分支，找到最优解。 简单分析一下上述方案的合理性：首先，将解集划分为包含某一条边和不包含某一条边 的两个子集，不会有情况漏掉；其次每次都更新矩阵，进行 1)中的处理，这样保证每次 都能找到满足划分条件的边；最

4、后，采用 2)中的条件选择边，是的左子节点下界增加的 小，而右子节点的增加的大，这样利用爬山策略，可以很快的找到可能解的代价，而且 这个代价还是比较小的， 对于右子节点代价增加的比较大， 可以在很早的阶段进行剪枝， 提高效率。 下面我们来完成课件中旅行商问题。 图 1 是最原始的代价矩阵，经过步骤 1)的处理(如图 2 所示)，变为图 3 所示的数据。将 图 2 中的减掉的数据(red color)加起来即为根节点的代价(可能解的下界)，为 96。 图 1 原始代价矩阵 图 2 对原始代价矩阵预处理 图 3 经过变换后的代价矩阵 下面我们按照 2)中的条件来选择边(i,j)来进行对代表所有解的

5、集合的根节点进行扩展子 节点。在图 3 中，找出所有的 cost(i, j)=0，然后选择边(i, j)使得不包含边(i, j)时的右子节 点的代价增加的最大， cost(1, 2)=0，“不包含边(1, 2)” 的代价增加为 cost(1,6)+cost(7, 2)=6， 同理所有满足 cost(i, j)=0 的边，我们计算不包含其的代价增量，见表 1。 表 1 图 3 中不包含 cost(i, j)=0 的边的代价下界的增量 Cost(i, j)=0 不含(i,j)时代价增量 Cost(i, j)=0 不含(i,j)时代价增量 (1,2) cost(1,6)+cost(7,2)=6 (6

6、,1) cost(6,7)+cost(2,1)=0 (2,1) cost(2,6)+cost(6,1)=12 (6,7) cost(6,1)+cost(3,7)=5 (3,5) cost(3,2)+cost(2,5)=18 (7,2) cost(7,3)+cost(1,2)=0 (4,6) cost(4,1)+cost(5,6)=32 (7,3) cost(7,2)+cost(6,3)=8 (5,6) cost(5,1)+cost(4,6)=3 (7,4) cost(7,2)+cost(5,4)=7 根据上表， 我们第一次选的边为(4,6)。 生成如图 4 所示的二叉树， 左子节点为 “包含(

7、4,6)” ， 其代价下界暂时不变，仍为 96，右子节点为“不包含(4,6)” ，由于其代价增加了 32，故 为 128。 图 4 选择边(4,6)划分解集 然后，我们还得对左右子节点的矩阵，进行相应的处理，对于“包含(4,6)”将矩阵中的 第 4 行， 第 6 列元素都删掉， 把原来矩阵中(6,4)改为， 然后按照步骤 1)中进行预处理， 发现第五列无 0 元素，故第 5 行元素都减去 3，如图 5 所示。 图 5 修改后的包含(4,6)的代价矩阵 所以，右子节点的代价加上 3，变为 96。对于左子节点，将(4,6)变为，也同样按照步 骤1)中进行同样处理， 发现第4行元素中无0元素， 则第

8、四行都减去该行最小的元素32， 如图 6 所示，所以右子节点代价增加 32 变为 160。 图 6 修改后的不包含(4,6)的代价矩阵 所以此时的二叉树如图 7 所示。 图 7 将左右子节点加入后最终的二叉树 按照爬山策略进行分支，所以选择代价为 99 的右子节点进行扩展，同样，我们要在图 5 所示的代价矩阵中选择一条边来进行划分右子节点所代表的解集， 需要计算不包含边(i,j) 时，代价的增量，如表 2 所示。 表 2 图 5 中不包含 cost(i, j)=0 的边的代价下界的增量 Cost(i, j)=0 不含(i,j)时代价增量 Cost(i, j)=0 不含(i,j)时代价增量 (1

9、,2) cost(1,4)+cost(7,2)=9 (6,7) cost(6,1)+cost(3,7)=5 (2,1) cost(2,5)+cost(6,1)=17 (7,2) cost(7,3)+cost(1,2)=0 (3,5) cost(3,2)+cost(2,5)=18 (7,3) cost(7,2)+cost(6,3)=8 (5,1) cost(5,4)+cost(6,1)=4 (7,4) cost(7,2)+cost(5,4)=4 (6,1) cost(6,7)+cost(2,1)=0 所以根据上表，我们选择(3,5)来划分，产生子节点“包含(3,5)”和“不包含(3,5)” ，右

10、儿 子的代价暂时为 99，左儿子的代价暂时为 99+18=117。分别对左右儿子对矩阵进行相应 的处理之后，左儿子的代价矩阵如图 8 所示，右儿子的代价矩阵如图 9 所示，第 3 行的值减掉 1，第 5 列的值减掉 17，一共减掉 18，所以右儿子代价为 117+18=135。 图 8 修改后的图 5 包含(3,5)所对应的代价矩阵 图 9 修改后的图 5 不包含(3,5)所对应的代价矩阵 所以，此时生成的二叉树如图 10 所示。 图 10 图 7 左儿子做扩展 重复以上步骤， 选择 “包括(3,5)” 的左儿子进行扩展， 在图 8 所示的矩阵上进行选择(i,j)。 选择的表如表 3 所示。

11、表 3 图 8 中不包含 cost(i, j)=0 的边的代价下界的增量 Cost(i, j)=0 不含(i,j)时代价增量 Cost(i, j)=0 不含(i,j)时代价增量 (1,2) cost(1,4)+cost(7,2)=9 (6,7) cost(6,1)+cost(5,7)=25 (2,1) cost(2,7)+cost(6,1)=26 (7,2) cost(7,3)+cost(1,2)=0 (5,1) cost(5,4)+cost(6,1)=4 (7,3) cost(7,2)+cost(6,3)=8 (6,1) cost(6,7)+cost(2,1)=0 (7,4) cost(7,

12、2)+cost(5,4)=4 所以，我们选择边(2,1)来扩展，得到的“包括边(2,1)”的左儿子的下界为：99+4=103， 未修改完全的矩阵如图 11 所示，第 5 行要减去 4。右儿子的下界为 99+26=125，其对应 的代价矩阵如图 12 所示。 2841018413072所有解的集合（L.B=96）包括边(4,6)（L.B=99）不包括(4,6)（L.B=160）包括边(3,5)（L.B=99）不包括(3,5)（L.B=135）图 11 未修改完全的图 8 包含(2,1)所对应的代价矩阵 图 12 未修改完全的图 8 不包含(2,1)所对应的代价矩阵 所以，我们最终形成新的二叉树如

13、图 13 所示。 图 13 图 10 左儿子做扩展 之后也是同样处理，只不过我们不叙述详细过程了，画出得到第一个可能的解时的二叉 树，如图 14 所示。 图 14 对于包括(7,3)的节点不能再继续扩展 -4-26所有解的集合（L.B=96）包括边(4,6)（L.B=99）不包括(4,6)（L.B=160）包括边(3,5)（L.B=99）不包括(3,5)（L.B=135）不包括(2,1)（L.B=151）包括边(2,1)（L.B=103）所有解的集合（L.B=96）包括边(4,6)（L.B=99）不包括(4,6)（L.B=160）包括边(3,5)（L.B=99）不包括(3,5)（L.B=135

14、）不包括(2,1)（L.B=151）包括边(2,1)（L.B=103）包括边(6,7)（L.B=103）不包括(6,7)（L.B=161）包括边(7,3)（L.B=103）不包括(7,3)（L.B=269）包括边(1,4)（L.B=112）不包括(1,4)（L.B=103）包括边(5,2)（L.B=126）不包括(5,2)（L.B=112）包括边(5,2)（L.B=117）不包括(5,2)（L.B=103）空集空集空集在此处，我们还要讨论一开始步骤 2)中的问题，即对于不包括(i,j)的节点的代价，是否 除了加上增加的代价之外，还要加上矩阵修改之后减掉的所有的值。其实应该是不用加 的，因为这两

15、个值表示的意义是相同的，就是不包括边(i,j)，那么 i 必须从指向某一点， 并且， 必须有另一个点指向j， 找到i行的最小值， j列的最小值(当然都是除了(i,j)之外的)， 两者相加即为增加的代价，在新的矩阵中，我们把不包含(i,j)的代价矩阵的第 i 行第 j 列 的位置置为；这样只有第 i 行和第 j 列可能没有 0 元素，所以要减去第 i 行，第 j 列的 最小值，这两个最小值即为求代价增加的那两个值，是相同的，所以不需要重复加。所 以我们对上面生成的二叉树进行改正，如图 15 所示。 图 15 对图 14 修正 所以，我们得到一个可能的解 4-6-7-3-5-2-1-4，其代价为

16、126，那么我们就可以用这个代 价作为上界来剪枝，对于所有大于等于 126 的节点都可以考虑不用扩展了。而且对于这 个问题，我们在不断的迭代步骤 2)的时候，可能有满足划分条件的边，但是加入这条边 会产生回路， 那么我们就不能取这样的边， 所有的cost(i, j)=0的边都不满足， 只能取cost(i,j) 0 的边，但是从代价小的便开始取，按这条边进行分支，对于分支的各个子节点的代 价矩阵还是按照步骤 2)的进行，例如图 15 中的节点“包括边(7,3)” 。所以我们接着来扩 展图 15 中的“不包括(3,5)”和“不包括(2,7)”节点，分别如图 16 和图 17 所示。 所有解的集合（L.B=96）包括边(4,6)（L.B=99）不包括(4,6)（L.B=128）包括边(3,5)（L.B=99）不包括(3,5)（L.B=117）不包括(2,1)（L.B=125）包括边(2,1)（L.B=103）包括边(6,7)（L.B=103）不包括(6,7)（L.B=132）包括边(7,3)（