这是以前做的一道题，拿来复习下，poj1915，解决的是国际象棋中给定一个起始点，一个目标点，要求计算马从起始点跳至目标点最小步数的问题。看似很简单，主要是来训练下双向广度优先搜索的code。因为这里要实现最小步数，所以用BFS比较好，一旦搜索到解即为最小的步数。为了加快搜索速度使用双向广度优先搜索。
广度优先搜索的方法很简单，用一个队列来保存待搜索的点，每次搜索将下一步要搜索的点依次加入队列中，伪代码如下：
初始化visited数组，将所有点的值设为false；//visited数组用来保存所有点的访问情况
visited[start]=true;//start为起始点
queue<type> search;//用来保存待搜索点的队列
search.push(start)；
while(!search.empty())
{
v=search.front();
search.pop(); //弹出一个点处理，用v表示
for(每一个v的相邻点)
if(!visited[v]){
visited[v]=true;
search.push(v);
}
}
以上代码部分只是所有点的遍历，为的是理解思想，并没有加入达到终止条件返回步数(这很关键)，我会在下面双向广度优先搜索加上。
双向广度优先搜索则是从出发点和目标点分别向后向前搜索，当相遇时则终止。在code时关键问题有：怎么记录当前搜索步数；怎么判断和什么时候判断达到终止条件；搜索时向前向后的顺序。对于搜索函数伪代码(不考虑点的存储结构)如下：
if(start==finish)
return 0;
初始化visited数组里每个值为0; //这里visited值为1则为向后搜索过的值，为2则为向前搜索过的值
初始化起始点start.step=true; //这里step属性为真则表示为某一搜索步数中的最后一个点,例如对于poj1915中第2步有八个点，只有第八个点的step为true,其余为false
初始化目标点finish.step=true;
visited[start]=true;
visited[finish]=true;
queue<type> frontSearch; //记录从前向后搜索的队列
queue<type> backSearch; //记录从后向前搜索的队列
fstep=0; //记录从前向后搜索的步数
bstep=0; //记录从后向前搜索的步数
frontSearch.push(start);
backSearch.push(finish);
while(!frontSearch.empty() || !backSearch.empty())
{
if(!frontSearch.empty())
{
do{
current=frontSearch.front();//从队列中弹出当前搜索的点
frontSearch.pop();
for(每一个current的相邻点v){
if(visited[v]==2)
return fstep+bstep+1;//如果遇到了从后向前搜索搜过的点则终止，并且返回总步数
if(!visited[v]){
visited[v]=1;
frontSearch.push(v);
}
}
}while(!current.step) //同一步的点已经全部搜完，结束循环
fstep++; //增加从前向后搜索的步数
current=frontSearch.front();
frontSearch.pop();
current.step=true;
frontSearch.push(current); //将当前步数最后一个点的step属性设为true；
}
if(!backSearch.empty())
{
do{
current=backSearch.front();//从队列中弹出当前搜索的点
backSearch.pop();
for(每一个current的相邻点v){
if(visited[v]==1)
return fstep+bstep+1;//如果遇到了从前向后搜索搜过的点则终止，并且返回总步数
if(!visited[v]){
visited[v]=2;
backSearch.push(v);
}
}
}while(!current.step) //同一步的点已经全部搜完，结束循环
bstep++; //增加从后向前搜索的步数
current=backSearch.front();
backSearch.pop();
current.step=true;
backSearch.push(current); //将当前步数最后一个点的step属性设为true；
}
}
总之，要一步一步的搜是关键。至于怎么控制有很多方法。
posted on 2009-05-29 22:56
tortoisewu 阅读(3937)
评论(5) 编辑 收藏 引用