- 浏览: 604324 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
一、深度优先搜索框架一递归实现,流程如下:
例:八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
运行:
D:\java>java Queen
No1: 1 5 8 6 3 7 2 4
No2: 1 6 8 3 7 4 2 5
No3: 1 7 4 6 8 2 5 3
No4: 1 7 5 8 2 4 6 3
No5: 2 4 6 8 3 1 7 5
No6: 2 5 7 1 3 8 6 4
No7: 2 5 7 4 1 8 6 3
..........................
92
二、深度优先搜索框架二(栈实现)流程如下:
例:深度优先搜索之迷宫问题
运行:
D:\java>java MazeDsf
入口(0,0),出口(8,7)的迷宫,0为通道,1为障碍:
01111111
00000000
01111010
00000010
01000010
01011010
01000011
01001000
01111100
一条迷宫路径:
(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(1,4)->(1,5)->(2,5)->(3,5)->(4,5)->(5,5)->(6,
5)->(7,5)->(7,6)->(7,7)->(8,7)
public void dfs(int v) { visited[v] = true; //访问起点v System.out.print(v+" "); for (int i = 0; i < k; i++) { //递归调用搜索没有被访问过的当前节点的下一个节点(邻接点) if (G[v][i] == 1 && !visited[i])//G[v][i]是图的邻接矩阵 dfs(i);//递归调用 } }
例:八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
public class Queen{ private int n = 8; private int a[]; //皇后放在 ( i, a[i] ) private boolean visited[]; //如果visited[i]为true,表示第i列已经被占了. int total = 0; //方案总数 public Queen(){ a=new int[8]; visited =new boolean[8]; } public static void main(String args[]){ Queen m=new Queen(); m.dfs(0); System.out.println(m.getTotal()); } private boolean can(int d){ //判断第d行的Queen可否放在第a[d]列 if( visited[a[d]] ) return false; //已经被占,则返回false for(int i=0; i<d; i++) if( Math.abs(a[d]-a[i])== Math.abs(i-d) )//如果第i行和第d行的Queen在同一对角线上,则返回false return false; return true; } private void output(){ int i; total++; System.out.print("No" +total +": "); for(i=0; i<n; i++) System.out.print(a[i]+1 +" "); System.out.println(); } public int getTotal(){ return total; } private void dfs(int d){ if( d>=n ){ //找到一个解并输出 output(); return; } for(int i=0; i<n; i++){ //每一行均有n种放法 a[d] = i; //第d行的Queen放在第i列 if(can(d)){ visited[i] = true; dfs(d+1); //如果第d行的方法可行,就放下一行 visited[i] = false;//恢复现场 } } } }
运行:
D:\java>java Queen
No1: 1 5 8 6 3 7 2 4
No2: 1 6 8 3 7 4 2 5
No3: 1 7 4 6 8 2 5 3
No4: 1 7 5 8 2 4 6 3
No5: 2 4 6 8 3 1 7 5
No6: 2 5 7 1 3 8 6 4
No7: 2 5 7 4 1 8 6 3
..........................
92
二、深度优先搜索框架二(栈实现)流程如下:
例:深度优先搜索之迷宫问题
import java.util.Stack; //////////////////////////////////////////////// //深度优先搜索之迷宫问题 public class MazeDsf{ private static final int M=9; private static final int N=8; //迷宫矩阵,0为通道,1为障碍 //入口(0,0),出口(8,7) private int[][] Matrix = { { 0, 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1, 0 }, { 0, 1, 0, 0, 0, 0, 1, 0 }, { 0, 1, 0, 1, 1, 0, 1, 0 }, { 0, 1, 0, 0, 0, 0, 1, 1 }, { 0, 1, 0, 0, 1, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 0, 0 } }; //标记数组,初始化为false boolean visited[][]; public MazeDsf(){ visited=new boolean[M][N]; } //节点 class Node{ int x; int y; Node(int i,int j){ x = i; y = j; } } /*坐标系统 0 ----------------->y | | | | | V x */ //右下上左 private int x_off[] = {0,1,-1,0}; private int y_off[] = {1,0,0,-1}; //输出状态 private void PrintVisited(){ for(int i = 0; i < M; ++i){ for(int j = 0; j < N; ++j) System.out.print(visited[i][j]+" "); System.out.println(); } } //输出迷宫 private void PrintMatrix(){ System.out.println("入口(0,0),出口(8,7)的迷宫,0为通道,1为障碍:"); for(int i = 0; i < M; ++i){ for(int j = 0; j < N; ++j) System.out.print(Matrix[i][j]); System.out.println(); } } //输出一条路径 //由于入栈路径是正序,要倒过来输出才是从入口到出口的路劲 private void PrintPath(Stack<Node> s){ System.out.println("一条迷宫路径:"); Stack<Node> t=new Stack<Node>(); while(!s.empty()){ t.push(s.pop()); } while(!t.empty()){ System.out.print("("+t.peek().x+","+t.peek().y+")->"); t.pop(); } System.out.println(); } //深度优先搜索一条可能的路径 private void DFS(){ //1.初始化栈 Stack<Node> s=new Stack<Node>(); Node start=new Node(0,0); s.push(start); visited[0][0] = true; while(!s.empty()){ //2.取得栈顶元素(注意不从栈内删除) Node top = s.peek(); //3.遍历栈顶元素的邻节点 int i=0; for(i = 0; i<4; ++i){ //右下上左 int nx = top.x + x_off[i]; int ny = top.y + y_off[i]; if(nx >= 0 && nx < M && ny>=0 && ny< N &&!visited[nx][ny] && Matrix[nx][ny] == 0){ //4.把满足条件的元素标记为已处理,并压入栈内 Node newNode=new Node(nx,ny); visited[nx][ny] = true; s.push(newNode); //找到出口,终止搜索 if(nx == 8 && ny == 7){ //输出找到的路径 PrintPath(s); return; } break; } } //5.当前节点没有满足条件的邻节点,把当前栈顶元素删除 if(i == 4){ s.pop(); } } } //测试代码主函数 public static void main(String args[]) { MazeDsf maze=new MazeDsf(); maze.PrintMatrix(); maze.DFS(); } }
运行:
D:\java>java MazeDsf
入口(0,0),出口(8,7)的迷宫,0为通道,1为障碍:
01111111
00000000
01111010
00000010
01000010
01011010
01000011
01001000
01111100
一条迷宫路径:
(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(1,4)->(1,5)->(2,5)->(3,5)->(4,5)->(5,5)->(6,
5)->(7,5)->(7,6)->(7,7)->(8,7)
发表评论
-
龙抬头
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 1850一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
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 1249一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 2030先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2270继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4985深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1445如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1169例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1505广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1675有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2132再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2280凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1112最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1285矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
在这个“深度优先搜索学习五例之四”的主题中,我们将重点关注使用Java实现DFS解决具体问题的情况。这篇博客文章可能通过一个具体的实例,如迷宫求解,来演示如何利用DFS进行递归或栈操作。 首先,我们来看"MazeDsf...
在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...
这篇博文“深度优先搜索学习五例之五(JAVA)”可能介绍了DFS在解决实际问题中的应用,尽管描述中没有给出具体细节,但我们可以从一般的角度来探讨DFS以及其在Java中的实现。 DFS的基本思想是从根节点开始,沿着某...
通常,这样的教程会包括代码实现、步骤解析以及为什么选择BFS而不是深度优先搜索(Depth-First Search, DFS)的原因。 【标签】:“源码”、“工具” “源码”标签表明文章会包含实际的Java代码示例,读者可以参考...
【标题】"广度优先搜索学习五例之三"涉及的是图论算法中的一个重要概念——广度优先搜索(Breadth-First Search, BFS)。在计算机科学中,BFS是一种用于遍历或搜索树或图的算法,尤其适用于查找最短路径问题。此标题...
在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...
- **深度优先搜索(DFS)**:递归地探索节点的邻接节点,用于遍历或搜索图。 - **广度优先搜索(BFS)**:使用队列数据结构,按照距离从起点到终点的顺序访问节点。 4. **动态规划(DP)**: - **斐波那契数列**:使用...
2. **搜索算法**:如线性搜索、二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些是解决查找问题的基础,对于理解数据结构至关重要。 3. **图论算法**:例如Dijkstra最短路径算法、Floyd-Warshall所有对...
9. **DFS(深度优先搜索)算法**:DFS是一种用于遍历或搜索树或图的算法,沿着树的深度遍历树的节点,尽可能深地搜索树的分支。在Java中,DFS可以借助于递归或栈来实现。 这些知识点涵盖了计算机科学基础和算法设计...
2. **搜索算法**:二分查找、线性查找、深度优先搜索(DFS)和广度优先搜索(BFS),这些算法在处理数据集合时非常实用。 3. **图论算法**:Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法,它们在网络...
2. **搜索算法**:二分查找、深度优先搜索、广度优先搜索等,探讨如何在数据结构中高效地查找目标元素。 3. **数据结构**:栈、队列、链表、树、图等,如何利用它们来实现各种算法。 4. **动态规划**:如斐波那契...
这些代码可能包括简单的排序算法(冒泡、选择、插入、快速、归并等)、查找算法(顺序、二分、哈希等)、图算法(深度优先搜索、广度优先搜索、最小生成树、最短路径等)以及其他复杂的数据结构实现。 5. **学习...
这个类可能实现了A*算法、Dijkstra算法或者深度优先搜索(DFS)等常见的寻找最短路径的算法。这些算法的核心目标是找到从起点到终点的最短路径,同时尽量避免无效的探索。 以A*算法为例,它结合了Dijkstra算法的...
深度遍历(又称深度优先遍历)是指沿着树的深度遍历树的节点,尽可能深地搜索树的分支,当节点v的所有出边都已被探寻过,搜索将回溯到发现节点v的那条边的起始节点。在目录结构中,这意味着如果当前遍历到的文件是...
在实现这个项目时,我们可能需要学习图算法,如深度优先搜索(DFS)或广度优先搜索(BFS),用于寻找从起点到终点的最短路径。数据结构如栈或队列会在这里发挥重要作用。同时,我们需要理解如何将迷宫表示为二维数组...
2. **搜索算法**:二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些算法在处理数据查找和遍历树形结构时非常有效。 3. **图论算法**:最短路径问题(Dijkstra算法、Floyd算法),最小生成树(Prim算法...
这可能需要使用图遍历算法,如深度优先搜索(DFS)或广度优先搜索(BFS)。 3. **文件输入与输出**: - 输入通常包含每个建筑物的长、宽、高和位置信息,可能以CSV、JSON或其他格式存储。Java的`Scanner`类可用于...
2. **搜索算法**:如二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)。这些算法在处理大量数据时具有重要作用,如在树和图结构中寻找特定元素或路径。 3. **图论算法**:如Dijkstra最短路径算法、Floyd-...
3. **图论算法**:如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法等。 4. **动态规划**:解决许多复杂问题的有效方法,如背包问题、最长公共子序列、...