用STL实现DFS/BFS算法
——检查重复状态
前几天，有网友留言说我使用“先深”、“先宽”的说法是狗屁二流子词汇，正确的说法应该是“深度优先”，“广度优先”。态度和用词虽然有点让人不好接受，但提的意见终归是有点道理的。请实话，我已经不记得最早是从哪里学来的“先深”、“先宽”，但可以肯定一点，本人是发明不出这样的词汇的，只是认为这两个词还不错，比较简单明了，所以就用上了。后来，我上GOOGLE查了一下，结果发现的确用四个字的比用两个字多得多，看来多数人还是喜欢长一点的词，或者说长一点的那两个词更通用一些。于是我就想是不是该“改正”一下自己的“错误”，换个大家更容易接受的词用用。
接下来，很高兴地看到有网友挺“先深”、“先宽”，于是我又想，如果我这就换了，岂不是有点对不起那些和我一样喜欢用“先深”、“先宽”的网友？思前想后，干脆用E文好了，所以就有了这个新的标题。
转入正题，前面我们说过，到目前为止我们的DFS/BFS算法还只能搜索无重复状态的状态空间树，而象下象棋、推箱子等问题，都会出现问题状态在几步之后可能会回到以前出现过的状态的情况。当重复状态出现时，我们必须能够识别出来，并且不应把它放入搜索树中。最简单、直接的做法就是，当问题状态类的nextStep()成员函数返回一组下一步可能状态时，我们对这些状态逐一进行检查，如果发现有重复的，就不把重复状态放入搜索树（即不入栈或入队列）。至于如何检查重复状态，我们还是采用函数模板最常见的方法，让使用者自己提供检查的方法，在我们的DFS/BFS算法中用一个泛型的模板参数来指定它。这样一来，我们的算法会变为这样（以BFS为例）：
template <class T1, class T2, class T3 >
int BreadthFirstSearch(const T1& initState, const T2& afterFindSolution,
T3& checkDup)
// 前两个参数与旧版本相同
// checkDup : 仿函式，对于每一个下一步可能的状态调用之，它接受一个const T1&，
// 并返回一个Boolean值，true表示状态重复，false表示状态不重复
// return : 找到的答案数量
{
int n = 0;
queue<T1> states;
states.push(initState);
vector<T1> nextStates;
bool stop = false;
while (!stop && !states.empty())
{
T1 s = states.front();
states.pop();
nextStates.clear();
s.nextStep(nextStates);
for (typename vector<T1>::iterator i = nextStates.begin();
i != nextStates.end(); ++i)
{
if (i->isTarget())
{ // 找到一个目标状态
++n;
if (afterFindSolution(*i)) // 处理结果并决定是否停止搜索
{
stop = true;
break;
}
} else { // 不是目标状态，判断是否放入搜索队列中
if (!checkDup(*i)) // 只将不重复的状态放入搜索队列
{
states.push(*i);
}
}
}
}
return n;
}
与旧版本的相比，我们可以看到，它只是增加了一个模板参数T3、一个调用参数checkDup和一行代码if (!checkDup(*i))。所有增加的东西都很清楚明白，就不用多说了。
现在，使用BFS的用户要多提供一个函数对象（或仿函式）类型，该函数对象负责保存传入的状态对象（类型为T1）并进行检查，看看传入的状态对象是否与以前传入的某个对象重复。为了减轻BFS使用者的负担，我认为应该提供几个简单的检查方法供使用者选用，只有我们提供的方法都不适用时，使用者才需要自行提供。
第一个最简单的检查方法就是不检查，即与我们的旧版本BFS一样。不检查的方法很简单，根据这个BFS算法的要求，我们直接返回false就行了。如下：
template <class T>
struct NoCheckDup : std::unary_function<T, bool>
{
bool operator() (const T&) const
{
return false;
}
};
在这里，我们可以再多做一些事情，让我们的新版本BFS与旧版本兼容，即提供一个与旧版本相同的接口，这样可以让用户更方便使用。办法也很简单，定义一个重载的BreadthSearchFirst，它接受两个参数（和旧版本一样），然后使用一个NoCheckDup<T1>对象作为第三参数调用新版本算法就行了。
template <class T1, class T2 >
int BreadthFirstSearch(const T1& initState, const T2& afterFindSolution)
// 两参数版本
// initState : 初始化状态，类T1应提供成员函数nextStep()和isTarget()，
// nextStep()用vector<T1>返回下一步可能的所有状态，
// isTarget()用于判断当前状态是否符合要求的答案；
// afterFindSolution : 仿函式，在找到一个有效答案后调用之，它接受一个const T1&，
// 并返回一个Boolean值，true表示停止搜索，false表示继续找
// return : 找到的答案数量
{
NoCheckDup<T1> noCheckDup;
return BreadthFirstSearch(initState, afterFindSolution, noCheckDup);
}
有了这个重载版本，我们前面的数独问题程序和N皇后问题程序都可以无须修改，重编译一下就可以了。
接下来，我们还可以再实现几个简单的重复状态检查方法，当然了，它们都会使用STL的容器和算法来实现。用STL来进行查重，可以有很多方法，我想到了最常用的三种：线性复杂度的find算法、对数复杂度的set容器，和速度更快但也是最复杂的hash容器。其中最后一种hash容器还不是STL的标准实现，不过多数STL实现都提供了，我们不妨试着用一下。下面，我们一个一个来看看如何实现。
首先是线性查找方法，我们可以用一个vector容器来保存所有传入的状态，然后用find算法来进行线性查找，代码如下；
// 仿函式，用vector容器检查状态结点是否重复，线性复杂度
// 要求状态类提供operator==
template <class T>
class SequenceCheckDup : std::unary_function<T, bool>
{
typedef vector<T> Cont;
Cont states_;
public:
bool operator() (const T& s)
{
typename Cont::iterator i =
find(states_.begin(), states_.end(), s);
if (i != states_.end()) // 状态已存在，重复
{
return true;
}
states_.push_back(s); // 状态未重复，记录该状态
return false;
}
};
为什么选用vector呢？我们的需求很简单：可以把状态对象依次放入容器、可以执行find算法就行了。当然，用deque和list都是可以的，而且时间复杂都是相同级别的（因为插入元素的次序并不重要，我们可以简单地选择后端插入）。这样，我就选择了占用空间最少的vector了。
为了使find算法可以执行，对状态类T提出了一个要求，它必须提供operator==。这一点由状态类的提供者（即BFS的使用者）负责。当BFS的使用者给出一个支持operator==的问题状态类MyState后，他就可以这样使用新版本的BFS：
MyState initState(n);
SequenceCheckDup<MyState> checkDup;
int total = BreadthFirstSearch(initState, continueSearch, checkDup);
还有一点要注意的是，与NoCheckDup不同，SequenceCheckDup是有状态的，使用同一个对象两次调用SequenceCheckDup的结果是不同的，对SequenceCheckDup的调用有可能会改变函数对象的状态。所以，它的operator()不可以是const的。使用这种有状态的函数对象要格外小心，这是题外话，就不多说了。
你可以想象，线性查找的速度是不能令人满意的。当搜索树增大到一定程度后，线性查找的速度会越来越慢。BFS在每次生成一个新的状态结点时，都会调用一次checkDup，所以如果搜索树的结点数为n，则BFS的时间复杂度为O(n*n)。我们知道STL中的set容器正是为提高容器内元素搜索的速度而设计的，如果使用set来替代vector，可以期望BFS的时间复杂度降为O(n*logn)。这样，我们有了第二个查重方法OrderCheckDup，如下：
// 仿函式，用set容器检查状态结点是否重复
// 要求状态类提供operator<
template <class T>
class OrderCheckDup : std::unary_function<T, bool>
{
typedef set<T> Cont;
Cont states_;
public:
bool operator() (const T& s)
{
typename Cont::iterator i = states_.find(s);
if (i != states_.end()) // 状态已存在，重复
{
return true;
}
states_.insert(i, s); // 状态未重复，记录该状态
return false;
}
};
与SequenceCheckDup相比，OrderCheckDup把存放已有状态对象的容器从vector换成了set，把原来的通用find算法换成了set::find()，把原来的vector::push_back换成了set::insert()，仅此而已。
与SequenceCheckDup不同的是，由于OrderCheckDup要把状态对象存入set，所以它要求状态类T提供operator<，而不是operator==。所以，如果你想使用OrderCheckDup，你就要给你的问题状态类MyState提供operator<；至于BFS的使用方法，则与前相同：
MyState initState(n);
OrderCheckDup<MyState> checkDup;
int total = BreadthFirstSearch(initState, continueSearch, checkDup);
通常来说，OrderCheckDup提供的O(n*logn)时间复杂度已经很不错了，对于绝大多数问题来说都是合适的。但有的时候，使用者可能要追求更高的查重速度，这时可以考虑使用hash容器。这就是我们的第三个查重方法HashCheckDup，如下：
// 仿函式，用hash_set容器检查状态结点是否重复
// 要求状态类提供operator==以及hash函数
template <class T, class HashFcn = hash<T> >
class HashCheckDup : std::unary_function<T, bool>
{
typedef hash_set<T, HashFcn> Cont;
Cont states_;
public:
typedef typename Cont::hasher hasher;
HashCheckDup(const hasher& hf) : states_(100, hf) {}
bool operator() (const T& s)
{
if (states_.find(s) != states_.end()) // 状态已存在，重复
{
return true;
}
states_.insert(s); // 状态未重复，记录该状态
return false;
}
};
它使用了尚未正式进入C++标准的hash_set，不过有很多STL实现都提供这个容器，具体的说明可以去看相关文档，这里只说一点，hash_set容器要求存入的对象类型T要提供operator==和一个hash函数。所以我们可以看到，HashCheckDup除了把set换成了hash_set，它还多了一个模板参数和一个构造函数（即hash函数）。Hash函数实现的好坏直接关系到hash_set容器进行查找的速度，没有一种通用的hash算法，所以必须由类型MyState的提供者来提供适用于MyState的hash算法，它的格式应该是这样的：
struct HashMyState
{
size_t operator() (const MyState& s) const
{
…
}
};
当你为MyState准备好了operator==以及hash算法后，可以这样来调用BFS：
MyState initState(n);
// 以下变量定义必须通过添加括号来消除二义性，否则编译器会把它看作函数声明
HashCheckDup<MyState, HashMyState> checkDup((HashMyState()));
int total = BreadthFirstSearch(initState, continueSearch, checkDup);
这段代码中有一个很有趣的现象，即在checkDup的定义中，用于调用构造函数的实参多了一重括号。一眼看上去，这重括号好象是多余的，但其实不是。如果没有这重括号，这段代码是通不过编译的，编译器会抱怨说在下一行代码中的BreadthFirstSearch()模板函数实例化有错，不能把MyState转换为HashMyState (*)()。开始的时候，我也被弄糊涂了，只依稀记得在哪见过这个错误。一番查找后，在《Exception C++ Style》的第29条找到了答案。原来在没有多一重括号时，编译器把这行代码：
HashCheckDup<MyState, HashMyState> checkDup(HashMyState());
看作是一个函数声明而不是变量定义！书中给出了最简单的解决方法：通过添加一对括号来消除二义性。这就是这对看似多余的括号之所以存在的原因。
现在我们有了总共四个查找重复状态的方法：不查找、线性查找、二分查找(set容器提供的其实就是一种有序容器上的二分查找)和hash查找。使用者可以根据需要选用它们中的一个。不同的方法对于问题状态类有不同的要求，总结如下：
|
查找方法
|
对问题状态类的要求
|
|
不查找
|
仅适用于不会出现重复状态的情况，对问题状态类无特别要求
|
|
线性查找
|
要求问题状态类提供operator==，查找速度慢
|
|
二分查找
|
要求问题状态类提供operator<，查找速度较快
|
|
Hash查找
|
要求问题状态类提供operator==以及hash算法，如果hash算法合适的话，查找速度最快
|
如果这四种方法都不合你意，你可以自行提供查找算法并用它来调用BFS好了。
说了这么多，我想也应该用一个实际的问题例子来检验一下我们的新版BFS了，我挑选的例子是几年前做过一道题目：推箱子；与数独问题和N皇后问题相比，推箱子游戏要复杂不少，所以下一篇文章可能会多花一点时间。