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

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

阅读更多
深度优先搜索DFS(Depth First Search)
(一)深度优先搜索遍历类似于树的先根遍历,是树的先根遍历的推广。

(二) 深度优先搜索就是在搜索树的每一层时始终先只扩展一个子节点,不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时,才从当前节点返回到上一级节点,沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。

  深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝,深度优先搜索如果误入无穷分枝(即深度无限),则不可能找到目标节点。所以,深度优先搜索策略是不完备的。
另外,应用此策略得到的解不一定是最佳解(最短路径)。


三、深搜编程框架
//深搜框架一:递归实现
	public  void dfs(int v) {
	  visited[v] = true;
	  System.out.print(v+"  ");
	  for (int i = 0; i < k; i++) {
	    //递归调用搜索没有被访问过的当前节点的下一个节点(邻接点)
	if (G[v][i] == 1 && !visited[i])//G[v][i]是图的邻接矩阵
		  dfs(i);//递归调用
	  }
	}




//深搜框架二:栈实现   
   public void dfs(){
     // 从顶点 v0开始搜索   
      visited[v0]= true;  //标记已访问过   
      display(v0); //显示顶点信息                
      theStack.push(v0); // 进栈   
  
      while( !theStack.isEmpty() ) {        
        // 查看栈顶元素,看其是否有未访问过的邻接点   
         int v = getAdjUnvisitedVertex( theStack.peek() );   
         if(v == -1)  // 没有邻接点  
            theStack.pop();             //出栈   
         else{       //有   
           visited[v]= true;  // 标记已访问v   
            display(v);              
            theStack.push(v);                 // 进栈   
         }   
     }
   }   
  
       
 


四、深度优先算法求数字的全排列(使用框架一)
import java.util.Scanner;
public class PaiLie{
 int n;
 boolean u[]; //u[i]标识数字i是否被使用过
 int ans[]; //ans排列的结果
 
 public PaiLie(int n){
   this.n=n;
   u=new  boolean[n+1];
   ans=new int[n+1];
 }
   
 private void print(){
    for (int i=0 ;i<n ;++i) 
      System.out.print(ans[i]+" ");
   System.out.println();
 }

  //递归实现深度优先搜索  
  void dfs(int d){
    if (d == n) {
        print();
        return;
    }    
    for (int i=1 ; i<=n; ++i)//当前顶点的所有可能邻接点
        if (!u[i]){//是邻接点
            ans[d] = i;
            u[i] = true;
            dfs(d+1);
            u[i] = false; //恢复现场
        }    
 }   
    public static void main(String args[]){
      Scanner in=new Scanner(System.in);
      int n=in.nextInt();
      PaiLie p=new PaiLie(n);
      p.dfs(0);
  }
}    


运行:
4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

五、农夫过河问题(使用框架二)
    一个农夫带着一只狼、一只羊和一棵草,身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船,船小到只能容下他和一件物品,另外只有农夫能撑船。另外,因为狼能吃羊,而羊爱吃草,所以农夫不能留下羊和草或者狼和羊单独在河的一边,自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢?

     要模拟农夫过河问题,首先需要选择一个对问题中每个角色的位置进行描述的方法。
一个很方便的办法是用四位二进制数顺序分别表示农夫、羊、草和狼的位置。例如用0表示农夫或者某东西在河的南岸,1表示在河的北岸。
因此整数5(其二进制表示为0101) 表示农夫和草在河的南岸,而羊和狼在北岸。


    图的遍历,设从南岸到北岸渡河,在南岸人、羊、草、狼的各个状态是(用二进制表示):0000,在北岸的时候各个状态是:1111。所以过河问题就是从0000起始状态到1111最终状态的过程。易得,总共有16种状态。然后把每一种状态看成图的一个结点,把可以连通的结点用有向边连起来,就构成的一个有向图。从0000这个结点遍历(深度优先或者广度优先)图,遍历到1111结点则找到解。 

public class manriver {
       private int[][] maxtri=new int[16][16];//邻接矩阵
       private boolean[] order=new boolean[16];// 状态是否被访问过的数组
	private stack stack=new stack();
	
	/**
	 * judge the adjacency matrix elements true or false(1 or 0)
	 *
	 */
	
  private boolean isConnected(int x,int y){//判断x与y是否是邻接点
	String X=getformatString(x);
	String Y=getformatString(y);
	
       if(X.charAt(0)==Y.charAt(0))//人必须渡河
		return false;
	else{
	  if(X.charAt(1)!=Y.charAt(1)&&X.charAt(2)!=Y.charAt(2)&&X.charAt(3)!=Y.charAt(3)){
		return false;//人 羊 草 狼不能一起过
	   }
	  else if(X.charAt(1)!=Y.charAt(1)&&X.charAt(2)!=Y.charAt(2)){
		return false;//人 羊 草 不能一起过
	  }
	  else if(X.charAt(1)!=Y.charAt(1)&&X.charAt(3)!=Y.charAt(3)){
	 	return false;//人 羊  狼不能一起过
	  }
	  else if(X.charAt(2)!=Y.charAt(2)&&X.charAt(3)!=Y.charAt(3)){
	 	return false;//人  草 狼不能一起过
	  }
 else if(((X.charAt(0)!=X.charAt(1))&&(X.charAt(1)!=Y.charAt(1)))||
((X.charAt(0)!=X.charAt(2))&&(X.charAt(2)!=Y.charAt(2)))||
((X.charAt(0)!=X.charAt(3))&&(X.charAt(3)!=Y.charAt(3)))){
			return false;//羊、草、 狼分别在人的对岸,羊、草、狼不可能直接回到人这一边
		}
		return true;
	}
	}
	/**
	 *  
	 *  produce the adjacency matrix
	 * 
	 */
	public void makeMaxtri(){
		for(int i=0;i< 16;i++){
			for(int j=0;j< 16;j++){
				if(isConnected(i, j))
				{	maxtri[i][j]=1;
				}
				else maxtri[i][j]=0;
			}
		}
	}
	/**
	 * 
	 * 得到状态的字符串表示
	 * 0000  四位分别代表人 羊 草 狼
	 * 
	 * */
	public String getformatString(int x){
		
		String X=Integer.toBinaryString(x);//十进制转为二进制字符串
		if(X.length()< 4&&X.length()>=3){
			X="0"+X;
		}
		else if(X.length()< 3&&X.length()>=2){
			X="00"+X;
		}
		else if(X.length()< 2&&X.length()>=1){
			X="000"+X;
		}
		return X;
	}
	
	/** 
	 *  
	 *  dfs arithmetic
	 *  dfs算法
	 *
	 */
  public void dfs(){
	stack.push(0);
	order[0]=true;
	while(!stack.isEmpty()){	
		if(stack.peek()==15){//状态为1111,全部过河
			break;
		}
		int v=getUnvisitedVetex(stack.peek());
		if(v==-1){
			try{stack.pop();
			}catch(Exception e){
				e.printStackTrace();
			}
		}
		else{
		
			stack.push(v);
			order[v]=true;
		}
	}				
   }
	/**
	 * 
	 *得到与输入节点相连的一个结点 
	 *  
	 */
   public int getUnvisitedVetex(int x){
	for(int j=0;j< 16;j++){
	
         if(maxtri[x][j]==1&&!order[j]){
				
	   String X=getformatString(j);
	   //合法性判断
	   if((X.charAt(0)!=X.charAt(1)&&X.charAt(1)==X.charAt(3))||//羊狼在一起,如0101
                 (X.charAt(0)!=X.charAt(1)&&X.charAt(1)==X.charAt(2))){//羊草在一起,如1000
		continue;	
	    }
	    else {
		return j;}
	    }
	 }
	return -1;
    }
	/**
	 * 
	 *  make order 
	 * 
	 */
public void printOrder() throws Exception{
  for(int i=0;i< stack.length()-1;i++){
	int x=stack.peekByIndex(i);
	int y=stack.peekByIndex(i+1);
	String X=getformatString(x);
	String Y=getformatString(y);
	String type="";
	if(X.charAt(0)=='0'){
		type="过河";
	}
	if(X.charAt(0)=='1'){
		type="回来";
	}
	if(X.charAt(1)!=Y.charAt(1)){
		System.out.println("人带羊"+type);
	}
	else if(X.charAt(2)!=Y.charAt(2)){
		System.out.println("人带草"+type);
	}
	else if(X.charAt(3)!=Y.charAt(3)){
		System.out.println("人带狼"+type);
	}
	else{
		System.out.println("人自己"+type);
	}
  }
}
	public static void main(String[] args){
		manriver manriver=new manriver();
		manriver.makeMaxtri();
		manriver.dfs();
		try{
			manriver.printOrder();
		}catch(Exception e){
			e.printStackTrace();
		}
	}
}
/**
 * 
 * 堆栈简单实现类 
 * 
 */
class stack{
	private int[] num;
	private int value;
	public stack(){
		num=new int[20];
		value=-1;
	}
	public int peek(){
	
		return num[value];
	}
	public int pop() throws Exception{
		if(value>=0){
			return num[value--];
		}
		else throw new Exception("无元素!");
		
	}
	public void push(int xx){
		if(value==-1){
			value=0;
			num[value]=xx;
		}
		else{
			num[++value]=xx;
		}	
	}
	public int getSize(){
		return value;
	}
	public boolean isEmpty(){
		return(value< 0);
	}
	public int length(){
		return value+1;
	}
	public int peekByIndex(int i)throws Exception{
		if(i< value+1&&i>=0){
		return num[i];
		}
	else throw new Exception("未找到合适元素!");
	}
  }

  
运行:
人带羊过河
人自己回来
人带狼过河
人带羊回来
人带草过河
人自己回来
人带羊过河

源码:
  • 大小: 28.5 KB
分享到:
评论

相关推荐

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

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

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

    深度优先搜索(DFS, Depth-First Search)是一种用于遍历或搜索树或图的算法,它从根节点开始,沿着某一条路径一直深入到叶子节点,然后再回溯寻找其他路径。在本例中,我们有两个Java文件:MazeDsf.java 和 Queen....

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

    这篇博文“深度优先搜索学习五例之五(JAVA)”可能介绍了DFS在解决实际问题中的应用,尽管描述中没有给出具体细节,但我们可以从一般的角度来探讨DFS以及其在Java中的实现。 DFS的基本思想是从根节点开始,沿着某...

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

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

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

    2. Main1.java:这个文件可能是对BFS的另一种实现,或者是辅助Main.java进行特定任务的类,比如提供额外的测试用例,或者实现了与BFS相关的其他算法(如深度优先搜索DFS)进行对比。 综上所述,这个压缩包文件的...

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

    在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...

    java实现的求迷宫最短路径算法

    这个类可能实现了A*算法、Dijkstra算法或者深度优先搜索(DFS)等常见的寻找最短路径的算法。这些算法的核心目标是找到从起点到终点的最短路径,同时尽量避免无效的探索。 以A*算法为例,它结合了Dijkstra算法的...

    回溯法入门学习之一

    回溯法是一种强大的算法...在这个“回溯法入门学习之一”的主题中,我们了解了回溯法的基本步骤,并通过一个Java程序进行了简单实现。通过持续学习和实践,我们可以熟练掌握这种算法,并将其应用于更复杂的实际问题中。

    Java经典算法(包你们划算)

    3. **图论算法**:如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法等。 4. **动态规划**:解决许多复杂问题的有效方法,如背包问题、最长公共子序列、...

    经典C语言程序设计200例

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

    学习常用算法之(3)回溯法

    总结来说,回溯法是一种系统化的方法,它通过深度优先搜索和回溯机制在庞大的解空间中寻找满足特定约束的解。这种方法在面对多解问题时特别有效,因为它可以在找到第一个解后立即停止搜索,也可以找到所有解。同时,...

    自己实现的ioc容器

    对于依赖查找,可以采用深度优先或广度优先的搜索策略。 对于属性注入,可以使用反射API来设置bean的属性值。例如,如果在配置文件中定义了`MyService`的`dao`属性,那么在实例化`MyService`时,需要找到对应的`...

    migong.rar_migong

    迷宫问题是一个经典的计算机科学问题,通常用于研究和实现搜索算法,如深度优先搜索(DFS)、广度优先搜索(BFS)、A*搜索等。开发者可能已经实现了基本的迷宫走动逻辑,但希望通过社区的经验和智慧来提升算法的效率...

    数据结构与算法java中文

    - **具体步骤**:采用深度优先搜索(DFS)策略,使用栈来记录已探索过的路径。 #### 五、递归 ##### 5.1 递归与堆栈 **5.1.1 递归的概念** - **递归定义**:一个方法直接或间接地调用自身的过程。 - **递归的...

    data structure tree ppt

    以UNIX目录结构为例,每一个目录都可以被看作是树中的一个节点,包含若干子目录(即子节点)和文件。通过递归遍历方法,可以逐层列出目录及其子目录的内容。这里,根目录可以被称作“Mark”,而它的子目录比如...

    找出哪几个数值的和接近目标值

    例如,我们可以定义一个递归函数,对数组进行深度优先搜索,每次选择一个元素加入当前子集,直到子集的和超过目标值,然后回溯并尝试下一个元素。另一种方法是使用两个指针,一个从数组开头开始,另一个从结尾开始,...

    图论资料,有源代码,还有图论小软件

    以深度优先搜索(DFS)算法为例,它能用于遍历或搜索图的结构,主要思想是尽可能深地搜索图的分支。广度优先搜索(BFS)算法则按层次遍历图的结构,适用于最短路径问题。Dijkstra算法用于求解单个源点到其他所有顶点...

    LeetCode 101 - A LeetCode Grinding Guide (C Version).pdf

    在搜索算法章节,作者探讨了深度优先搜索(DFS)、回溯法、广度优先搜索(BFS)等基本搜索技巧,以及如何在实际问题中应用这些搜索策略。 书中的一个重要特点是,作者强调了刷题不是提高计算机科学能力的全部,而是...

Global site tag (gtag.js) - Google Analytics