- 浏览: 604278 次
- 来自: ...
文章分类
最新评论
-
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 632... -
求推箱子的最小步数(java)
2014-05-06 08:32 3776题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3062POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3337回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1848一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1943很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5941Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1248一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 2030先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2316一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2270继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4983深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1445如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1504广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1675有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2131再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2280凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1112最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1285矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
【标题】:“广度优先搜索学习五例之二(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*搜索,通过结合路径代价和预计到达目标的...
而图的遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS),则为处理复杂数据结构提供了有力的工具。更高级的算法,如动态规划,则能够指导学习者如何将复杂问题分解为更易于管理和求解的子问题。 第二部分的...
此外,C语言也常用于实现图的遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS)。这些算法在解决网络路由、社交网络分析等问题时有着广泛的应用。还有动态规划、贪心算法、回溯法等高级算法,它们在解决复杂...
1. **算法基础**:书中涵盖的基础算法包括排序(快速排序、归并排序、堆排序等)、搜索(深度优先搜索、广度优先搜索)以及动态规划。这些是任何程序员都需要掌握的核心技能,对于解决实际问题至关重要。 2. **数据...
2. **搜索算法**:如二分查找、广度优先搜索(BFS)、深度优先搜索(DFS),以及哈希表查找等。这些算法在数据检索和遍历复杂结构时发挥关键作用。 3. **图论算法**:如Dijkstra最短路径算法、Floyd-Warshall全连接...