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

广度优先搜索学习五例之四
例：输出由数字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

下载源码：

查看更多 下一篇