旅行商问题

问题分析

带权邻接矩阵g[][]如下所示,空表示为无穷,即没有路径。

15305
15612
3063
5123

算法设计

可以使用优先队列分支限界法,加快搜索速度。
设置优先级:当前已走过的城市所有的路径长度cl。cl越小,优先级越高。
从根节点开始,以广度优先的方式进行搜索。根节点首先成为活结点,也是当前的扩展结点。一次性生成所有的孩子结点,判断孩子结点是否满足约束条件和限界条件,如果满足,将其加入到队列中,反之,舍弃。然后再从队列中取出一个元素,作为当前扩展结点,搜索过程队列为空时为止。

代码实现

(1)时间复杂度:O(n!)。空间复杂度:O(n*n!)。

算法优化拓展

  1. 算法开始时创建一个用于表示活结点优先队列。每个结点的费用下界zl=cl+rl值作为优先级。cl表示已经走过的路径长度,rl表示剩余路径长度的下界,rl用剩余每个结点的最小出边之和来计算。初始时先计算图中每个顶点i的最小出边,并用minout[i]数组记录,minsum记录所有结点的最小出边之和。如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法立即结束。
    • 限界条件:zl<bestl,zl<cl+rl。
  2. 优先级:zl指已经走过的路径长度+剩余路径长度的下界。zl越小,优先级越高。

算法优化代码实现

1.定义节点结构体

2.定义队列优先级

3.计算下界

4.Travelingbfsopt 为优化的优先队列式分支限界法

算法复杂度分析

时间复杂度最坏为O(nn!),空间复杂度为O(n2*(n+1)!)。

最优工程布线问题

问题描述

在3×3的方格阵列,灰色表示封锁,不能通过。将每个方格抽象为一个结点,方格和相邻4个方向(上下左右)中能通过的方格用一条线连接起来,不能通过的方格不连线。这样,可以把问题的解空间定义为一个图,如下图所示。

该问题是特殊的最短路径问题,特殊之处在于用布线走过的方格数代表布线的长度,布线时每一个方格,布线长度累加1.我们可以看出,从a到b有多种布线方案,最短的布线长度即从a到b的最短路径长度为4。
既然只能朝四个方向布线,也就是说如果从树型搜索的角度来看,我们可以把它看做为m叉树,那么问题的解空间就变成了一颗m叉树。

算法设计

(1)定义问题的解空间。可以把最优工程布线问题解的形式为n元组{x1,x2,...,xi,...,xn},分量xi表示最优布线方案经过的第i个方格,而方格也可以用(x,y)表示第x行第y列。因为方格不可重复布线,所以在确定xi的时候,前面走过的方格{x1,x2,...,xi-1}都不可以再走,xi的取值范围为S-{x1,x2,...,xi-1}
注意:和前面问题不同,因为不知道最优布线长度,所以n是未知的。

(2)解空间的组织结构:一颗m叉树,m=4,树的深度n未知。

(3)搜索解空间。搜索从起始结点a开始,到目标节点b结束。
- 约束条件:非障碍物或边界未曾布线。
- 限界条件:最先碰到的一定是距离最短的,因此无限界条件。
- 搜索过程:从a开始将其作为第一个扩展结点,沿a的右、下、左、上4个方向的相邻结点扩展。判断约束条件是否成立,若成立,则放入活结点中,并将这个方格标记为1。接着从活结点队列中取出队首结点作为下一个扩展结点,并沿当前扩展结点的右、下、左、上四个方向的相邻结点扩展,将满足约束条件的方格记为2,依此类推,一直继续搜索到目标方格或活结点为空为止,目标方格里的数据就是最优的布线长度。

构造最优解过程从目标节点开始,沿着右、下、左、上四个方向。判断如果某个方向方格里的数据比扩展结点方格的数据小1,则进入该方向方格,使其成为当前的扩展结点。以此类推,搜索过程一直持续到起始结点结束。

算法实现

复杂度分析

时间复杂度O(nm),构造最短布线需要O(L),空间复杂度O(n)。