我在使用 DFS 作为起点确定迷宫中回溯的算法时遇到问题，之后我想包括启发式成本来确定最短路径。给定 0 和 1 的迷宫，我的猎人节点必须找到猎物节点。我已经做了我能做的，但是当它到达死胡同时，它会"跳"到我的堆栈中的下一个可步行节点，这不是我想要的，我需要能够回溯到那个可步行节点并从那里继续探索迷宫。
1 是路径，0 是墙。
0001000001
0111110101
0100010101
0111011101
0001010001
0111010101
0100010101
0111011101
0001000001
1111111111
主类：
public class main {
public static void main(String[] args) {
//create maze from file
MazeGenerator mazeGenerationTest = new MazeGenerator();
mazeGenerationTest.generateFromTextFile();
//create hunter and prey nodes
Node hunter = new Node(0,3);
Node prey = new Node(0,9);
//setup maze
MazeTraversal mazeTraverse = new MazeTraversal(mazeGenerationTest.getNodeGrid(),hunter,prey);
mazeTraverse.setCols(mazeGenerationTest.getCols());
mazeTraverse.setRows(mazeGenerationTest.getRows());
//run algo
mazeTraverse.dfs();
mazeGenerationTest.seeMaze();
}
}
迷宫生成器类，用于从文本文件读取
public class MazeGenerator {
private Node nodeGrid[][];
private ArrayList<Node> adjList = new ArrayList<Node>();
private int rows = 0;
private int cols = 0;
public MazeGenerator(){
}
public void generateFromTextFile(){
BufferedReader br = null;
try {
br = new BufferedReader(new FileReader(CONSTANTS.MAZE_PATH));
StringBuilder sb = new StringBuilder();
String line = br.readLine();
cols = line.length();
while (line != null) {
rows++;
sb.append(line);
sb.append(System.lineSeparator());
line = br.readLine();
}
br.close();
//set 2d array of node according to rows and cols read from text file, and init nodes
setNodeGrid(getRows(),getCols(),sb.toString());
//seeMaze();
//manualAdjList();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e){
e.printStackTrace();
}
}
public Node[][] getNodeGrid() {
return nodeGrid;
}
/***
* Creates and initializes a 2d node grid.
* @param rows The number of rows for initializing the 2d array
* @param cols The number of columns for initializing the 2d array
* @param mazeTxt The string of maze text read from the file
*/
public void setNodeGrid(int rows, int cols,String mazeTxt) {
this.nodeGrid = new Node[rows][cols];
int nodesAccessed = 0;
//initialise nodes into grid
for(int r = 0; r < rows; r++){
for(int c = 0; c < cols; c++){
if(mazeTxt.charAt(nodesAccessed) != 'n' && mazeTxt.charAt(nodesAccessed) != 'r'){
if(mazeTxt.charAt(nodesAccessed) == '1'){//if node is 1 == path
nodeGrid[r][c] = new Node(r,c,false);
}else{
nodeGrid[r][c] = new Node(r,c,true);//node == 0 is wall
}
}
else{
--c;
}
nodesAccessed++;
}
}
}
public int getRows() {
return rows;
}
public int getCols() {
return cols;
}
public void seeMaze(){
for(int r = 0; r < getRows();r++){
for(int c = 0; c< getCols();c++){
getNodeGrid()[r][c].toString();
}
}
}
}
算法的迷宫遍历类
public MazeTraversal(Node[][] nodeGrid,Node hunter,Node prey){
this.nodeGrid = nodeGrid;
this.hunter = hunter;
this.prey = prey;
}
public void dfs(){
Stack<Node> stack = new Stack<Node>();
Node hunterNode = null;
Node preyNode = null;
Node currentNode = null;
hunterNode = nodeGrid[getHunter().getX()][getHunter().getY()];
preyNode = nodeGrid[getPrey().getX()][getPrey().getY()];
//Add hunter node to stack
stack.push(hunterNode);
System.out.println("Pushed Start-"+hunterNode.toString());
while(!stack.isEmpty()){//while there are items in the stack
currentNode = stack.pop();//pop into currentNode
System.out.println("Popped-"+currentNode.toString());
if(currentNode.equals(preyNode)){
System.out.println("Found!");
return;
}
if(!currentNode.isDiscovered()){//if the current node is not yet discovered
currentNode.setDiscovered(true);//we mark it as discovered
generateNeighboursForNode(currentNode);//discover all neighbours of currentNode and add it to the nodes neighbour list
for(Node neighbour : currentNode.getNeighboursList()){//for all neighbour of current node
if(neighbour.getPredecessor()==null)//we do this check so the next node cannot replace the parent node
neighbour.setPredecessor(currentNode);//and add currentNode as their parentNode.
if(!neighbour.equals(currentNode.getPredecessor()))//if this neighbour is not equal to the parent
{
stack.push(neighbour);// we push to stack, so we do not add the parent into the stack again
System.out.println("Pushed-"+neighbour.toString());
}
}
}else{//discovered
System.out.println("This node is discovered ! " +currentNode.toString());
boolean allDiscovered = true;//assume all is discovered
for(Node neighbour : currentNode.getNeighboursList()){
if(!neighbour.isDiscovered()){//for each neighbour that is not yet discovered;push neighbour
stack.push(neighbour);
System.out.println("Pushed-"+neighbour.toString());
allDiscovered = false;//as long as one neighbour is not yet discovered
}
}
if(allDiscovered){//if all neigbour is discovered
stack.push(currentNode.getPredecessor());//backtrack to parent;push parent
System.out.println("Pushed-"+currentNode.toString());
}
}
}//while end
}
public Node getHunter() {
return hunter;
}
public void setHunter(Node hunter) {
this.hunter = hunter;
}
public Node getPrey() {
return prey;
}
public void setPrey(Node prey) {
this.prey = prey;
}
public int getRows() {
return rows;
}
public void setRows(int rows) {
this.rows = rows;
}
public int getCols() {
return cols;
}
public void setCols(int cols) {
this.cols = cols;
}
public MazeTraversal(Node[][] nodeGrid){
this.nodeGrid = nodeGrid;
}
public void generateNeighboursForNode(Node node){
//add adj nodes
int nodeX = node.getX();
int nodeY = node.getY();
Node currentNode = nodeGrid[nodeX][nodeY];
if(currentNode.isWall()){//if we are looking at a wall we return
return;
}
Node rightNode = null;
if (nodeY < cols - 1){ // the condition for the existence of a right node
rightNode = nodeGrid[nodeX][nodeY+1];
if(!rightNode.isWall()){
currentNode.addNeighbor(rightNode);
}
}
Node bottomNode = null;
if (nodeX < rows - 1){
bottomNode = nodeGrid[nodeX+1][nodeY];// the condition for the existence of a bottom node
if(!bottomNode.isWall()){
currentNode.addNeighbor(bottomNode);
}
}
Node leftNode = null;
if (nodeX > 0){
leftNode = nodeGrid[nodeX-1][nodeY];// the condition for the existence of a left node
if(!leftNode.isWall()){
currentNode.addNeighbor(leftNode);
}
}
Node topNode = null;
if (nodeY > 0){
topNode = nodeGrid[nodeX][nodeY-1];// the condition for the existence of a top node
if(!topNode.isWall()){
currentNode.addNeighbor(topNode);
}
}
System.out.println("Generating neighbours "+node.toString());
}
}
节点类
public class Node {
private Node predecessor;//previous node
private boolean isWall;
private boolean isDiscovered;
private int x;
private int y;
private ArrayList<Node> neighbours = new ArrayList<Node>();
//for a star
private int hCost;
public Node(int x , int y){
this.x = x;
this.y = y;
this.predecessor = null;
this.isWall = false;
this.isDiscovered = false;
}
public Node(int x , int y,boolean isWall){
this.x = x;
this.y = y;
this.predecessor = null;
this.isWall = isWall;
this.isDiscovered = false;
}
//add a neighbor to this cell, and this cell as a neighbor to the other
public void addNeighbor(Node other) {
if (!this.neighbours.contains(other)) { // avoid duplicates
this.neighbours.add(other);
}
}
public Node getPredecessor() {
return predecessor;
}
public void setPredecessor(Node predecessor) {
this.predecessor = predecessor;
}
public boolean isWall() {
return isWall;
}
public void setWall(boolean isWall) {
this.isWall = isWall;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int gethCost() {
return hCost;
}
public void sethCost(int hCost) {
this.hCost = hCost;
}
public boolean isDiscovered() {
return isDiscovered;
}
public void setDiscovered(boolean isDiscovered) {
this.isDiscovered = isDiscovered;
}
public ArrayList<Node> getNeighboursList() {
return neighbours;
}
public String coordStr(){
return "("+this.x+","+this.y+")";
}
@Override
public boolean equals(Object other) {
if (!(other instanceof Node)) return false;
Node otherCell = (Node) other;
return (this.x == otherCell.x && this.y == otherCell.y);
}
@Override
public int hashCode() {
// random hash code method designed to be usually unique
return this.x + this.y * 256;
}
@Override
public String toString() {
String coords ="";
String parent = "";
String neighbour ="";
String discovered ="";
coords = "Node:"+coordStr();
if(getPredecessor() !=null)
parent = " Parent Node:"+getPredecessor().coordStr();
neighbour = " Neighbours:";
for(Node n: getNeighboursList()){
neighbour+= n.coordStr()+n.isDiscovered;
}
discovered = " isDiscovered():"+isDiscovered();
return coords+discovered+parent+neighbour;
}
}
为了解释我所说的跳转是什么意思，从我的调试消息中，您可以看到从 9,0 它将跳到 9,4，这不应该是这种情况，而是应该回到 9,3 并从那里继续到 9,4
推送节点：（9,3） 已发现（）：假 父节点：（8,3） 邻居：
弹出节点：（9,3） 已发现（）：假父节点：（8,3） 邻居：
生成邻居节点：（9,3） 已发现（）：真 父节点：（8,3）邻居：（9,4）假（8,3）真（9,2）假
推送节点：（9,4） 已发现（）：假 父节点：（9,3） 邻居：
推送节点：（9,2） 已发现（）：假父节点：（9,3） 邻居：
弹出节点：（9,2） isDisfound（）：false 父节点：（9,3） 邻居：
生成邻居节点：（9,2） 已发现（）：真 父节点：（9,3） 邻居：（9,3）真（9,1）假
推送节点：（9,1） 已发现（）：假父节点：（9,2） 邻居：
弹出节点：（9,1） 已发现（）：假父节点：（9,2） 邻居：
生成邻居节点：（9,1） 已发现（）：真 父节点：（9,2） 邻居：（9,2）真（9,0）假
推送节点：（9,0） 已发现（）：假 父节点：（9,1） 邻居：
弹出节点：（9,0） isDisfound（）：false 父节点：（9,1） 邻居：
生成邻居 节点：（9,0） 已发现（）：真 父节点：（9,1） 邻居：（9,1）真
弹出节点：（9,4） 是发现（）：假父节点：（9,3） 邻居：
生成邻居节点：（9,4） 已发现（）：真 父节点：（9,3） 邻居：（9,5）假（9,3）真
推送节点：（9,5） 已发现（）：假 父节点：（9,4） 邻居：
弹出节点：（9,5） 是发现（）：假父节点：（9,4） 邻居：
生成邻居节点：（9,5） 已发现（）：真 父节点：（9,4） 邻居：（9,6）假（9,4）真
推送节点：（9,6） 已发现（）：假父节点：（9,5） 邻居：
弹出节点：（9,6） isDisfound（）：false 父节点：（9,5） 邻居：
与其推送所有邻居/子节点，不如推送需要重新访问的节点，然后确定当该节点被弹出时要转到的下一个邻居/子节点。 通过将要访问的节点和要重新访问的节点保留在同一堆栈上，难怪它们在某些时候会感到困惑。