- 浏览: 600347 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈或递归来实现,而广度优先搜索通过队列来实现。
广度优先搜索:
它首先访问起始顶点的所有邻接点,然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。
图的广度优先搜索,要遵守以下规则:
(0) 选取某一顶点作为开始搜索的起点(当前顶点)入队列,标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点,这个点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。
例二:迷宫问题
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
下载源码
广度优先搜索:
它首先访问起始顶点的所有邻接点,然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。
图的广度优先搜索,要遵守以下规则:
(0) 选取某一顶点作为开始搜索的起点(当前顶点)入队列,标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点,这个点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。
例一:文件目录的广度优先遍历 private static void BFS(File file) throws IOException{ System.out.println(file.getCanonicalPath());//先访问起点 Queue< File> queue = new LinkedList< File>(); queue.offer(file); //起点入队 File fileInQueue = null; while (queue.size() > 0) { fileInQueue = queue.poll(); //当前顶点出队列 File[] files =fileInQueue.listFiles(); //求出当前顶点的所有邻接点 for (File eachFile : files) {//依次访问当前顶点的所有邻接点 if (eachFile.isFile()) {//标记这个邻接点已访问,是文件没有必要入队列 System.out.println("file:" + eachFile.getCanonicalPath()); } else {//标记这个邻接点已访问,是目录则入队列 System.out.println("dir--:" + eachFile.getCanonicalPath()); queue.offer(eachFile); } }//当前顶点所有邻接点访问完毕 }//队列为空退出 }
例二:迷宫问题
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
import java.util.*; public class Main{ private Point cur,next;//当前顶点及它的邻接点 private Point record[][];//用来记录路径 private int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};//沿四个方向,右,下,左,上 private int mark[][]; //迷宫数组 public Main(int mark[][]){//构造函数 this.mark=mark; record=new Point[5][5]; for(int i=0;i< 5;i++) for(int j=0;j< 5;j++) record[i][j]=new Point(); cur=new Point(); next=new Point(); } public void bfs(){ //广度优先搜索迷宫 int i; Queue<Point> qu=new LinkedList<Point>(); cur.x=0; cur.y=0; qu.offer(cur); //起点入队 mark[0][0]=1; //标记为已访问 while(!qu.isEmpty()) { //队列非空 cur=qu.poll(); //队列头节点出队,当前节点 //访问当前节点的所有邻接点,可能有四个,沿四个方向,右,下,左,上 for(i=0;i<4;i++){ next.x=cur.x+dir[i][0]; next.y=cur.y+dir[i][1]; if(next.x==4&&next.y==4){//如果是出口 record[next.x][next.y].x=cur.x; //这个节点存上个节点的坐标 record[next.x][next.y].y=cur.y; return; } if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5&&mark[next.x][next.y]==0){ //如果是邻接点 //这个节点存上个节点的坐标 record[next.x][next.y].x=cur.x; //这个节点存上个节点的坐标 record[next.x][next.y].y=cur.y; mark[next.x][next.y]=1; //标记此邻接点已访问 qu.offer(new Point(next.x,next.y)); //入队 } }//当前点的所有邻接点访问完毕 } //队列为空 } public void print(){ Point point[]=new Point[50]; int i=4;int j=4;int k=0; int m=0;int n=0; while(i!=0||j!=0)/////把得到的记录record[][]存起来 { m=i;n=j; point[k]=record[m][n]; i=record[m][n].x; j=record[m][n].y; k++; } for(i=k-1;i>=0;i--)/////////////逆序输出 System.out.printf("(%d, %d)\n",point[i].x,point[i].y); System.out.printf("(4, 4)\n");////最后要打印的,之前没记录它 } public static void main(String[] args) { Scanner in=new Scanner(System.in); int[][] mark=new int[5][5]; for(int i=0;i< 5;i++) for(int j=0;j< 5;j++) mark[i][j]=in.nextInt(); Main m=new Main(mark); m.bfs(); m.print(); } } class Point { int x = 0; int y = 0; public Point() { this(0, 0); } public Point(int x, int y) { this.x = x; this.y = y; } public boolean equals(Point p) { return (x == p.x) && (y == p.y); } @Override public String toString() { return "(" + x + ", " + y + ")"; } }
下载源码
发表评论
-
龙抬头
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-16 15:26 1147例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1491广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之二(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矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
【标题】:“广度优先搜索学习五例之四” 在计算机科学中,广度优先搜索(Breadth-First Search,简称BFS)是一种用于遍历或搜索树或图的算法。它按照从根节点开始,逐层进行探索的方式进行。在本案例中,我们可能...
【标题】:“广度优先搜索学习五例之二(JAVA)” 在计算机科学中,图算法是解决问题的关键工具之一,而广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或搜索树或图的算法。本篇文章将重点讲解如何在...
【标题】"广度优先搜索学习五例之三"涉及的是图论算法中的一个重要概念——广度优先搜索(Breadth-First Search, BFS)。在计算机科学中,BFS是一种用于遍历或搜索树或图的算法,尤其适用于查找最短路径问题。此标题...
在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...
在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...
在这个“深度优先搜索学习五例之四”的主题中,我们将重点关注使用Java实现DFS解决具体问题的情况。这篇博客文章可能通过一个具体的实例,如迷宫求解,来演示如何利用DFS进行递归或栈操作。 首先,我们来看"MazeDsf...
盲目搜索如宽度优先搜索(BFS)和深度优先搜索(DFS),在未知环境中探索所有可能的解决方案路径,虽然简单但效率较低。启发式搜索则依据某种评估函数来指导搜索方向,如A*搜索,通过结合路径代价和预计到达目标的...
总结来说,搜索是人工智能问题求解的关键技术之一,包括但不限于盲目搜索(如宽度优先搜索)和启发式搜索。这些方法在游戏策略、知识表示、规划等领域有广泛应用。理解并掌握搜索策略对于深入学习人工智能至关重要。
盲目搜索遵循预设的控制策略,不利用中间信息来改进策略,例如深度优先搜索和广度优先搜索。而启发式搜索则引入了与问题相关的启发式信息,如评估函数,以引导搜索向最有可能导致解的方向发展,如A*搜索算法。启发式...
- 广度优先搜索(BFS):一种用于遍历或搜索树或图的算法。它先访问起始点的邻接节点,然后是邻接节点的邻接节点,依此类推。 - 启发式搜索:利用特定问题领域的知识来引导搜索过程,如A*搜索算法。 - 双向搜索:...
搜索算法如二分查找、广度优先搜索(BFS)和深度优先搜索(DFS),在解决图论问题和树形结构问题时非常关键。动态规划是一种强大的问题解决方法,通过构建状态转移方程,可以解决很多复杂的问题,如斐波那契数列、...
在C语言中实现这样的算法,通常会用到深度优先搜索(DFS)或广度优先搜索(BFS)等图遍历策略,也可能涉及动态规划等复杂算法。 通过这个文件,学习者可以了解到如何在C语言中表示图,如何遍历图以及如何设计和实现...
盲目搜索是一种不考虑问题特性的简单搜索方法,例如宽度优先搜索(BFS)和深度优先搜索(DFS)。而启发式搜索则引入了估计代价或接近目标程度的函数,如A*搜索算法,它结合了盲目搜索和启发式信息,能够在有限计算...
例如,快速排序、归并排序、二分查找、哈希表、贪心算法、深度优先搜索和广度优先搜索等。这些都是ACM竞赛中常见的问题类型,学习这些算法不仅可以提升你的编程能力,也能训练你的逻辑思维和问题解决技巧。 C语言的...
图的遍历算法是图论中的基础概念之一,深度优先遍历和广度优先遍历各有优缺点,具体选择哪种遍历方法取决于实际应用场景的需求。例如,在搜索最短路径问题中,广度优先遍历更合适;而在搜索所有可能路径的问题中,...
最小生成树是图论中的一个重要概念,特别是在...通过深度优先搜索和广度优先搜索,我们可以找到图中的路径和最短路径,进而构造出最小生成树。这些算法在解决实际问题如网络设计、运输调度等场景中具有广泛的应用价值。
5. **算法实现**:C语言是实现算法的理想工具,实例可能涵盖了排序(如冒泡排序、快速排序)、查找(如线性查找、二分查找)、图算法(如深度优先搜索、广度优先搜索)等经典算法。 6. **游戏编程**:例如“俄罗斯...
8. **图形算法**:如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra算法和Floyd算法用于找到图中两点间的最短路径。 9. **数学算法**:如大整数运算、矩阵运算、素数检测、组合数学等,这些算法在密码学...
迭代则在很多情况下提供更高效的解决方案,如深度优先搜索、广度优先搜索等。 10. **字符串处理**:KMP算法、Rabin-Karp模式匹配算法、Z算法等,这些算法在文本处理、搜索引擎等领域有着广泛的应用。 通过《经典...