这一讲介绍货郎问题的分支 限界算法。我们先看看货郎问题的
定义,有n个城市, 任何两个城市之间都有距离,
ci到cj的距离等于cj到ci的距离, 那么它的解呢是,
一个排列,城市的排列,在这个排列下, 正好从第一个城市出发,所有的城市恰好走一次,
这个总的路线长度达到最短。也就是说从
ck1到ck2的距离加上ck2到ck3的距离,一直加到 ck
n-1 到ckn的距离,再加上ckn回到ck1的距离。
所有这个距离的总和达到最小,这就是
它的解的要求。下面我们看看这个算法设计。
这个算法设计它是一个回溯的算法,
加上分支限界,解向量 描述成一个n维的向量,实际上是一个n个城市的一个排列,
我们规定从第一个城市出发,整个这个搜索空间是一棵排列树,
在结点i1、i2、ik,在这个结点它表示已经
前k个城市都安排好走的顺序了, 已经得到了k步的路线,约束条件,
已经走过的城市标号放到B集合里面,
那么后面的城市必须是没有走过的城市,所以从城市集合里面
把这个走过的城市减掉,它只能从这个范围中来选择,
也就是说每个结点只能访问一次。
下边我们看一下它的代价函数。
这个界是当前已经得到的最短巡回路线的长度,这个是界。
然后我们我们看一下它的代价函数。假设顶点ci出发的最短边,
我们记作li,dj是选定
巡回路线中第j段的长度,那就是说前面有k段已经
选定了,把这些走过的
这些个边的长度都加起来,就是选定的这k条边
的长度都在前面这个和式里头,这项表示从第k个城市 到第k加1个城市的最小边长。
就是连接它的最短边的长度。这是 再后续的没有选过的那些城市,从它
出发的最短边的边长,因此后边这一项是
所有还没有出去,从这个城市 向外出发还没有出去过的那些城市,它所
连接它的最短边的边长,你无论怎么走,那条边 长度也不会比这个最短边的长度还要小,所以这个可以作为一个
下界,因此前面这一项代表的是已经走过的路径长度,后面
这一项是剩余长度的一个下界,把它作为一个代价函数的计算值。
下面我们看一下这个例子。这个例子呢,
这是刚才那个代价函数的计算公式,这一项代表 已经走过的边长,这个是后边估计的边长,
假定我们已经走到1、3、2,就是走这红颜色的1、3、2走到这儿了,
走到这个结点以后,它已经走过的变长是9 和13,所以前边这两项就是在这个和式里
面是9和13,那么剩下 现在已经走到2了,那就要加上从2出发的最短边,
那就是这条边,所以加一个2的长度,就是在这项里头,
那么还没有涉及到的城市,就是在这里头没有出现的是谁,是4号结点,从4号结点出发的-
最短边, 实际上是这条2的边,因此我们这个地方再加上一个2,就是这一项,
没有碰到的结点从它出发的最短边的长度,因此这个估计值是26。
也就是说当你沿着这条红路线走到这儿以后,下边无论你怎么走,
它的长度不会比26更小,这是后面的
预计的一个长度的下界,这就是它的公式的含义。
下边我们看一下在这样的一个
规定下它的搜索树是什么样子?
第一个城市肯定是1号城市,然后下边可以走2、3、4,
可以有三种选择是三条边,那么当你2号城市
选定了以后,下边可以选的是3号或者4号城市,所以是这样的
一棵排列树。那我们按照深度优先,假定来遍历这棵树, 加上刚才的代价函数的估计,那就是说
第一个走的是这样一条路径1、2、3、4, 也就是说按照这个图来讲是1
、2、3、4再回到1,这个 长度计算出来是29,那就是说得到了第一个巡回路线,
也就是第一个界是29。从它回到 父结点再回到它,然后再走下一个路径,
这个时候得到了第二个可行的旅行路线,这个值是23,这个界
就更新了,因为它比29更好,然后回到这儿,回到这儿,回到这儿,到这儿,到这儿,
到这儿是1、3、2。1、3、2按照公式计算它的代价函数值是26,
这个26比这个23还大,所以下面的搜索没有意义,回头。
回头以后回到这儿,回到这儿以后到这个结点,
得到了一个解还是23,跟它一样,正好是跟刚才的路线倒着走,
向相反方向走一圈,这个跟它的值是一样的,然后由它回到父结点,
再向这个方向搜索,所以它的搜索过程就是这样一个过程。你向右边走的过程中,
同样的要做代价函数的估计,而且你得到的这个巡回路线
的长度不会比这两个解更好,因此最终就是
最优解是这两个解,如果取其中的一个,按照算法来讲
取第一个,留下来就可以了。这个是它的搜索树。
那么对于这个
实例的运行,我们可以把它总结成下面的这些个结果。
第一个界,就是最左边那个界,<1,2,3,4>,长度是29,
第二个界呢,找到了更好的结果,是<1,2,4,3>,长度是23,
然后在结点<1,3,2>代价函数的值,刚才估计的是26,
因为比23大,所以就不再搜索,返回到它的父结点<1,3>,
沿着右子树向下,走到结点<1,3,4>
得到的代价函数值是20,这个计算的20,比这个23还要小,所以继续搜索,
继续搜索得到第二个可行解<1,3,4,2>,长度是23,正好是刚才那个23的
反方向的旅行构成的这个路线, 它的长度是一样的。然后用这个结点一直
向上回,一直回溯到结点1 然后再沿着<1,4>这个方向继续向下。
所以这个是刚才讲那个搜索过程,我们都把它记录到这里。
最后得到的最优解就是这个长度是23的这个解。
那么关于这个算法,我们可以分析一下它的复杂度。
搜索树有n减1阶乘片的叶片, 每个叶片对应着一条路径,每条路径上面有n个
结点,每个结点假定代价函数计算是常数时间的话, 每条路径的计算时间也是O(n)的时间,
所以总的这个算法的工作时间, 在最坏情况下达到n阶乘的时间和蛮力算法
是一样的,没有什么区别。
但是你如果要是真的实际运行起来, 通过裁剪,它的算法平均的时间要好得多。
把这个算法小结一下,货郎问题的分支限界 算法,它的约束条件是只能选没有走过的结点。
代价函数呢它是走过的这一段的长度加上后续长度的一个下界,
通过这个公式来估计它的代价函数, 时间复杂度是n阶乘的量级。
比蛮力算法没有好多少,这是它的情况。