用STL实现DFS/BFS算法
——基于策略的类设计
作者：alai04 来源：csdn 发表时间：2006-06-05
浏览次数：
字号：大 中 小
前三个CheckDup都与旧版本一样，而最后一个HashCheckDup则有了小小的变化。新的接口是，要求状态类提供operator==以及hash()成员函数，后者是用于计算hash值的。HashCheckDup中定义了一个嵌套函数对象类HashFcn，它通过调用状态类所提供的hash()成员函数来计算hash值并返回给hash_set容器。其它部分都与旧版本一样，可见改变是很小的。现在，我们的四个查重策略都具有相同的模板参数格式了。
我们再回过头来看看BFS和DFS分别所对应的SearchInserter，它们的代码如下：
// BFS算法对应的新结点插入策略
template <class Cont>
class BFSInserter
{
public:
BFSInserter(Cont& c) : c_(c) {}
typedef typename Cont::iterator iterator;
typedef typename Cont::value_type value_type;
void operator()(iterator it, const value_type& v) {
c_.push_back(v); //新结点插入到列表的末端，即未搜索的结点后
}
private:
Cont& c_;
};
// DFS算法对应的新结点插入策略
template <class Cont>
class DFSInserter
{
public:
DFSInserter(Cont& c) : c_(c) {}
typedef typename Cont::iterator iterator;
typedef typename Cont::value_type value_type;
void operator()(iterator it, const value_type& v) {
c_.insert(++it, v); //新结点插入到未搜索的结点前
}
private:
Cont& c_;
};
BFSInserter和DFSInserter都是函数对象类模板，它们以保存状态空间树的容器为模板参数，提供一个operator()操作符，该操作符函数接受一个指向容器内的迭代器和一个要插入到容器里的值，它负责执行插入的动作。BFS和DFS分别对应于不同的插入策略。
可选的SearchInserter和CheckDup策略都已准备好了，在进入到StateSpaceTreeSearch的实现部分之前，我们再讨论一个小问题，就是关于SearchInserter和CheckDup这两个模板参数的顺序和缺省值的问题。Andrei Alexandrescu在《Modern C++ Design》中说到，我们应该把最可能被使用者显式指定的策略放在前面，同时把使用者最可能使用的某种策略作为该类策略的缺省值。
那么，第一个问题：SearchInserter和CheckDup分别应该使用什么缺省值？我觉得，很多实际问题会要求给出最少步数的解法，这时就应该使用BFS而不是DFS，所以我选择了BFSInserter作为SearchInserter的缺省值。至于CheckDup，我就选择了对性能影响最少的NoCheckDup作为缺省值。
第二个问题：对于SearchInserter和CheckDup，哪一个会更多地被显式指定？我觉得好象差不多，所以就比较随意地安排了现在这个次序。
下面准备进入StateSpaceTreeSearch。我们再来重温一次，通常解决一个具体的搜索问题，除了前面已经提到的State、SearchInserter和CheckDup以外，我们还需要什么？对了，就是一个初始状态（它应该是一个State对象）和一个关于找到解答后的回调函数（也可以看成是某种策略）。初始状态无疑应该作为函数调用的参数被传入，但是回调函数呢？它应不应该也成为StateSpaceTreeSearch的一类策略呢？
我的看法是，State、SearchInserter和CheckDup三部分已经组成了一个具体问题的解法，使用者应该用这三个组成部分来实例化出一种具体问题（如推箱子）的解法，如下：
StateSpaceTreeSearch<SokoState, BFSInserter, OrderCheckDup> sokoSearch;
而当你需要对这种问题的某个特定题目（如一道具体的推箱子题目）进行解答时，你应该执行这个解法sokoSearch，并把题目传入，等待sokoSearch返回答案，如：
sokoSearch(initState);
那么，找到解答后所执行的回调函数应该属于问题解法的范畴还是属于特定题目解答的范畴呢？我认为，把它归入到后者会更为灵活些。例如，对于同一种问题（如推箱子），我们可以用一个sokoSearch对象来解答多条特定题目，并且每条题目可以选择不同的回调函数。如：
sokoSearch(initState1, printAnswerAndContinue);
sokoSearch(initState2, printAnswerAndStop);
所以，我把StateSpaceTreeSearch设计为一个函数对象类模板，即它提供一个operator()，该操作符函数接受两个参数：一个是问题的初始状态，另一个是找到解答后的回调函数，函数的返回值为整数，表示搜索结束时找到的解答数量。StateSpaceTreeSearch的代码如下：
// 状态空间树搜索模板
// State：问题状态类，提供nextStep()和isTarget()成员函数
// SearchInserter：可选择BFS或DFS
// CheckDup：状态查重算法，可选择NoCheckDup,HashCheckDup,OrderCheckDup等
template < class State, template <class> class SearchInserter = BFSInserter,
template <class> class CheckDup = NoCheckDup >
class StateSpaceTreeSearch
{
public:
typedef list<State> Cont;
typedef typename Cont::iterator iterator;
template <class Func>
int operator()(const State& initState, Func afterFindSolution) const
// initState : 初始化状态，类State应提供成员函数nextStep()和isTarget()，
// nextStep()用vector<State>返回下一步可能的所有状态，
// isTarget()用于判断当前状态是否符合要求的答案；
// afterFindSolution : 仿函式，在找到一个有效答案后调用之，它接受一个
// const State&，并返回一个bool值，true表示停止搜索，
// false表示继续搜索
// return : 找到的答案数量
{
CheckDup<State> checkDup;
Cont states;
SearchInserter<Cont> inserter(states);
states.push_back(initState);
iterator head = states.begin(); //指向下个搜索的结点
vector<State> nextStates;
int n = 0; //记录找到的解答数量
bool stop = false;
while (!stop && head != states.end())
{
State s = *head; //搜索一个结点
nextStates.clear();
s.nextStep(nextStates); //从搜索点生成下一层结点
for (typename vector<State>::iterator i = nextStates.begin();
i != nextStates.end(); ++i)
{
if (i->isTarget())
{ // 找到一个目标状态
++n;
if (stop = afterFindSolution(*i)) //处理结果并决定是否停止
{
break;
}
} else { // 不是目标状态，判断是否放入搜索队列中
if (!checkDup(*i)) // 只将不重复的状态放入搜索队列
{
inserter(head, *i);
}
}
}
++head; //指针移到下一个元素
}
return n;
}
};
我想，代码中的注释已经解释了许多，我只在这里简单的补充说明一下。StateSpaceTreeSearch使用list<State>作为保存状态空间树的容器，不过这个容器并不是StateSpaceTreeSearch的数据成员，而是operator()操作符函数里的局部变量。也就是说，该容器在每次执行搜索时生成，搜索结束后销毁，不会在两次搜索间保留。这样，实例化出一个StateSpaceTreeSearch类就可以多次执行搜索。具体的搜索由operator()操作符函数执行，指定策略的CheckDup和SearchInserter都在其中进行实例化和使用。operator()中的代码按照本文开始时对DFS和BFS的分析进行编写。
以推箱子游戏为例，我们将这样使用新版的DFS/BFS算法：
StateSpaceTreeSearch<SokoState, DFSInserter, OrderCheckDup> sokoSearch;
int n = sokoSearch(initState, printAnswer);
作为对比，我把旧版的代码也贴出来：
OrderCheckDup<SokoState> checkDup;
int n = BreadthFirstSearch(initState, printAnswer, checkDup);
如果你是使用者，你会觉得哪一种用法更方便呢？
=>中国源码网：全球著名开源项目大本营
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
