posts - 10,  comments - 14,  trackbacks - 0

这是以前做的一道题,拿来复习下,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 阅读(3939) 评论(5)  编辑 收藏 引用

FeedBack:
# re: 双向广度优先搜索方法(在做完poj 1915后总结的)
2009-07-15 21:38 | future
请请问一下:

初始化起始点start.step=true; //这里step属性为真则表示为某一搜索步数中的最后一个点,例如对于poj1915中第2步有八个点,只有第八个点的step为true,其余为false

这句语句的作用?  回复  更多评论
  
# re: 双向广度优先搜索方法(在做完poj 1915后总结的)
2010-01-12 20:40 | huangzhifei
太精典了,
不过1楼的问题,我也想问!  回复  更多评论
  
# re: 双向广度优先搜索方法(在做完poj 1915后总结的)
2010-10-03 10:21 | 040374
不是用循环就可以控制了吗?干嘛还要最后一个step?  回复  更多评论
  
# re: 双向广度优先搜索方法(在做完poj 1915后总结的)[未登录]
2011-05-19 11:57 | VC爱好者
@future
这个的作用主要是可以搜索一层,如果不设置,就没有办法搜索一层。
就是向前搜索 搜索一层, 向后搜索搜索一层。
不仅可以搜索的一层,还可以控制搜索的深度。
楼主 你看怎么样  回复  更多评论
  
# re: 双向广度优先搜索方法(在做完poj 1915后总结的)
2011-12-02 21:54 | cqlf__
不知你有没考虑到 如果先遇到非最优解跳出的q情况
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(1)

随笔档案

文章分类

搜索

  •  

最新评论

阅读排行榜

评论排行榜