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

11S103001 郝亚峰 2 班 第十次算法作业 1、完成旅行商问题。 解：旅行商问题的求解方案如下： a) 对代价矩阵进行预处理，处理的目的是为了使每行每列都至少有一个0 ，若果该行 没有0 元素，则该行的元素都减去该行中最小的那一个元素，列也同样处理。把所 有可能的解作为根节点，把代价矩阵中减去的所有值加起来构成旅行商问题最优解 代价的下界，同时该下界作为根节点的代价。 b) 分支的策略采用爬山法，选择所有子节点中代价最小的进行进一步分支，产生分支 的方法如下： a) 选择边(i, j)，产生“包含边(i, j)”和“不包含边(i, j)”的左右两个子节点。选择 边(i, j)要满足条件cost(i, j)=0 and (i,j)=arg max{min{cost(i, k)}+min{cost(h, j)}} ，即 使得左子节点的代价下界不变，使右子节点的代价下界增加最大，增加为根节 点的代价加上min{cost(i, k)}+min{cost(h, j)}。 b) 修改代价矩阵，对于左子节点，因为其中已经包含了(i, j)，所以把第i 行和第j 列的元素都删掉，把(j,i)的代价改为∞；然后对新的代价矩阵进行 1)中那样预 处理，把所有减掉的值加到左子节点的代价上。对于右子节点，将(i, j)在代价 矩阵中值置为∞，然后进行与1)中相同的处理，把所有的减掉的值加到右子节 点的代价上(对于右子节点代价是否要加上这部分值，我们后面会讨论，对于这 个例子我们先按加上算，但是个人觉得是不合理的)。 c) 不断的进行步骤2)，但是要避免产生局部回路，直到找到一个可能的解，记录该解 的代价，把树中所有代价大于该值的节点全剪掉，对于剩下的节点再进行分支，找 到一个可能的解，若其代价小于之前的代价，则记录该代价，并用这个代价进行之 后的剪枝，直到遍历所有的分支，找到最优解。 简单分析一下上述方案的合理性：首先，将解集划分为包含某一条边和不包含某一条边 的两个子集，不会有情况漏掉；其次每次都更新矩阵，进行1)中的处理，这样保证每次 都能找到满足划分条件的边；最后，采用2) 中的条件选择边，是的左子节点下界增加的 小，而右子节点的增加的大，这样利用爬山策略，可以很快的找到可能解的代价，而且 这个代价还是比较小的，对于右子节点代价增加的比较大，可以在很早的阶段进行剪枝， 提高效率。 下面我们来完成课件中旅行商问题。 图1 是最原始的代价矩阵，经过步骤1)的处理(如图2 所示)，变为图3 所示的数据。将 图2 中的减掉的数据(red color)加起来即为根节点的代价(可能解的下界)，为96 。 图1 原始代价矩阵 图2 对原始代价矩阵预处理 图3 经过变换后的代价矩阵 下面我们按照 2) 中的条件来选择边(i,j)来进行对代表所有解的集合的根节点进行扩展子 节点。在图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,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