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

《分支界限算法解决旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、i,j)在代价矩阵中值置为∞，然后进行与1)中相同的处理，把所有的减掉的值加到右子节点的代价上(对于右子节点代价是否要加上这部分值，我们后面会讨论，对于这个例子我们先按加上算，但是个人觉得是不合理的)。c)不断的进行步骤2)，但是要避免产生局部回路，直到找到一个可能的解，记录该解的代价，把树中所有代价大于该值的节点全剪掉，对于剩下的节点再进行分支，找到一个可能的解，若其代价小于之前的代价，则记录该代价，并用这个代价进行之后的剪枝，直到遍历所有的分支，找到最优解。简单分析一下上述方案的合理性：首先，将解集划分为

4、包含某一条边和不包含某一条边的两个子集，不会有情况漏掉；其次每次都更新矩阵，进行1)中的处理，这样保证每次都能找到满足划分条件的边；最后，采用2)中的条件选择边，是的左子节点下界增加的小，而右子节点的增加的大，这样利用爬山策略，可以很快的找到可能解的代价，而且这个代价还是比较小的，对于右子节点代价增加的比较大，可以在很早的阶段进行剪枝，提高效率。下面我们来完成课件中旅行商问题。图1是最原始的代价矩阵，经过步骤1)的处理(如图2所示)，变为图3所示的数据。将图2中的减掉的数据(redcolor)加起来即为根节点

5、的代价(可能解的下界)，为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)

6、=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(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)

7、+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所示的二叉树，左子节点为“包含(4,6)”，其代价下界暂时不变，仍为96，右子节点为“不包含(4,6)”，由于其代价增加了32，故为128。图4选择边(4,6)划分解集然后，我们还得对左右子节点的矩阵，进行相应的处理，对于“包含(4,6)”将矩阵中的第4行，第6列元素都删掉，把原来矩阵中(6,4)改为∞，然后按照步骤1)中进行预处理，

8、发现第五列无0元素，故第5行元素都减去3，如图5所示。图5修改后的包含(4,6)的代价矩阵所以，右子节点的代价加上3，变为96。对于左子节点，将(4,6)变为∞，也同样按照步骤1)中进行同样处理，发现第4行元素中无0元素，则第四行都减去该行最小的元素32，如图6所示，所以右子节点代价增加32变为160。图6修改后的不包含(4,6)的代价矩阵所以此时的二叉树如图7所示。图7将左右子节点加入后最终的二叉