Java 问题算法中的深度优先搜索实现始终只向右搜索

Question

我意识到我在之前的问题中没有正确表达自己，所以我决定尽可能更好地写下这个问题。

这不是一个重复的问题，这是我尽我所能表达自己。我有一个深度优先搜索算法：

本练习的目标是找到一条从迷宫起点到终点的有效路径。

搜索算法.java

import java.util.Random;
import java.lang.System;

public class SearchAlgorithm

{
protected int gridSize;

protected int gridLength;

protected Node[][] grid;

public SearchAlgorithm(int gridSize)
{
    int gridLength  = (int) Math.sqrt(gridSize);

    this.gridSize = gridSize;

    this.gridLength = gridLength;

    Node[][]arr = new Node[gridLength][gridLength];

    Random r = new Random();

    for(int i=0;i<gridSize;i++)
    {
        Node n;

        if(i==0)
        {
         n= new Node(i,0,false);

         arr[i][i] = n;
        }
        else if(i==gridSize-1)
        {
            n = new Node(i,0,true);

            arr[gridLength-1][gridLength-1] = n;
        }
        else
        {
            int x = i%gridLength;

            int y = i/gridLength;

            n = new Node(i,r.nextInt(2),false);

            arr[x][y] = n;

        }
    }

    this.grid = arr;

}
public void print()
{
    for(int i=0;i<gridLength;i++)
    {
       for(int j=0;j<gridLength;j++)
       {
         System.out.print("Position:"+grid[j][i].getPosition()+" Type:"+grid[j][i].getType()+" ");

       }

       System.out.println();

    }

}

}

grid

是

Node

类的二维数组：它有2个坐标x和y。X由Node.position%i找到，Y由Node.position/i找到

DeepFirstSearch.java

import java.lang.System;

public class DeepFirstSearch extends SearchAlgorithm {

private  int[] position;


public DeepFirstSearch(int gridSize) {
    super(gridSize);

    position = new int[2];

    position[0]=0;

    position[1]=0;
}
public int calc(int[]position)
{
    System.out.println(grid[position[0]][position[1]].getPosition());

    if(grid[position[0]][position[1]].getType()==1)
    {
       System.out.println("Path been blocked!Exit status:"+1);

       return 1;

    }
    else if(grid[position[0]][position[1]].getIsExit())
    {
        System.out.println("Path been found");

        return 0;
    }

    else
    {
        if(position[0]<gridLength-1)
        {
           position[0]++;

           calc(position);
        }
        if(position[0]>0)
        {
            position[0]--;

            calc(position);
        }
        if(position[1]<gridLength-1)
        {
            position[1]++;

            calc(position);
        }
        if(position[1]>0)
        {
            position[1]--;

            calc(position);
        }
    }

 return -1;
 }
 }

int[]position

存储当前

Node

的位置。如果我们用

Node

击中

Node.getType()==1

，则路径无效。带有

Node

的

getIsExit()==true

是所需的目的地（它只有1）在我的例子中）。

Main.java

public class Main {
public static void main(String[] args) {

    DeepFirstSearch sch = new DeepFirstSearch(9);

    sch.print();

    int[]pos = {0,0};

    sch.calc(pos);
}
}

问题是，当我运行程序时，我得到这个：

Position:0 Type:0 Position:1 Type:0 Position:2 Type:1 
Position:3 Type:1 Position:4 Type:1 Position:5 Type:1 
Position:6 Type:0 Position:7 Type:1 Position:8 Type:0 
0
1
2
Path been blocked!Exit status:1
1
2
Path been blocked!Exit status:1
1
2
Path been blocked!Exit status:1
1
2
Path been blocked!Exit status:1
1
2

依此类推，直到

StackOverflowException

被抛出。是的，我在main中将初始位置设置为{0,0}。

Answer 1

您还没有实现“访问”的概念。您访问过的位置不应再次访问。这是搜索算法的基本原理。当您准备好查看某个节点的邻居时，该节点就被称为“已访问”。当您对邻居进行递归调用时，该邻居就会被访问。如果发现该邻居已经被访问过，则表明该邻居位于您已经走过的路径上，因此不应再次访问它。如果你愿意，你会循环运行，这就是你遇到的问题。

所以你需要在某处保持已访问状态。有很多方法可以做到这一点。一是给

Node

添加布尔字段：

public class Node
{
    private int position;
    private int type;
    private boolean IsExit;
    private boolean isVisited; // See also getter & setter

    public Node(int position,int type,boolean IsExit)
    {
        this.position = position;
        this.type = type;
        this.IsExit = IsExit;
        this.isVisited = false;
    }

    public int getPosition()
    {
        return position;
    }
    
    public int getType()
    {
        return type;
    }
    
    public boolean getIsExit()
    {
        return IsExit;
    }

    public void setIsExit(boolean b)
    {
        IsExit = b;
    }

    public boolean getIsVisited() {
        return isVisited;
    }
    
    public void setIsVisited(boolean b) {
        isVisited = b;
    }
}

我还建议让

calc

返回

boolean

而不是

int

，因为这就是你在那里所做的：要么搜索成功，要么不成功。

如果您不将

position

作为两个数组传递，而是传递两个单独的

int

，一个用于

row

，一个用于

col

，也会更容易。此外，

position

不应该是一个字段；它只是随每次递归调用一起传递的本地信息。

这是更新的

calc

方法：

import java.lang.System;

class DeepFirstSearch extends SearchAlgorithm {
    public DeepFirstSearch(int gridSize) {
        super(gridSize);
    }
        
    public boolean calc(int row, int col)
    {
        // Perform all validity checks here, and test node was not yet visited
        if (   row >= gridLength
            || row < 0
            || col >= gridLength
            || col < 0
            || grid[row][col].getIsVisited()
        ) {
            return false; // Target was not found here
        }
        Node node = grid[row][col];
        node.setIsVisited(true); // Mark as visited
        System.out.println(node.getPosition());
        if (node.getType() == 1)
        {
            System.out.println("Path been blocked!Exit status: false");
            return false; // Target was not found here
        }
        else if(node.getIsExit())
        {
            System.out.println("Path been found");
            return true; // Target found!
        }
        else
        {
            // Use short circuit evaluation: as soon as one of the calls 
            //   returns true, no further calls will be made, and the return
            //   value will be true if and only when that happens.
            return calc(row + 1, col) || calc(row - 1, col) 
                || calc(row, col + 1) || calc(row, col - 1); 
        }
    }
}

初始调用应该是：

class Main {
    public static void main(String[] args) {
        DeepFirstSearch sch = new DeepFirstSearch(9);
        sch.print();
        sch.calc(0, 0);
    }
}