广度优先搜索解决“营救公主”问题
在之前的一片文章(迷宫营救公主算法)中提供了一个半成品的解决方案，之所以说他是半成品，是因为首先选择的算法就不对，采用的是深度优先搜索，其次也没有真正的用对深度优先算法，走过的点应该标记为已经走过，而不应该重复遍历该节点。下面的文章对于广度优先和深度优先两种算法的解释非常到位。今天准备把这个问题再完整的用正确的算法解答一遍。
文章链接：【图论】广度优先搜索和深度优先搜索。
就营救公主的问题而言，这里不再重复描述问题了，请点击这里查看题目分析：链接。这次选用广度优先算法来解决该问题。上面的算法介绍文章中对该算法已经分析得非常清晰了。先给解决本问题的算法伪代码：
这里每个节点有三种状态：
*)该状态表示墙，如果访问到该类型节点，则不用继续遍历。应退回至上层节点。
.)该状态表示该节点通行，访问到该节点应该将节点压入队列。并将该节点标记为已经访问。为区别图中已经有的几种元素，这里定义一个新的标记’#’来表示已经访问过的节点。同时可以使用一个二维数组记录从起始节点到该节点的访问距离step[i][j]，该值应该是由其上一个节点的值加1之后得到。这样起始节点的值为1，依次每一个节点的距离都可以得到。
P)该状态表示已经搜索到了公主的位置，搜索结束。这时给出P点的距离，如果该距离值在给定的范围内，则可以营救出公主，否则失败。
解决问题的关键在于用一个step数组记录每个节点的距离起始点的距离，另外用一个’#’字符标记该节点已经被访问过，避免走“回头路”。
BFS(G, s)init V[G] // 由测试用例实现。
status[s] = S // s王子的位置，通过一次遍历可以获取其坐标。
int count = -1;
queue q
q.add(s) // 将王子的位置入队。
while !q.isEmpty()
t = q.poll()
for each vertex v in Adj[t] // 与t邻接的点
if status[v] = 'P' // 只对未访问的操作
count = step[v] = step[t] + 1
q.clear()
break
elseif status[v] = '.'
status[v] = '#' // 标记为已经走过该节点
q.add(v)
step[v] = step[t] + 1 // 累加得到当前节点的步长
elseif status[v] = '*'
step[v] = -1 // 遇到墙，则将该节点的距离置为-1，在遍历完整个图时，
// 如果遇到最后一个节点的值为-1，则表明没有找到。
else
error
if count != -1
if count < L
return true
return false
package com;import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城堡，魔王的城堡是一座很大的迷宫。
* 为了使问题简单化，我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙，王子不能通过。王子只
* 能移动到相邻(上下左右四个方向)的方格内，并且一秒只能移动一步。地图由'S'，'P'，'.'，'*'
* 四种符号构成，'.'表示王子可以通过，'*'表示墙，王子不能通过；'S'表示王子的位置；'P'表示公主
* 的位置；T表示公主存活的剩余时间，王子必须在T秒内到达公主的位置，才能救活公主。如下图所示：
*/
public class SavePrincess
{
private int m;
private int n;
private char[][] visited;
private Position s = null;
private Position p = null;
public static void main(String[] args)
{
char maze[][] = {
/* 0 1 2 3 4 5 6 7 8 9 */
/* 0 */{ '.', '*', '.', '.', '.', '*', '.', '.', '.', '.' },
/* 1 */{ '*', 'S', '*', '.', '.', '.', '.', '.', '.', '.' },
/* 2 */{ '.', '*', '*', '.', '.', '.', '.', '.', '.', '.' },
/* 3 */{ '.', '.', '*', '*', '*', '.', '.', '.', '.', '.' },
/* 4 */{ '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
/* 5 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
/* 6 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
/* 7 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
/* 8 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
/* 9 */{ '.', 'P', '.', '.', '*', '.', '.', '.', '.', '.' } };
new SavePrincess().saved(maze, 10, 8, 11);
}
/**
* @param vis
* M行N列迷宫
* @param m
* M
* @param n
* N
* @param t
* T
*
* @return boolean true表示营救成功，反之表示失败。
*/
public boolean saved(char[][] vis, int m, int n, int t)
{
if (t < 0)
{
return false;
}
this.m = m;
this.n = n;
this.visited = vis;
int step[][] = new int[m][n];
init(m, n, step);
if (s == null || p == null)
{
System.out.println("input visited error!");
return false;
}
Queue<Position> queue = new LinkedList<Position>();
queue.add(s);
int l = -1;
while (!queue.isEmpty())
{
Position e = queue.poll();
l = dealOneNode(step, queue, l, e);
}
if (l != -1 && l <= t)
{
System.out.println("Saved the princess in " + l + " seconds!");
return true;
}
System.out.println("failed saved the princess! " + l + " > " + "t");
return false;
}
private void init(int m, int n, int[][] step)
{
for (int i = 0; i != m; i++)
{
for (int j = 0; j != n; j++)
{
System.out.print(visited[i][j]);
System.out.print(' ');
step[i][j] = 0;
switch (visited[i][j])
{
case '*':
break;
case 'S':
this.s = new Position(i, j, 'S');
break;
case '.':
break;
case 'P':
this.p = new Position(i, j, 'P');
break;
default:
System.out.println("input visited error!");
System.exit(-1);
}
}
System.out.println("");
}
}
private int dealOneNode(int[][] step, Queue<Position> queue, int l, Position e)
{
/**
* 在求相邻节点时做了一点优化，遇到墙的节点则不放到相邻节点中。
* 从设计思想和可读性上看不是太好，从运行效率考虑，可以。
*/
for (Position c : getNextPostions(e))
{
switch (c.getV())
{
case 'P':
queue.clear();
l = step[e.getI()][e.getJ()] + 1;
break;
case '.':
visited[c.getI()][c.getJ()] = '#';
queue.add(c);
step[c.getI()][c.getJ()] = step[e.getI()][e.getJ()] + 1;
break;
default:
// 不可能进入该分支。
System.err.println("some error!");
break;
}
}
return l;
}
/**
* 取有效节点。
* 遇到墙则不加入相邻节点中。
*
* @param e
* @return
*/
private List<Position> getNextPostions(Position e)
{
int i = e.getI();
int j = e.getJ();
List<Position> lst1 = new LinkedList<Position>();
addOneNode(i + 1, j, lst1);
addOneNode(i, j + 1, lst1);
addOneNode(i - 1, j, lst1);
addOneNode(i, j - 1, lst1);
return lst1;
}
private void addOneNode(int i, int j, List<Position> lst)
{
if (i >= m || i < 0 || j >= n || j < 0)
{
return;
}
char v = visited[i][j];
switch (v)
{
case '.':
case 'P':
lst.add(new Position(i, j, v));
break;
default:
break;
}
}
private class Position
{
private int i;
private int j;
private char v;
public Position(int i, int j, char value)
{
this.i = i;
this.j = j;
this.v = value;
}
public char getV()
{
return v;
}
public int getI()
{
return i;
}
public int getJ()
{
return j;
}
public String toString()
{
return "(" + i + ", " + j + ")";
}
}
}
建议继续学习：
扫一扫订阅我的微信号：IT技术博客大学习
- 作者：童燕群 来源： 忘我的追寻
- 标签： 广度优先
- 发布时间：2013-10-15 13:42:14
-
[17] [译]Google Chrome中的高性能网 -
[14] 最近总结的一些技巧(vim,python,s
-
[14] 在FreeNAS/BSD搭建基于Nginx+
-
[14] 关于Linux的文件系统cache
-
[13] Linux常用系统信息查看命令
-
[11] Linux(Ubuntu 10.04)上安装
-
[9] Centos yum 安装nginx+PHP
-
[8] base64_encode 和 urlenc
-
[7] nginx.conf控制指定的代理ip和ip
-
[7] 根据文件大小删除一个特殊文件名的文件
