深度优先搜索二维阵列 [英] Depth First Search on 2-D array

问题描述

我正在尝试通过创建一个通过迷宫（2d数组）导航我的食人魔的程序来学习DFS。这类似于每日编程挑战，但我只使用1x1食人魔。

I am trying to learn DFS by creating a program that navigates my ogre through a maze (2d array).This is similar to a dailyprogramming challenge, but I am doing it with just a 1x1 ogre.

我的迷宫：

static int[][] maze = { 
{2,1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{1,0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1,0,1},
{1,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0,3}};

其中2是我的英雄（0,0），3是我的目标（9,9）， 1s是障碍物，0s是可移动的空间。

Where 2 is my hero (0,0), 3 is my goal (9,9), 1s are obstacles, and 0s are traverseable space.

由于我是新手，我怀疑它是否需要，但不适用包括整个程序，以便于复制和排除故障。

Since I am new to this, I doubt it will be needed, but ill include the whole program for easy duplication and troubleshooting.

import java.awt.Point;
import java.util.ArrayList;


public class OgrePath {

    static int[][] maze = { 
        {2,1,0,0,0,0,0,0,0,0},
        {0,0,1,0,0,0,0,0,0,0},
        {1,0,0,0,0,1,0,1,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,1,1,0,0,0,0,0,0},
        {0,0,1,0,0,0,0,1,0,1},
        {1,1,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,1,1,0,0,0},
        {0,0,0,0,0,1,0,0,0,3}};
public static boolean[][] visited = new boolean[maze.length][maze[0].length];
static ArrayList<Point> neighbors = new ArrayList<Point>();

public static void main(String[] args) {
    OgrePath OP = new OgrePath();
    for (int i=0;i<maze.length;i++){
        for (int j=0;j<maze[i].length;j++){
            visited[j][i] = false;
        }
    }
    visited[getOgre(maze).x][getOgre(maze).y] = true;
    System.out.println("Ogre: " + getOgre(maze));
    dfs(maze, getOgre(maze));
}

public static boolean dfs(int[][] maze, Point p){
    neighbors = getNeighbors(maze,p);
    if (maze[p.x][p.y] == 3){
        System.out.println("FOUND IT");
        return true;
    }
    if (neighbors.isEmpty()){
        return false;
    }
    for (int i=0;i<neighbors.size();i++){
        System.out.println("Nieghbors: " + neighbors);
        System.out.println(i + "(" + p.x + "," + p.y + ")");
        visited[neighbors.get(i).x][neighbors.get(i).y] = true;
        dfs(maze, neighbors.get(i));
    }
    return false;
}

public static ArrayList<Point> getNeighbors(int[][] maze, Point p){
    ArrayList<Point> neighbors = new ArrayList<Point>();
    Point left = new Point();
    Point right = new Point();
    Point down = new Point();
    Point up = new Point();
    down.x = p.x - 1;
    down.y = p.y;
    if (valid(maze,down)) neighbors.add(down);
    up.x = p.x + 1;
    up.y = p.y;
    if (valid(maze,up)) neighbors.add(up);
    left.x = p.x;
    left.y = p.y - 1;
    if (valid(maze,left)) neighbors.add(left);
    right.x = p.x;
    right.y = p.y + 1;
    if (valid(maze,right)) neighbors.add(right);
    return neighbors;
}

public static boolean valid(int[][] maze, Point p){
    if (inMaze(maze,p) && canGo(maze,p) && visited[p.x][p.y] == false) return true;
    else return false;
}

public static boolean inMaze(int[][] maze, Point p){
    if (p.x < (maze[0].length - 1) && p.x > -1 && p.y < (maze.length - 1) && p.y > -1){
        return true;
    } else return false;
}

public static boolean canGo(int[][] maze, Point p){
    if (maze[p.x][p.y] != 1 && maze[p.x][p.y] != 4) return true;
    else return false;  
}

public static Point getOgre(int[][] maze){
    Point ogre = new Point();
    for (int i=0;i<maze.length;i++){
        for (int j=0;j<maze[i].length;j++){
            if (maze[i][j] == 2){
                ogre.x = j;
                ogre.y = i;
            }
        }
    }
    return ogre;
}
}

我希望能够递归调用DFS，但是关于我编写它的方式的一些事情使得程序在探索了一条可能的行并且失败之后就停止了。

I want to be able to recursively call DFS, but something about the way I wrote it makes the program stop after it has explored 1 possible line and failed.

推荐答案

好的，所以那里我看到的一些问题会阻止你的代码正常工作，所以让我们一次看一下。

Okay, so there a few issues I see that would prevent your code from working properly so lets look at them one at a time.

首先，你的dfs函数不会遍历'for '循环，因为它会立即返回。尝试更改

First, you dfs function will not iterate through the 'for' loop because it will immediately return. Try changing

dfs(maze, neighbors.get(i));

到

if(dfs(maze, neighbors.get(i))){
    return true;
}

这解决了部分问题，只搜索单个路径。

This fixes part of your issue with only searching a single path.

第二个问题是你的邻居。当您的dfs完全探索路径时，它应该返回一步并检查所有邻居。您只有一个顶级邻居变量，因此当您的分支以零邻居终止时，它认为所有早期节点都有零邻居。

The second issue is with your neighbors. When your dfs does fully explore a path, it should go back a step and check all neighbors. You only have a single top-level neighbors variable, so when your branch terminates with zero neighbors, it thinks all earlier nodes have zero neighbors.

删除静态邻居变量

static ArrayList<Point> neighbors = new ArrayList<Point>();

并在getNeighbors中放置一个非静态版本

And put a non-static version in getNeighbors

ArrayList<Point> neighbors = new ArrayList<Point>();

这几乎完全修复了搜索，但对于你的迷宫，你仍然无法找到结束。

This almost completely fixes the search, but for your maze, you will still not find the end.

您的inMaze函数检查边界不正确。您正在检查x或y是否小于长度减去1。您只需要使用'小于'来检查边界。

Your inMaze function is checking bounds incorrectly. You were checking for if x or y was less than length minus one. You only need to use 'less than' for checking the boundary.

if (p.x < maze[0].length && p.x > -1 && p.y < maze.length && p.y > -1)

这篇关于深度优先搜索二维阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！