深度优先搜索实现：算法只继续向右搜索

问题描述 投票：0回答：1

我有一个深度优先搜索练习。

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

这是我的代码：

Node.java

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

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

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

搜索算法.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);
    }
}

我在

{0,0}
函数中将初始位置设置为
main
。

问题是，当我运行程序时，我得到以下输出：

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
。为什么算法不断访问相同的节点？

java algorithm recursion depth-first-search
1个回答
0
投票

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

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

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);
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.