- 浏览: 600333 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
例:输出由数字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
下载源码:
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
下载源码:
- eightD1.zip (3 KB)
- 下载次数: 2
发表评论
-
龙抬头
2014-11-10 15:06 618... -
求推箱子的最小步数(java)
2014-05-06 08:32 3742题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3053POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3309回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1831一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1922很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5922Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4043一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1242一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 2007先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2310一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2265继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4959深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1439如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1491广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1670有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2119再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2268凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1109最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1266矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
【标题】:“广度优先搜索学习五例之二(JAVA)” 在计算机科学中,图算法是解决问题的关键工具之一,而广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或搜索树或图的算法。本篇文章将重点讲解如何在...
**广度优先搜索(Breadth-First Search, BFS)**是一种在图或树中进行搜索的算法,常用于寻找最短路径或者遍历结构。它遵循“先探索节点的所有邻居,再探索邻居的邻居”的策略,从起点开始,逐层向外扩展。BFS的关键...
【标题】"广度优先搜索学习五例之三"涉及的是图论算法中的一个重要概念——广度优先搜索(Breadth-First Search, BFS)。在计算机科学中,BFS是一种用于遍历或搜索树或图的算法,尤其适用于查找最短路径问题。此标题...
在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...
在这个“深度优先搜索学习五例之四”的主题中,我们将重点关注使用Java实现DFS解决具体问题的情况。这篇博客文章可能通过一个具体的实例,如迷宫求解,来演示如何利用DFS进行递归或栈操作。 首先,我们来看"MazeDsf...
在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...
通过深入学习和实践这些案例,我们可以掌握如何运用广度优先搜索解决实际问题,并且在遇到类似问题时能够快速找到合适的算法和方法。此外,对于同一问题的深入探讨可以帮助我们探索更优的解决方案,比如通过剪枝技术...
我们将依次讨论深度优先搜索(DFS)、宽度优先搜索(BFS)以及启发式搜索策略,如A*算法,并结合图形化界面来直观展示搜索过程。 一、八数码问题简介 八数码问题是一个在3x3的网格上移动数字,目标是通过最少的步数...
广度优先搜索(BFS)是一种用于遍历或搜索树或图的算法,其基本思想是从根节点开始,沿着树的宽度优先遍历,直到找到目标节点或者遍历完所有节点。在本例中,我们将关注如何运用广度优先搜索(BFS)来寻找迷宫中的...
**广度优先搜索(BFS)算法是一种在图或树中搜索节点的遍历方法,其基本思想是从起点开始,先访问所有距离起点最近的节点,然后再依次访问更远的节点。这种算法常用于查找最短路径、解决迷宫问题等。在本程序包中,...
在爬虫技术中,两种常见的遍历策略是深度优先搜索(DFS, Depth-First Search)和广度优先搜索(BFS, Breadth-First Search)。本篇将重点探讨广度优先算法及其在网络爬虫中的应用。 首先,广度优先算法的核心思想是...
该程序可能包含了实现八数码问题的各种算法,如深度优先搜索(DFS)、广度优先搜索(BFS)或A*搜索等。 描述中的"可以直接运行的程序,是八数码的C的源代码,直接运行即可"表明这个压缩包里的1.cpp文件是一个可执行的C...
盲目搜索如宽度优先搜索(BFS)和深度优先搜索(DFS),在未知环境中探索所有可能的解决方案路径,虽然简单但效率较低。启发式搜索则依据某种评估函数来指导搜索方向,如A*搜索,通过结合路径代价和预计到达目标的...
这些例子可能包含经典的排序算法(如插入排序、选择排序)、查找算法(如二分查找)、图算法(如深度优先搜索、广度优先搜索)以及其他实用的算法如动态规划和回溯法。通过实践这些算法,学习者将能提高问题解决能力...
总结来说,搜索是人工智能问题求解的关键技术之一,包括但不限于盲目搜索(如宽度优先搜索)和启发式搜索。这些方法在游戏策略、知识表示、规划等领域有广泛应用。理解并掌握搜索策略对于深入学习人工智能至关重要。
此外,C语言也常用于实现图的遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS)。这些算法在解决网络路由、社交网络分析等问题时有着广泛的应用。还有动态规划、贪心算法、回溯法等高级算法,它们在解决复杂...
例如,你可以在这里找到基础的冒泡排序、快速排序,二分查找,图的遍历算法如深度优先搜索和广度优先搜索,以及更复杂的动态规划问题解决方案。这些算法的C语言实现不仅帮助学习者理解算法原理,还能让他们熟悉如何...