理处言语然自

启发式搜索与推箱子

考虑一个普通的图搜索问题：给出初始状态(节点 s)和目标状态(节点 t，可以不止一个)以及状态的产生规则，求从 s 到 t 的一条路经。搜索过程可描述如下：

1. 待展开的节点集合(OPEN 表)为 {s}，已展开的节点集合(CLOSED 表)为 {}，节点 s 的层深为 g(s) = 0。
2. 每次从 OPEN 表中取出一个节点 n，根据规则扩展产生一组节点 m_i，然后把 n 放入 CLOSED 表中。节点 m_i 可能属于下列三种情况之一：
   • 新的节点，则把 m_i 的源标记为 n，层深 g(m_i) = g(n) + 1，并放入 OPEN 表中。
   • 已在 OPEN 表中存在的节点，并且层深 g(m_i) > g(n) + 1，说明从 s 到 m_i 并且经由 n 的路径要比先前搜索得到的路径要短。因此，把 m_i 的源改记为 n，层深 g(m_i) = g(n) + 1，仍放入 OPEN 表中。
   • 已在 CLOSED 表中存在的节点，并且层深 g(m_i) > g(n) + 1。同理，把 m_i 的源改记为 n，层深 g(m_i) = g(n) + 1，并从 CLOSED 表中取出重新放入 OPEN 表中，留待以后重新搜索计算 m_i 的子节点的层深。
3. 不断重复上一步操作，直到满足下列条件之一：
   • n == t，搜索成功。
   • OPEN 表为空，搜索失败。

在以上过程中，如何从 OPEN 表中选取待扩展的节点是关键。如果每次均选取层深 g(n) 最小的节点，以上过程就是宽度优先搜索；如果每次均选取层深 g(n) 最大的节点，以上过程就是深度优先搜索。启发式搜索算法 A 的思想是，给节点定义一个评价函数

• f(n) = g(n) + h(n) (1)

其中，g(n) 是节点的层深，即从 s 到 n 目前搜索已知的最短路径长度，h(n) 是节点 n 到目标节点 t 的最短路径长度的估计值，称为启发函数。拥有最小 f(n) 值的节点有希望成为从 s 到 t 的最短路径上的一个节点，因而被取出并扩展。

启发函数 h(n) 具有下列一些性质(证明略，我也不完全懂)：

• 如果 h(n) 处在从 n 到 t 的最短路径长度的真实值 h^*(n) 的下界，即恒有 h(n) <= h^*(n)，则算法 A 找到的一定是从 s 到 t 的最短路径。此时算法 A 称为算法 A^*。
• 可以想象，h(n) 越接近真实值 h^*(n)，它所包含的启发信息就越多，搜索所需扩展的节点数就越少。
• 如果对所有节点 n_i 和 n_j (其中 n_j 是 n_i 的子节点)都有 h(n_i) – h(n_j) <= 1，则称启发函数 h(n) 满足单调限制条件。此时，算法 A^* 在选取节点 n 进行扩展时，必有 g(n) == g^*(n)，在搜索过程中不会出现把 m_i 从 CLOSED 表中取出重新放入 OPEN 表的情况。

算法实现

• solve.cpp 启发式搜索通用程序

程序中定义的四个函数：

int orderDown(NodeInfo *infos, int *opens, const int &open_used, int root);
堆的向下(从根到叶)调整，内部使用

int orderUp(NodeInfo *infos, int *opens, const int &open_used, int leaf);
堆的向上(从叶到根)调整，内部使用

template <class Node> int key(Node *nodes, const int &hash_size, const Node &n);
在散列数组中查找节点

template <class Node> int solve(Node *nodes, int hash_size, Node s);
搜索函数，程序的入口

基于可重用性的考虑，搜索函数 solve 被定义为模板函数，它操作的对象是一个表示节点的模板类。节点类要求具有被搜索函数使用的一些基本接口，这些接口描述了节点的基本行为和属性，而节点的具体意义(比如表示推箱子的某个状态)则隐藏在类的实现细节中。节点类的基本接口如下：

int from;
节点的源，返回目标路径时使用

Node();
空节点的构造函数

int possibleMoves() const;
可能的扩展节点数

int move(int sw);
按第 sw 种扩展方式改变节点

int h() const;
启发函数

int isTarget() const;
判断节点是否目标节点

int isNull() const;
判断节点是否空节点

int hash() const;
散列函数

friend int operator == (const Node &left, const Node &right);
判断两个节点是否同一

void output() const;
输出

为了提高速度，节点的存储和查找使用开地址散列，使用简单的线性探测解决冲突。程序中的 Node nodes[] 和 NodeInfo infos[] 是并列的两个散列数组，分别存储所有已展开的节点和节点的附加信息(f 值和在 OPEN 表中的位置)。key 根据节点的散列函数 hash() 在散列数组中查找或分配节点。

OPEN 表实际上是一个优先队列，因而采用堆的方式实现。程序中的 int opens[] 是以数组(完全二叉树)存储的堆，数组元素表示节点在散列数组中的位置，最小 f 值的节点可以在堆的根即 opens[0] 处中给出。orderDown 和 orderUp 是调整堆的需要。

推箱子

• box.cpp 推箱子程序，Linux 下以 g++ box.cpp -o box -O3 编译

应用通用程序求解推箱子问题，关键是节点类的实现。

• 状态的划分

  推箱子的状态由人和箱子的位置决定。考虑到人可以在墙壁和箱子围成的连通区域内任意行走而不会对局面产生实质性的影响，规定人必须位于他所处的连通区域的左上角。考虑到箱子的全同性，箱子的坐标应从小到大排序。这些都在构造函数 Box() 或者节点扩展函数 move(sw) 中完成。这时，判断两个状态是否相等只需分别比较每个箱子和人的坐标是否相等即可。

• 节点的扩展

  每个箱子可以推向四个方向，因此总的可能的扩展节点数是箱子数的四倍。考虑到人的可到达范围(way[])的限制，某些箱子的某些方向(push_directions[])是不可到达的。另外，地图中还存在一些“死位置”(dead_positions[])，比如墙角、两个箱子并列在墙边等等。还有，箱子的背后可能是墙壁或者另一个箱子。这些不可能的情况都可以在节点扩展函数 move(sw) 中予以拒绝。

• 启发函数

  可以计算所有箱子离最近的目标的距离之和作为启发函数 h() 的返回值。不难看出，此定义的启发函数满足算法 A^* 的下界条件，因而找到的目标路径一定是最优解。

• 散列函数

  可以将所有箱子的坐标移位相加再平方取中，得到散列函数 hash() 的返回值。

以上是我的推箱子程序的主要思路，如果你感兴趣，请进一步阅读我的程序。(可能不太好读。:-)

我的程序在 128M ~ 512M 内存的条件下(需要根据情况修改程序中 HASH_SIZE 和 HEAP_SIZE 的设置)基本上可以解六个箱子之内的关，八到十个箱子的关或者特别复杂的六个箱子的关解起来会比较费劲，特别复杂的八个箱子以上的关基本上就解不了了。启发式搜索虽然可以在很大程度上缩小搜索空间，但是无法根本解决指数爆炸的问题。目前我能想到一些改进措施是：

• 如果不苛求最优解，可以适当增大上文提到的启发函数值。事实上，所有箱子离最近的目标的距离之和与实际到达目标所需的步数之间有很大的差距，因而扩展生成了许多无关的节点。增大启发函数值，例如人为的给它乘以二，以牺牲最优解为代价更快地到达目标。
• 用另一种方式计算每个箱子到达目标所需的步数。考虑一个箱子紧挨着一个目标的情况，因为地图和人的位置关系，箱子很可能根本无法一步推到目标上，这时简单的以箱子和目标的距离计算就不太合适了。一种可能的办法是，在正式搜索之前先搜索得出一个箱子从不同的位置出发推到目标所需的步数。不过，这点改进对搜索的性能能有多大提高还是一个未知数。
• 删除搜索树上的“死”分枝。这点属于对启发式搜索通用程序的改进，与推箱子无关。但是测试表明，在推箱子的搜索过程中，“死”分枝的比例一般只占总节点数的一半左右。因此，这点改进带来的效果估计也不会很明显。:-(

来源：http://elephant.net.cn/articles/box.php