+关注继续查看

# 正文

## 算法介绍

开始

当栈为非空时，继续执行，否则算法结束
取得队栈顶点V；访问并标记为已访问
如果顶点V有未被访问过的子节点
查找顶点V的第一个未被访问过的子节点W1
标记W1为已访问
将W1入栈
否则将顶点V出栈

## 代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Robot {
//行数
public static int colomnNum;

//列数
public static int rowNum;

//障碍物数量
public static int obstacleNum;

//用于深度优先搜索的栈
public static Stack<State> stack;

//地图
public static String[][] map;

//灰尘坐标列表
public static List<Point> dirtList;

//closeList，用于存放已经存在的state
public static List<State> closeList;

//遍历总耗费
public static int cost = 0;

public static void main(String[] args) {
State initialState = new State();
Scanner sc = new Scanner(System.in);
rowNum = sc.nextInt();
colomnNum = sc.nextInt();
map = new String[rowNum][colomnNum];
dirtList = new ArrayList<Point>();
closeList = new ArrayList<State>();
sc.nextLine();
for(int i=0; i<rowNum; i++)
{
System.out.println("Please Enter the Elements in row " + (i + 1) + ":");
String line = sc.nextLine();
for(int j=0; j<colomnNum; j++)
{
//统计障碍物数量
if(line.charAt(j) == '#')
{
obstacleNum++;
}

//将灰尘格子坐标存入list中
if(line.charAt(j) == '*')
{
}

//设置机器人初始坐标
if(line.charAt(j) == '@')
{
initialState.setRobotLocation(new Point(i, j));
}

//初始化地图
map[i][j] = line.charAt(j) + "";
}
}
sc.close();
initialState.setDirtList(dirtList);

//初始化栈
stack = new Stack<State>();

stack.push(initialState);
cost++;

//遍历开始
while(!stack.isEmpty()){
State state = stack.peek();
//如果达到目标,输出结果并退出
if(isgoal(state)){
output(state);
return;
}
calculate(state);
}
}

public static void calculate(State state){
//获取当前机器人的坐标
int x = state.getRobotLocation().getX();
int y = state.getRobotLocation().getY();

//如果当前的点是灰尘并且没有被清理
if(map[x][y].equals("*") && !isCleared(new Point(x, y), state.getDirtList())){
State newState = new State();
List<Point> newdirtList = new ArrayList<Point>();
//在新的state中,将灰尘列表更新,即去掉当前点的坐标
for(Point point : state.getDirtList())
{
if(point.getX() == x && point.getY() == y)
continue;
else
}
newState.setDirtList(newdirtList);
newState.setRobotLocation(new Point(x, y));
//C代表Clean操作
newState.setOperation("C");
newState.setPreviousState(state);

//若新产生的状态与任意一个遍历过的状态都不同,则进入栈
if(!isDuplicated(newState)){
stack.push(newState);
cost++;
return;
}
}

//若当前机器人坐标下方有格子并且不是障碍物
if(x + 1 < rowNum)
{
if(!map[x+1][y].equals("#"))
{
State newState = new State();
newState.setDirtList(state.getDirtList());
newState.setRobotLocation(new Point(x + 1, y));
//S代表South,即向下方移动一个格子
newState.setOperation("S");
newState.setPreviousState(state);
if(!isDuplicated(newState)){
stack.push(newState);
//加入到closeList中
cost++;
return;
}
}
}

//若当前机器人坐标上方有格子并且不是障碍物
if(x - 1 >= 0)
{
if(!map[x-1][y].equals("#"))
{
State newState = new State();
newState.setDirtList(state.getDirtList());
newState.setRobotLocation(new Point(x - 1, y));
//N代表North,即向上方移动一个格子
newState.setOperation("N");
newState.setPreviousState(state);
if(!isDuplicated(newState)){
stack.push(newState);
cost++;
return;
}
}
}

//若当前机器人坐标左侧有格子并且不是障碍物
if(y - 1 >= 0)
{
if(!map[x][y-1].equals("#"))
{
State newState = new State();
newState.setDirtList(state.getDirtList());
newState.setRobotLocation(new Point(x, y - 1));
//W代表West,即向左侧移动一个格子
newState.setOperation("W");
newState.setPreviousState(state);
if(!isDuplicated(newState)){
stack.push(newState);
cost++;
return;
}
}
}

//若当前机器人坐标右侧有格子并且不是障碍物
if(y + 1 < colomnNum)
{
if(!map[x][y+1].equals("#"))
{
State newState = new State();
newState.setDirtList(state.getDirtList());
newState.setRobotLocation(new Point(x, y + 1));
//E代表East,即向右侧移动一个格子
newState.setOperation("E");
newState.setPreviousState(state);
if(!isDuplicated(newState)){
stack.push(newState);
cost++;
return;
}
}
}

stack.pop();
}

//判断是否已经达到目标,即当前遍历到的state中是否已经没有灰尘需要清理
public static boolean isgoal(State state){
if(state.getDirtList().isEmpty())
return true;
return false;
}

//输出,由最后一个state一步一步回溯到起始state
public static void output(State state){
String output = "";
//回溯期间把每一个state的操作(由于直接输出的话是倒序)加入到output字符串之前,再输出output
while(state != null){
if(state.getOperation() != null)
output = state.getOperation() + "\r\n" + output;
state = state.getPreviousState();
}
System.out.println(output);
//最后输出遍历过的节点(state)数量
System.out.println(cost);
}

//判断节点是否存在,即将state与closeList中的state相比较,若都不相同则为全新节点
public static boolean isDuplicated(State state){
for(State state2 : closeList){
if(State.isSameState(state, state2))
return true;
}
return false;
}

//判断地图中当前位置的灰尘在这个state中是否已经被除去。
public static boolean isCleared(Point point, List<Point> list){
for(Point p : list){
if(Point.isSamePoint(p, point))
return false;
}
return true;
}

}


开始

当栈为非空时，继续执行，否则算法结束
取得队栈顶点V；访问并标记为已访问
如果顶点V有未被访问过的子节点
查找顶点V的第一个未被访问过的子节点W1
标记W1为已访问
将W1入栈
否则将顶点V出栈

stack.pop();

## 运行结果与广度优先搜索的对比

@#*
*__
#*_

Please Enter Row Number:
3
3
Please Enter the Elements in row 1:
@#*
Please Enter the Elements in row 2:
*__
Please Enter the Elements in row 3:
#*_
S
C
E
S
C
N
E
N
C

14

Please Enter Row Number:
3
3
Please Enter the Elements in row 1:
@#*
Please Enter the Elements in row 2:
*__
Please Enter the Elements in row 3:
#*_
S
C
E
S
C
N
E
N
C

45

*#_*
_*__
_#_@

Please Enter Row Number:
3
4
Please Enter the Elements in row 1:
*#_*
Please Enter the Elements in row 2:
_*__
Please Enter the Elements in row 3:
_#_@
N
N
C
S
S
W
N
W
C
W
N
C

15

Please Enter Row Number:
3
4
Please Enter the Elements in row 1:
*#_*
Please Enter the Elements in row 2:
_*__
Please Enter the Elements in row 3:
_#_@
N
N
C
S
W
W
C
W
N
C

56

O(bm),BM

# 结束语

《中国人工智能学会通讯》——7.32 量化计算 建立情感数据库

1583 0
《中国人工智能学会通讯》——4.36 信号量化

949 0
《中国人工智能学会通讯》——4.35 时变传输周期

979 0
《中国人工智能学会通讯》——4.33 单包传输与多包传输

1283 0
《中国人工智能学会通讯》——4.13 采用关联滤波器的卷积神经网络

1305 0
《中国人工智能学会通讯》——4.15 关联滤波器

1317 0
《中国人工智能学会通讯》——11.36 非线性系统 H∞ 最优控制

1200 0
+关注

java，前端，算法相关技术专家