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

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

阅读更多
例:输出由数字0,1,2..n组成的全部可重复全排列
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class Permutation{

  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    System.out.println("由数字0--"+n+"可生成"+BFS(n+1)+"种可重复全排列");
  }

  public static   long BFS(int k) {
   String v="";   
   long s=0;
  //队列用来保存被访问节点的分支节点(邻接点)   
  Queue< String> que = new LinkedList< String>();   
  que.offer(v);//起点入队列   
  while (!que.isEmpty()) {   
    v = que.poll();//弹出当前顶点   
     //将当前节点的分支节(邻接)点加入到队列中   
      for (int i = 0; i < k; i++) {   
        String u=v+i;
        if(u.length()==k){//如果是一个K位的排列,输出
          System.out.println(u);
          ++s;
        }
        else
          que.add(u);   
      }   
   }  
   return s; 
  }
 }  

运行:
C:\java>java Permutation
2
000
001
002
010
011
012
020
021
022
100
101
102
110
111
112
120
121
122
200
201
202
210
211
212
220
221
222
由数字0--2可生成27种可重复全排列

例:八数码难题(poj 1077)
   在3X3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格(用0表示)。空格周围的棋子可以移到空格中。
要求解的问题是:找到一种最少的移动方法,实现从初始状态到目标状态的转变。
例如程序中输入:234150768(代表要从此状态转为后一状态123456780),则应该输出:ullddrurdllurdruldr(上左左下下右上右下左左上右下右上左下右)

如下所示:
2 3 4
1 5 0
7 6 8

1 2 3
4 5 6
7 8 0


[分析]
状态表示:用二维数组arr[][]来表示状态。arr[i][j]表示第i行、第j列上放的棋子数字。空格用0表示。

规则:原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察,也可看做空格向四周移动。这样处理更便于广度优先搜索编程。
如果空格位置在arr[i][j],则有四条规则:
(1)空格向上移动: change(i,j,i-1,j)
(2)空格向下移动: change(i,j,i+1,j)
(3)空格向左移动: change(i,j,i,j-1)
(4)空格向右移动: change(i,j,i,j+1);

搜索策略(广度优先搜索):
(1)把初始状态作为当前状态;
(2)从当前状态出发,运用四条移动规则,产生新的状态;
(3)判断新的状态是否达到目的状态,如果是,转(5);
(4)把新的状态记录下来(入队列),从队列中取出下一个中间状态作为当前状态,返回(2);
(5)输出从初始状态到目标状态的路径,结束。

import java.util.*;
public class Main
{
  private int[][] arr;//3*3棋盘
  private boolean[] bb=new boolean[10000000];
  private Queue< my> qu=new LinkedList< my>();

  public Main(){
   arr=new int[5][5];
   for(int i=0;i<5;i++)
     Arrays.fill(arr[i],0);
   }

  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();//从命令行接受初始状态
    Main m=new Main();
    m.bfs(n);
   }

    private void bfs(int t){
      qu.add(new my("",t));//初始状态入队列
      while(!qu.isEmpty()){
        my h=qu.poll();//弹出当前状态
	int u=h.u;
	String s=h.s;
	if(u==123456780){//如果当前状态等于目标状态
            System.out.println(s);//输出移动方案
	    return;
        }
	if(bb[u%9999991]) continue;//如果当前状态已访问过
	bb[u%9999991]=true;//标记当前状态为已访问
	int i=-1,j=-1,p=u;
        for(int u1=3;u1>0;u1--){//从整数表示状态转为棋盘表示状态,并找出“0”的位置
           for(int u2=3;u2>0;u2--){
             arr[u1][u2]=p%10;
             if(arr[u1][u2]==0){
                i=u1;
                j=u2;
             }
             p/=10;
         }
        }
        change(i,j,i-1,j);//"0"向上移动
        int y=getNum();
        qu.add(new my(s+"u",y));//入队,记录状态,"u"代表向上
        change(i-1,j,i,j);//复位
			
        change(i,j,i+1,j);//“0”向下移动,"d"表示向下
        y=getNum();
        qu.add(new my(s+"d",y));
        change(i+1,j,i,j);//复位
			
        change(i,j,i,j+1);//“0”向右移动
        y=getNum();
        qu.add(new my(s+"r",y));//"r"表示向右
        change(i,j+1,i,j);//复位
			
        change(i,j,i,j-1);//“0”向左移动,"l"表示向左
        y=getNum();
        qu.add(new my(s+"l",y));
        change(i,j-1,i,j);//复位
      }
       System.out.println("unsolvable");
     }

  //棋盘表示的状态转为用整数表示
  private int getNum(){
    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;
  }

   //处于棋盘某一位置(x,y,)的“0”,与位置(x2,yx)交换
  private  void change(int x1,int y1,int x2,int y2){
     arr[x1][y1]=arr[x2][y2];
     arr[x2][y2]=0;
  }

  private void print(){ 
    
    for(int i=1;i<4;i++){
     for(int j=1;j<4;j++)
       System.out.print(arr[i][j]+"  ");
     System.out.println();
    }
  }  

 
 
}

  class my{
    String s="";
    int u;
    public my(String t,int a){
      u=a;
      s=t;
    }
}

运行:
C:\java>java Main
234150768
ullddrurdllurdruldr

下载源码:
分享到:
评论

相关推荐

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

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

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

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

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

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

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

    在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**: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*搜索,通过结合路径代价和预计到达目标的...

    C++语言经典、实用、趣味编程百例精解\C++经典程序200例、c语言经典算法100例

    这些例子可能包含经典的排序算法(如插入排序、选择排序)、查找算法(如二分查找)、图算法(如深度优先搜索、广度优先搜索)以及其他实用的算法如动态规划和回溯法。通过实践这些算法,学习者将能提高问题解决能力...

    《人工智能导论-》- 03 搜索.ppt

    总结来说,搜索是人工智能问题求解的关键技术之一,包括但不限于盲目搜索(如宽度优先搜索)和启发式搜索。这些方法在游戏策略、知识表示、规划等领域有广泛应用。理解并掌握搜索策略对于深入学习人工智能至关重要。

    C语言经典算法100例

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

    经典C语言程序设计200例

    例如,你可以在这里找到基础的冒泡排序、快速排序,二分查找,图的遍历算法如深度优先搜索和广度优先搜索,以及更复杂的动态规划问题解决方案。这些算法的C语言实现不仅帮助学习者理解算法原理,还能让他们熟悉如何...

Global site tag (gtag.js) - Google Analytics