`
128kj
  • 浏览: 604245 次
  • 来自: ...
社区版块
存档分类
最新评论

广度优先搜索学习五例之五

阅读更多
   如果已经知道搜索的开始状态和结束状态,要找一个满足某种条件的一条路径(一般是最短路径),为了避免无谓的“组合爆炸”产生,就可以采取双向广度搜索算法,也就是从开始状态和结束状态同时开始搜索,一个向前搜,一个向后找。 直至在两个扩展方向上出现同一个子结点,搜索结束,这就是双向搜索过程。出现的这个同一子结点,我们称为相交点,如果确实存在一条从初始结点到目标结点的最佳路径,那么按双向搜索进行搜索必然会在某层出现“相交”,即有相交点,初始结点一相交点一目标结点所形成的一条路径即是所求路径。

   这样做的好处是什么?
      我们不妨假设每次搜索的分支因子是r,如果最短的路径长为L的话(也就是搜了L层),那么,用一般的BFS算法(不考虑去掉重复状态),总的搜索状态数是r^L(^表示乘方运算);而如果采取双向BFS算法,那么,从前往后搜,我们只需要搜索L/2层,从后往前搜,我们也只要搜L/2层,因此,搜索状态数是2*(r^(L/2)),比普通BFS就快了很多了。

    双向BFS算法的实质还是BFS,只不过两边同时开始BFS而已。还是可以利用队列来实现:可以设置两个队列,一个用于向前的BFS,另一个用于向后的BFS,利用这两个队列,同时从前、后开始层次遍历搜索树。


结点扩展顺序
    双向扩展结点,在两个方向的扩展顺序上,可以轮流交替进行,但由于大部分的解答树并不是棵完全树,在扩展完一层后,下一层则选择结点个数较少的那个方向先扩展,可以克服两个方向结点生成速度不平衡的状态,明显提高搜索效率。

双向广度优先算法编程的基本框架如下:

数据结构:
Queue q1, q2; //两个队列分别用于两个方向的扩展(注意在一般的广度优先算法中,只需要一个队列)

算法流程:
void DBFS(){
1. 将起始节点放入队列q1,将目的节点放入队列q2
2. 当 两个队列都未空时,作如下循环
   1) 如果队列q1里的未处理节点比q2中的少,则扩展队列q1,并判断是否出现相交点;
   2) 否则扩展队列q2,并判断是否出现相交点;
3. 如果队列q1未空,循环扩展q1直到为空
4. 如果队列q2未空,循环扩展q2直到为空
}

例:再解POJ 1077
题意:8数码问题,给出一个含数字1~8和字母x的3*3矩阵,如:

          2  3  4
          1  5  X
          7  6  8

现在要你移动x的位置(上下左右),使得这个矩阵为:

           1  2  3
          4  5  6
          7  8  x
求出移动步数最少的移动方案。

例如程序中输入:2 3 4 1 5 0 7 6 8(代表要从此状态转为后一状态123456780),则应该输出:ullddrurdllurdruldr(上左左下下右上右下左左上右下右上左下右)


思路:这里用双向bfs。状态可采用全排列的hash函数http://128kj.iteye.com/blog/1699795

import java.util.*;
public class Main
{
  private int[][] arr1,arr2;//保存中间过程的数组
  private String [] bb1=new String[362882];//9!=362880,最大状态9!,标记访问过的结点,同时记录操作动作
  private String [] bb2=new String[362882];
  private Queue< my> qu1=new LinkedList< my>();//用于向前向后的两个队列
  private Queue< my> qu2=new LinkedList< my>();
  static final int fac[] = {1,2,6,24,120,720,5040,40320}; //用于计算全排列的Hash值

  public Main(int[][] arr1,int[][] arr2){
        this.arr1=arr1;
        this.arr2=arr2;
  }

  public static void main(String[] args){
     Scanner in=new Scanner(System.in);
     int[][] arr1=new int[5][5];//起点
     int[][] arr2={{0,0,0,0,0},//目标
                   {0,1,2,3,0},
                   {0,4,5,6,0},
                   {0,7,8,0,0},
                   {0,0,0,0,0}}; 
     String s;
     for(int i=1;i< 4;i++){
      for(int j=1;j< 4;j++){
        s=in.next();
	if(s.equals("x"))arr1[i][j]=0;
	else arr1[i][j]=Integer.parseInt(s);
      }
     }

      Main m=new Main(arr1,arr2);         
      int from=m.getNum(arr1);//数组表示的状态转为用整数表示   

      int to=m.getNum(arr2);//数组表示的状态转为用整数表示   

       m.Dbfs(from,to);	
   }

        
  private  void Dbfs(int from,int to){       
     int ha=0;
     qu1.offer(new my("",from)); //起点入队列1
     qu2.offer(new my("",to));  //目标入队列2
     while(!qu1.isEmpty()&&!qu2.isEmpty()){
       if(!qu1.isEmpty()){//从起点向目标广度优先搜索搜索
	my h=qu1.poll();
	int u=h.u;
	String s=h.s;
        ha=hash(u,9);
	if(bb2[ha]!=null){//双向搜索出现相交点,输出结果
           System.out.println(s+bb2[ha]);
           return;
        }             
        if(bb1[ha]!=null) continue;//此状态已访问过
	bb1[ha]=s;//记录操作动作,标记为已访问
	int i=-1,j=-1,p=u;
        //从整数表示的状态转为数据组表示状态,并找出“0”的位置,应该写成一个方法.
	for(int u1=3;u1>0;u1--){
         for(int u2=3;u2>0;u2--){
           arr1[u1][u2]=p%10;
           if(arr1[u1][u2]==0){
              i=u1;
              j=u2;
           }
           p/=10;
         }
        }
 
        //从四个方向访问当前状态的邻接点
        change(arr1,i,j,i-1,j);//向上一步
	int y=getNum(arr1);
	qu1.add(new my(s+"u",y));//邻接点入队
        change(arr1,i-1,j,i,j);//复位
			
	change(arr1,i,j,i+1,j);
	y=getNum(arr1);
	qu1.add(new my(s+"d",y));
        change(arr1,i+1,j,i,j);
			
        change(arr1,i,j,i,j+1);
        y=getNum(arr1);
        qu1.add(new my(s+"r",y));
        change(arr1,i,j+1,i,j);
			
        change(arr1,i,j,i,j-1);
        y=getNum(arr1);
	qu1.add(new my(s+"l",y));
        change(arr1,i,j-1,i,j);
       }
                 
                  
       if(!qu2.isEmpty()){////从目标向起点广度优先搜索搜索
         my h=qu2.poll();
         int u=h.u;
         String s=h.s;
         ha=hash(u,9);
         if(bb1[ha]!=null){//双向搜索出现相交点,输出结果
            System.out.println(bb1[ha]+s);
            return;
         }
                        
	 if(bb2[ha]!=null) continue;
         bb2[ha]=s;
         int i=-1,j=-1,p=u;
         for(int u1=3;u1>0;u1--){
            for(int u2=3;u2>0;u2--){
              arr2[u1][u2]=p%10;
              if(arr2[u1][u2]==0){
                i=u1;
                j=u2;
              }
              p/=10;
             }
          }
          change(arr2,i,j,i,j+1);
          int y=getNum(arr2);
          qu2.add(new my("l"+s,y));
          change(arr2,i,j+1,i,j);
			
          change(arr2,i,j,i,j-1);
          y=getNum(arr2);
          qu2.add(new my("r"+s,y));
          change(arr2,i,j-1,i,j);

          change(arr2,i,j,i-1,j);
          y=getNum(arr2);
          qu2.add(new my("d"+s,y));
          change(arr2,i-1,j,i,j);
			
          change(arr2,i,j,i+1,j);
          y=getNum(arr2);
          qu2.add(new my("u"+s,y));
          change(arr2,i+1,j,i,j);	
        } 
      }
      System.out.println("unsolvable");
    }

   private int hash(int num,int k){//全排列的哈西函数   
    int  n[]=new int[k];   
    for(int i = k-1; i >=0; i--){   
        n[i] = num % 10;   
        num /= 10;   
    }   
      
    int key = 0;   
    int c;   
    for(int i = 1; i <k; i++){   
         c=0;   
     for(int j = 0; j < i; j++)   
         if(n[j] > n[i]) c++;   
     key += c * fac[i-1];   
    }   
    return key;   
}   

 private int getNum(int[][] arr){
    int t=0;
    for(int i=1;i< 4;i++)
     for(int j=1;j< 4;j++){
       t*=10;
       t+=arr[i][j];
     }
     return t;
   }

  private void change(int[][] arr,int x1,int y1,int x2,int y2){
      arr[x1][y1]=arr[x2][y2];
      arr[x2][y2]=0;
  }
 }
class my{
   String s="";
   int u;
   public my(String s,int u){
     this.s=s;
     this.u=u;
   }
}

运行:
D:\java>java Main
2 3 4 1 5 0 7 6 8
ullddrurdllurdruldr
分享到:
评论

相关推荐

    广度优先搜索学习五例之四

    【标题】:“广度优先搜索学习五例之四” 在计算机科学中,广度优先搜索(Breadth-First Search,简称BFS)是一种用于遍历或搜索树或图的算法。它按照从根节点开始,逐层进行探索的方式进行。在本案例中,我们可能...

    广度优先搜索学习五例之二(JAVA)

    【标题】:“广度优先搜索学习五例之二(JAVA)” 在计算机科学中,图算法是解决问题的关键工具之一,而广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或搜索树或图的算法。本篇文章将重点讲解如何在...

    广度优先搜索学习五例之一

    **广度优先搜索(Breadth-First Search, BFS)**是一种在图或树中进行搜索的算法,常用于寻找最短路径或者遍历结构。它遵循“先探索节点的所有邻居,再探索邻居的邻居”的策略,从起点开始,逐层向外扩展。BFS的关键...

    广度优先搜索学习五例之三

    【标题】"广度优先搜索学习五例之三"涉及的是图论算法中的一个重要概念——广度优先搜索(Breadth-First Search, BFS)。在计算机科学中,BFS是一种用于遍历或搜索树或图的算法,尤其适用于查找最短路径问题。此标题...

    深度优先搜索学习五例之四(JAVA)

    在这个“深度优先搜索学习五例之四”的主题中,我们将重点关注使用Java实现DFS解决具体问题的情况。这篇博客文章可能通过一个具体的实例,如迷宫求解,来演示如何利用DFS进行递归或栈操作。 首先,我们来看"MazeDsf...

    深度优先搜索学习五例之一(JAVA)

    在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...

    图的广度优先搜索的应用

    通过深入学习和实践这些案例,我们可以掌握如何运用广度优先搜索解决实际问题,并且在遇到类似问题时能够快速找到合适的算法和方法。此外,对于同一问题的深入探讨可以帮助我们探索更优的解决方案,比如通过剪枝技术...

    python深度,广度,三种启发式搜索解决八数码问题

    我们将依次讨论深度优先搜索(DFS)、宽度优先搜索(BFS)以及启发式搜索策略,如A*算法,并结合图形化界面来直观展示搜索过程。 一、八数码问题简介 八数码问题是一个在3x3的网格上移动数字,目标是通过最少的步数...

    广度优先搜索例程:迷宫最短路径-易语言

    广度优先搜索(BFS)是一种用于遍历或搜索树或图的算法,其基本思想是从根节点开始,沿着树的宽度优先遍历,直到找到目标节点或者遍历完所有节点。在本例中,我们将关注如何运用广度优先搜索(BFS)来寻找迷宫中的...

    广度优先算法算例,可直接运行

    **广度优先搜索(BFS)算法是一种在图或树中搜索节点的遍历方法,其基本思想是从起点开始,先访问所有距离起点最近的节点,然后再依次访问更远的节点。这种算法常用于查找最短路径、解决迷宫问题等。在本程序包中,...

    浅谈网络爬虫中广度优先算法和代码实现.pdf

    在爬虫技术中,两种常见的遍历策略是深度优先搜索(DFS, Depth-First Search)和广度优先搜索(BFS, Breadth-First Search)。本篇将重点探讨广度优先算法及其在网络爬虫中的应用。 首先,广度优先算法的核心思想是...

    八数码C代码

    该程序可能包含了实现八数码问题的各种算法,如深度优先搜索(DFS)、广度优先搜索(BFS)或A*搜索等。 描述中的"可以直接运行的程序,是八数码的C的源代码,直接运行即可"表明这个压缩包里的1.cpp文件是一个可执行的C...

    人工智能原理学习教案.pptx

    盲目搜索如宽度优先搜索(BFS)和深度优先搜索(DFS),在未知环境中探索所有可能的解决方案路径,虽然简单但效率较低。启发式搜索则依据某种评估函数来指导搜索方向,如A*搜索,通过结合路径代价和预计到达目标的...

    信息学奥赛一本第五版通教学课

    搜索算法如二分查找、广度优先搜索(BFS)和深度优先搜索(DFS),在解决图论问题和树形结构问题时非常关键。动态规划是一种强大的问题解决方法,通过构建状态转移方程,可以解决很多复杂的问题,如斐波那契数列、...

    经典C语言程序设计200例

    而图的遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS),则为处理复杂数据结构提供了有力的工具。更高级的算法,如动态规划,则能够指导学习者如何将复杂问题分解为更易于管理和求解的子问题。 第二部分的...

    C语言经典算法100例

    此外,C语言也常用于实现图的遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS)。这些算法在解决网络路由、社交网络分析等问题时有着广泛的应用。还有动态规划、贪心算法、回溯法等高级算法,它们在解决复杂...

    高效算法128例配套代码

    1. **算法基础**:书中涵盖的基础算法包括排序(快速排序、归并排序、堆排序等)、搜索(深度优先搜索、广度优先搜索)以及动态规划。这些是任何程序员都需要掌握的核心技能,对于解决实际问题至关重要。 2. **数据...

Global site tag (gtag.js) - Google Analytics