`

图的深度优先搜索-求解迷宫解空间

阅读更多
1.原理描述:
  给定图G的初始状态是所有顶点均未曾访问过,在G中任选一顶点V为初始出发点(源点、根结点)。
则描述如下:首先访问出发点V,并将其标记为已访问过;然后依次从V出发搜索V的每个邻接点(子结点)W。
若W未曾访问过,则以W为新的出发点继续进行深度优先遍历,直到图中所有和源点V有路径相同的顶点(从源点
可达的顶点)均已被访问为止。若此图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复
上述过程,直到图中所有顶点均已被访问为止。

2.算法描述
  (1) 确定图的存储方式。
  (2) 设计搜索过程中的操作,其中包括为输出问题解而进行的存储操作。
  (3) 搜索到问题的解,则输出;否则回溯。
  (4) 一般在回溯前应该将结点恢复为原始状态,特别是在多解问题中。

3.一种实现:走迷宫问题。给定入口,求解搜索到出口的解空间。

package com.maozj.datastruct.graphic;

/**
 * create on 2010.05.15 说明:图的深度优先搜索
 * 
 * @author 毛正吉
 * @version v1.0
 * 
 * 
 */
public class DeepSearch {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		DeepSearch ds = new DeepSearch();
		ds.search(0, 0);
		System.out.println("\n"+ds.getTotal());
	}

	private int[][] maze = {
			{ 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 1, 1, 1, 1, 0, 1, 0 }, 
			{ 0, 0, 0, 0, 1, 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, 1, 0 } };
	
	private int[] fx = { 1, -1, 0, 0 };
	private int[] fy = { 0, 0, -1, 1 };
	private int total;

	public DeepSearch() {
		total = 0;
		// 入口坐标设置已走标志
		maze[0][0] = 3;
	}

	public void search(int i, int j) {
		int k, newi, newj;
		// 搜索可达的方格
		for (k = 0; k < 4; k++)
			if (check(i, j, k)) {
				newi = i + fx[k];
				newj = j + fy[k];
				// 来到新位置后,设置已走过标志
				maze[newi][newj] = 3;
				// 如到出口则输出,否则下一步递归
				if (newi == 7 && newj == 7) {
					Out();
				} else {
					search(newi, newj);
				}
			}
		// 标识走入死胡同的方格
		maze[i][j] = 2;
	}

	public void Out() {
		int i, j;
		for (i = 0; i < 8; i++) {
			System.out.println("");
			for (j = 0; j < 8; j++) {
				if (maze[i][j] == 3) {
					System.out.print("V");
					total++;
				} else {
					System.out.print("*");
				}
			}
		}
	}

	public boolean check(int i, int j, int k) {
		boolean bool = true;
		i += fx[k];
		j += fy[k];
		if (i < 0 || i > 7 || j < 0 || j > 7) {// 是否在迷宫内
			bool = false;
		} else if (maze[i][j] != 0) {// 是否可行
			bool = false;
		}
		return bool;
	}

	public int getTotal() {
		return total;
	}

}
分享到:
评论

相关推荐

    基于A搜索和深度优先搜索解迷宫问题完整项目代码

    本文利用A*算法求解迷宫,按照A*算法的思想,针对迷宫问题提出了求解方案、制定了启发函数、在搜索中使用启发信息,缩小搜索的空间,尽快的求得问题的解,并编程验证了该算法的有效性。 关键词:迷宫问题 ;A*算法...

    基于Python实现的迷宫搜索游戏源码+项目详细说明(课程作业).zip

    BFS也是常用的迷宫问题求解算法,通过广度优先的方法,通常来说广度优先搜索在路径搜索中可以得到最优解。如果迷宫有且仅有唯一解,该算法所探索的格子一般远高于DFS探索的空间,但如果迷宫中有多个路径存在时,该...

    leetcode耗时-MazeAlgorithms:使用最小生成树和一些递归算法实现的随机迷宫生成器

    虽然深度优先搜索和随机 Prim 需要第一种类型的表示,但递归除法和随机 Kruskal 必须基于第二种类型。 本研究中使用的所有算法都生成没有循环路线或封闭空间的迷宫,这保证了迷宫中任意两个单元格之间存在唯一路径。...

    MazeGeneratorAndSolver:生成随机迷宫并解决它们

    然后程序将使用广度优先搜索 (BFS) 和深度优先搜索 (DFS) 来解决每个迷宫。 BFS 只找到一条也是最短路径的路径。 DFS 找到所有可用路径,找到的路径总数显示在最底部。 路径用 (#) 字符清楚地标出。 路径长度在每个...

    MAZE:Python中的真迷宫生成器(RBT)和求解器(后面是右手)。 2018年Spring

    真正的迷宫生成器,具有深度优先搜索/递归回溯功能。 迷宫求解器使用右手跟随算法。 生成器脚本将根据sizes.txt指定的大小制作迷宫。 求解器脚本需要指定输入迷宫。 真正的迷宫不包含循环,也就是说,从头到尾只有...

    数据结构、算法与应用:C++语言描述(原书第2版)第二部分

    16.8.5 深度优先搜索的实现 16.8.6 方法graph::dfs的复杂性分析 16.9 应用 16.9.1 寻找一条路径 16.9.2 连通图及其构成 16.9.3 生成树 第三部分 算法设计方法 第17章 贪婪算法 17.1 最优化问题 17.2 贪婪算法思想...

    数据结构、算法与应用--C++语言描述

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

    数据结构算法与应用-C++语言描述

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

    数据结构算法与应用-C__语言描述

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

    数据结构算法与应用-C C++语言描述

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

    数据结构算法与应用-C++语言描述.rar

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3...

    C++语言描述(PDF合集)

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

    数据结构算法与应用(C++语言描述).rar

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

    数据结构C++描述

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

    数据结构 C++描述

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

    数据结构(C语言描述)

    12.10.5 深度优先搜索 397 12.11 应用 399 12.11.1 寻找路径 399 12.11.2 连通图及其构件 400 12.11.3 生成树 402 第三部分 算法设计方法 第13章 贪婪算法 405 13.1 最优化问题 405 13.2 算法思想 406 13.3 应用 409...

Global site tag (gtag.js) - Google Analytics