| 用STL实现DFS/BFS算法
——推箱子游戏(2)
前面，我们给出了SokoState的输入输出操作符。接下来，我们来看看isTarget()成员函数。它很简单，我们只要检查一下是否每个箱子都已经被移动到了目的地就行了，即检查一下每个格子的isDest()状态与isBox()状态是否相同（同时为真或同时为假）。代码如下：
bool SokoState::isTarget() const
{
for (int i = 1; i < rows_-1; i++)
{
for (int j = 1; j < cols_-1; j++)
{
Point p(i, j);
if (isDest(p) != isBox(p))
return false;
}
}
return true;
}
由于二维图的最外围一圈肯定是Wall，所以无需进行检查，这样可以让我们稍快一点。
在进入nextStep()成员函数之前，让我们先看看SokoStep类及其相关函数。为了表示一步移动，我们需要两个东西：位置和方向。所以，我这样定义SokoStep类：
class SokoState
{
…
struct SokoStep //用于记录每一步箱子的移动
{
int x_;
int y_;
char d_; // direction: R,L,U,D
SokoStep(int x, int y , char d) : x_(x), y_(y), d_(d) {}
friend ostream& operator<< (ostream& os, const SokoStep& s)
{
os << "[" << s.x_ << ", " << s.y_ << ", " << s.d_ << "]";
return os;
}
};
…
}
它有一个构造函数和一个输出操作符，因为我们在找到答案后，将要输出从初始问题状态与解答状态所经过的每一步移动，这个输出操作符可以帮不少忙。
为了输出答案，我们还需要给 SokoState类添加一个printAnswer()成员函数，因为SokoState类的数据成员都是私有的。它的任务是把数据成员steps_输出来，steps_是一个vector容器，我们可以使用copy算法和ostream_iterator适配器，如下：
void SokoState::printAnswer(ostream& os) const
{
copy(steps_.begin(), steps_.end(), ostream_iterator<SokoStep>(os, " "));
}
下面是我们最重要的部分：nextStep ()成员函数。我的想法是，对于当前的状态，扫描所有的箱子，判断哪个箱子可以向哪个方向移动，把所有可能的移动找出来，返回给DFS/BFS。有了我们前面给出的stateEq()成员函数的处理，判断一次移动是否可能就非常简单的了：只要箱子的一侧为空且另一侧有人就可以向空的方向移动，否则箱子就不能移动（要么一侧有障碍物，要么另一侧没有人）。照这个方法，我们写出moveBox()成员函数供nextStep()调用，如下：
bool SokoState::moveBox(SokoState& r, Point box, Point soko, Point nBox,
char d) const
{
if (!isSoko(soko) || !isSpace(nBox))
return false;
r = *this;
for (int i = 0; i < r.rows_; i++) //清除soko标志
{
for (int j = 0; j < r.cols_; j++)
{
r.map_[i][j] &= ~FlagSoko;
}
}
r.map_[box.x_][box.y_] &= ~FlagBox; //移动箱子
r.map_[box.x_][box.y_] |= FlagSoko;
r.map_[nBox.x_][nBox.y_] |= FlagBox;
r.stateEq();
r.steps_.push_back(SokoStep(box.x_, box.y_, d));
return true;
}
moveBox()有五个参数，第一个参数是一个SokoState引用，用于返回移动后（如果可以移动的话）的状态；第二、三、四个参数分别是箱子、人和移动后箱子的位置；最后一个是移动的方向，用一个char表示（’U’,’D’,’L’,’R’分别表示上下左右）；函数返回一个bool值表示是否可以移动。函数一开始就判断是否可以移动，判断的方法我们前面说过了，就是看看箱子的一侧是否有人且另一侧是否有空位。如果可以移动，就把当前状态复制到返回用的目标状态变量中，然后对目标状态进行修改。修改分为四步：首先把目标状态中的所有soko标志清除掉，这是因为箱子移动后，原来用stateEq()计算出来的多个soko标志中的某些会无效，必须重新用stateEq()进行计算；然后在箱子移动的格子中修改标志，包括清除原箱子所在格的box标志，置为soko标志，以及把箱子新移动到的格子置为box标志；第三步是调用stateEq()重新计算整个二维图的soko标志；最后是把这次移动的步骤添加到steps_成员中。这样就可以返回true了。
nextStep()成员函数从二维图中找出所有箱子的位置，对每个箱子逐个使用moveBox()来尝试向四个方向进行移动，如果有某个移动是可行的，就把移动后的新状态添加到vector容器中返回给DFS/BFS。代码如下：
void SokoState::nextStep(vector<SokoState>& vs) const
{
SokoState newState;
for (int i = 1; i < rows_-1; i++)
{
for (int j = 1; j < cols_-1; j++)
{
Point p(i, j);
if (!isBox(p))
continue;
if (moveBox(newState, p, p.down(), p.up(), 'U'))
vs.push_back(newState);
if (moveBox(newState, p, p.up(), p.down(), 'D'))
vs.push_back(newState);
if (moveBox(newState, p, p.right(), p.left(), 'L'))
vs.push_back(newState);
if (moveBox(newState, p, p.left(), p.right(), 'R'))
vs.push_back(newState);
}
}
}
至此，我们的SokoState好象快完成了，不过还漏了一点点，就是operator<了。正如在前面一篇文章里提到的，推箱子问题有可能在某些步骤后产生重复的状态，因此DFS/BFS 算法必须考虑对重复状态的检查。DFS/BFS已经准备了三种可选的检查策略：线性查找、二分查找和hash查找。考虑到推箱子问题的问题状态空间树可能比较大，结点数量可能会很多，线性查找的效率可能会比较低，所以不建议采用线性查找。另一方面，如果使用hash查找，就要为SokoState类准备一个hash函数，也比较麻烦。所以我选择了效率比较高而且不太麻烦的方法——二分查找，它是利用STL的set容器来实现的，要求SokoState类提供一个operator<操作符。用最简单的方法实现如下：
bool SokoState::operator< (const SokoState& other) const
{
if (rows_ < other.rows_)
return true;
if (rows_ > other.rows_)
return false;
if (cols_ < other.cols_)
return true;
if (cols_ > other.cols_)
return false;
for (int i = 0; i < rows_; i++)
{
for (int j = 0; j < cols_; j++)
{
if (map_[i][j] < other.map_[i][j])
return true;
if (map_[i][j] > other.map_[i][j])
return false;
}
}
return false;
}
其实就是逐个比较SokoState中的各个数据成员来分出大小，当然steps_成员是用于记录移动步骤的，它与问题状态无关，不用于比较。事实上，如果你对steps_也进行比较的话，那么使用不同先后步骤到达同一状态的两个SokoState对象就会被看作不等价，这样就会无法消除搜索树中的重复状态结点，从而导致DFS/BFS算法陷入无限循环。
现在，DFS/BFS所需要的整个 SokoState类已经准备好了，不过DFS/BFS还要求使用者提供一个afterFindSolution函数对象来给出搜索到答案时的执行动作和策略。在这个推箱子问题中，我想只需做两件事：输出得到答案的步骤，以及结束搜索。所以这个函数很简单，我们不准备用函数对象了，用一个普通函数就OK 了：
bool printAnswer(const SokoState& s)
{
s.printAnswer(cout);
cout << endl;
return true;
}
你应该记得，返回一个true表示让DFS/BFS停止搜索。
好了，最后就是我们的main()函数的，我想不用多解释，你应该一看就明白了。如果有不明白的地方，你可能需要回过头去看一下前面相关的几篇文章。
int main(int argc, char *argv[])
{
SokoState initState;
cin >> initState;
cout << initState;
OrderCheckDup<SokoState> checkDup;
int n = BreadthFirstSearch(initState, printAnswer, checkDup);
if (n == 0)
{
cout << "No answer." << endl;
}
return 0;
}
还是以我们开始的游戏为例，这个关卡属于中等难度，不过我试了半天也没推出来，所以写了这个程序来帮我找答案。
500)this.width=500'>
程序在我的机器上跑了两秒多，找到了答案：
[3, 6, U] [2, 6, L] [2, 5, L] [3, 2, D] [4, 2, D] [5, 2, D] [4, 5, R] [4, 6, U] [3, 6, U] [6, 2, R] [2, 4, L] [3, 4, D] [4, 4, D] [2, 6, L] [2, 5, L] [2, 4, D] [6, 3, L] [6, 2, R] [2, 3, R] [6, 3, L] [6, 2, U] [5, 2, U] [4, 2, U] [5, 4, D] [2, 4, R] [3, 4, D] [4, 4, D] [2, 5, L] [2, 4, D] [6, 4, L] [6, 3, L] [6, 2, R] [6, 3, R] [6, 4, R] [6, 5, R] [6, 6, U] [5, 6, U] [4, 6, U] [5, 4, D] [6, 4, L] [6, 3, L] [6, 2, R] [6, 3, R] [6, 4, R] [6, 5, R] [6, 6, U]
程序虽然跑过了，不过还有很多可以改进和优化的地方。其中一点是状态存储所占的空间，你可能也注意到了，在这个DFS/BFS算法中，搜索树中的每个结点代表一个状态，搜索树可能采用stack或 queue容器。同时，如果需要采用重复状态检查，则同一个状态又会保存在一个查重所用的容器中（可能是vector、set或hash_set）。即一个问题状态会被保存两份，虽然搜索树中保存的那一份会在搜索过后被释放（即移出stack或queue容器），但是该状态对象还是被构造和析构了一次。
其实我们可以只保存一份问题状态，而不是两份同样的问题状态。这时我们需要的容器是一个功能更强大的容器，它应该按两种或以上的次序来排序和访问，这正是boost库中的Multi-index Containers。通过使用它，我们可以只保存一份问题状态，而同时实现DFS/BFS的搜索次序和set/hash_set的查重，而且它还有一个额外的好处。因为我们在搜索过程中保留了所有的问题状态，这样就无需在每一个问题状态中保存从初始状态到当前状态的变化过程（即SokoState类中的 steps_成员所作的工作），而只需要保存从上一个状态到当前状态的变化过程（它只需要一个step对象而不是由N个step对象组成的vector容器）以及上一个状态在搜索树中的位置即可。当找到解答时，我们可以从解答状态开始回溯来得到从初始状态到解答状态的所有变化过程。这样同样也节省了存储的空间和复制vector<step>容器的时间。 |
