时间戳

首页 > 解决方案 > 深度优先搜索路径

java - 深度优先搜索路径

问题描述

我有一个问题需要我实现一个算法来寻找从一个角色到另一个角色的路径，沿途有障碍物。

我知道有很多高级寻路算法（A*、BFS、DFS、dijkstra ......）。然而，经过大量的研究和尝试，我正在努力在我的代码中实现所有这些概念，而且我认为我不需要实现所有这些高级算法。

“最短”路径不是必需的，我所需要的只是一条可以通过避免移动到障碍物来将我的角色引导到另一个角色的路径。谁能给我一个想法（也许一些算法比回溯更好）或有用的网站（类似的例子）这个问题？

任何帮助将非常感激

标签： javapath-finding

解决方案

由于我不知道您的“网格”是如何描述的，以及“单元格”是什么，我假设网格是矩形的，单元格仅映射其上的对象，而不是空白空间。

我建议您char[][] array = new char[rows][columns];使用某个值对其进行初始化（或字符）并进行迭代Cells，以某种有意义的方式填充 2D 数组，例如G用于目标、#障碍等。然后您从 Goal 启动 DFS 以查找 Start。

您需要在某处存储正确的路径，因此您也需要一个ArrayList list;变量。由于它是一个列表，因此您可以使用 向其中添加项目list.add(item);，这很方便。

非最优路径：DFS

DFS 是一个非常基本的递归算法，在您的情况下，它将如下所示：

bool DFS(list, array, row, column):
    if(array[row][column] == '#' or
       array[row][column] == 'v') return False; # Obstacle or visited, ignore it
    if( ...               == 'S') return True;  # It's the Start, path found

    array[row][column] = 'v'; # mark as visited, nothing interesting.
    # If you want the shortest path, you're supposed to put here the distance from goal,
    #that you would pass on and increment as additional argument of DFS 

    #Check for edge cases, or initialize array to be bigger and place obstacles on edge#
    if( DFS(list, array, row-1, column) ){ # If DFS fount a path to Start from cell above
        list.add("Move Up");               # Then you add a direction to go below to the list
        return True;                       # And then tell the previous DFS, that the path was found
    }
    if()
    if()
    if()
    # And then you add the checks for the other directions in a similar manner

    return False; # You didn't find anything anywhere
}

这不是代码，但它应该足以让你从那里完成你的任务。

它可能会找到这样的路径：

...→→→→↓
...↑.↓←↓
...S.F↑↓
......↑↓
......↑←

但是在有很多障碍物或只有一条正确路径的网格中，它会形成更合理的路径。你也可以通过选择你尝试方向的顺序来改进它，所以它总是首先尝试朝着目标前进，但这很痛苦。

最佳路径：增强 DFS

为了找到最短路径，人们通常会提到 A*，但我读过它，它不像我记得的那样，它只是不必要地复杂，所以我将解释一个扩展的 DFS。与 A* 或 BFS 相比，找到答案需要更长的时间，但对于大小合理的网格，它并不明显。

该算法的思想是将整个网格与到的距离进行映射Goal，然后随着距离的减小从起点走到目标。

首先，您需要使用int[][] array而不是char以前的情况。那是因为您需要存储距离，其中 char 在某种程度上也可以，而且还需要存储网格中的非距离标记，例如障碍物等。

该算法的思想是您调用DFS(array, row, col, distance)，其中distance计算为Cell调用 DFS 的距离增加 1。然后在下一个单元格中的 DFS 检查它通过的距离是否小于其当前距离，如果是，则有是找到该单元格的较短路径，您也需要重新计算其所有邻居。否则新路径更长，您可以忽略它。通过递归调用 DFS，您将逐渐映射整个迷宫。

之后，您将调用另一个函数FindPath(list, array, row, col)，该函数将检查它开始的单元格，并向单元格添加一个方向neighbor.distance == (this.distance - 1)，list然后调用FindPath该邻居，直到距离为 0，此时它就是目标。

它应该看起来像这样：

main()
{
    # initialize grid with Integer.MAX_VALUE or just a big enough number
    # for Cell in Cells -> put obstacles on Grid as -1,
    #                      find the Start and Goal and record them somewhere
    # DFS_plus(array, Goal, 0);
    # FindPath(list, array, Start);
    # Done
}


void DFS_plus(array, row, column, distance):
    if(array[row][col] <= distance) return; # There already exists a shorter path there
    # or it's an obstacle, we store obstacles as -1. 
    # It's smaller than any possible path and thus blocks further search

    array[row][column] = distance; # update distance.
    # If this happened its neighbors will need to be updated too.

    #Check for edge cases, or initialize array to be bigger and place obstacles on edge#

    DFS_plus(array, row-1, column, distance+1); # You just map everything, no returns expected
    DFS_plus(); # For all 4 directions
    DFS_plus();
    DFS_plus();
}

FindPath(list, array, row, col){
    if(array[row][col] == 0) return; # It's the Goal

    if(array[row-1][col] == (array[row][col] - 1)){ # Check if Cell above is 1 closer to Goal
        list.add("MoveUp");                           # Add direction
        FindPath(list, array, row-1, col);          # Look for next direction
        return; # You don't need to check other directions as path is guaranteed
    }
    if(){}; # Check other directions if Up wasn't the one
    if(){};
    if(){};
}

它并不复杂，但它为您提供了最短的路径。这不是找到最短路径的最快方法，但它与任何递归算法一样相对简单。

推荐阅读