最优工程布线问题

问题描述

在3×3的方格阵列，灰色表示封锁，不能通过。将每个方格抽象为一个结点，方格和相邻4个方向（上下左右）中能通过的方格用一条线连接起来，不能通过的方格不连线。这样，可以把问题的解空间定义为一个图，如下图所示。 该问题是特殊的最短路径问题，特殊之处在于用布线走过的方格数代表布线的长度，布线时每一个方格，布线长度累加1.我们可以看出，从a到b有多种布线方案，最短的布线长度即从a到b的最短路径长度为4。 既然只能朝四个方向布线，也就是说如果从树型搜索的角度来看，我们可以把它看做为m叉树，那么问题的解空间就变成了一颗m叉树。