24-算法设计

6.4.2　算法设计

（1）定义问题的解空间

可以把最优工程布线问题解的形式为n元组：{x₁，x₂，…，x_i，…，x_n}，分量x_i表示最优布线方案经过的第i个方格，而方格也可以用（x，y）表示第x行第y列。因为方格不可重复布线，因此在确定x_i时，前面走过的方格{x₁，x₂，…，x_i−1}不可以再走，x_i的取值为S−{x₁，x₂，…，x_i−1}，S为可布线的方格集合。

特别注意：和前面的问题不同，因为不知道最优布线的长度，因此n是未知的。

（2）解空间的组织结构

问题的解空间是一棵m叉树，m=4。树的深度n是未知的。如图6-60所示。

（3）搜索解空间

搜索从起始结点a开始，到目标结点b结束。

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

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