广度优先搜索学习5例之四
广度优先搜索学习五例之四
例:输出由数字0,1,2..n组成的全部可重复全排列
运行:
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)输出从初始状态到目标状态的路径,结束。
运行:
C:\java>java Main
234150768
ullddrurdllurdruldr
下载源码:
例:输出由数字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
下载源码: