首页 文章

逃离监狱 - 找到最短的路

提问于
浏览 次
-1

我已经完成了一项任务，我必须逃离迷宫 . 目标是找到最短的路 . 我做了一些研究，似乎有两种解决问题的策略：Depth-first search和Breadth-first search，其中第一个从根开始（迷宫中的起点）并在回溯之前尽可能沿着每个分支进行探索，第二个开始在根节点处检查所有相邻节点 . 然后，对于这些邻居节点中的每一个，它检查它们未被访问的邻居节点，等等 .

我已经实现了两种算法（非递归实现），直到找到结束为止：

/**
 * A non-recursive implementation of DFS
 * @param maze
 */
void solveUsingDepthFirst(IMaze maze) {
    Stack<IMazePosition> candidates = new Stack<IMazePosition>();
    //insert start position
    candidates.push(maze.getStartPosition());

    IMazePosition currentPosition;
    IMazePosition nextPosition;
    while (!candidates.empty()) {
        currentPosition = candidates.pop();

        if (maze.isMazeSolved(currentPosition)) break;

        //mark the current position
        maze.markPosition(currentPosition, maze.getPathMark());
      // maze.printMaze();
        // Check for possible ways to go
        nextPosition = currentPosition.north();
        if (maze.canMove(nextPosition)) candidates.push(nextPosition);
        nextPosition = currentPosition.east();
        if (maze.canMove(nextPosition)) candidates.push(nextPosition);
        nextPosition = currentPosition.south();
        if (maze.canMove(nextPosition)) candidates.push(nextPosition);
        nextPosition = currentPosition.west();
        if (maze.canMove(nextPosition)) candidates.push(nextPosition);
    }

    System.out.println(!candidates.empty() ? "Done" : "Sorry, could not do it");
    maze.printMaze();
}

/**
 * A non-recursive implementation of BFS
 * @param maze
 */
void solveUsingBreadthFirst(IMaze maze) {
    LinkedList<IMazePosition> candidates = new LinkedList<IMazePosition>();
    //insert start position
    candidates.add(maze.getStartPosition());

    IMazePosition currentPosition;
    IMazePosition nextPosition;
    while (!candidates.isEmpty()) {
        currentPosition = candidates.removeFirst();

        if (maze.isMazeSolved(currentPosition)) break;

        //markPosition the current position
        maze.markPosition(currentPosition, maze.getPathMark());
     //   maze.printMaze();

        // Check for possible ways to go
        nextPosition = currentPosition.north();
        if (maze.canMove(nextPosition)) candidates.add(nextPosition);
        nextPosition = currentPosition.east();
        if (maze.canMove(nextPosition)) candidates.add(nextPosition);
        nextPosition = currentPosition.south();
        if (maze.canMove(nextPosition)) candidates.add(nextPosition);
        nextPosition = currentPosition.west();
        if (maze.canMove(nextPosition)) candidates.add(nextPosition);
    }

    System.out.println(!candidates.isEmpty() ? "Done" : "Sorry, could not do it");
    maze.printMaze();
}

Map （或迷宫）表示为 char[][] . MazePosition是坐标的表示：

public MazePosition(int x, int y) {
    this.x = x;
    this.y = y;
}

现在有了这个代码，我有了所有可能的路径，从头到尾，我能够找到，直到我第一次找到结束 - 是否公平地假设最短的路径在他们中间？鉴于我有可能的路径，我如何找到最短的路径？并且，路径生成的代码是否有任何好处？我可以优化我已经拥有的任何例程 .

另外，据我所知，迷宫中没有“洞”，这意味着我总能坚持到墙上 .

java algorithm graph graph-algorithm

2 回答

  • 1

    如果你有所有可能的路径，我愿意打赌最短的是其中之一 .

    正如Blender所提到的，在广泛的第一次搜索中，发现的第一个解决方案将属于最佳解决方案集（最短路径） .

    如何找出候选人的路径有多长？将pathLength字段添加到 MazePosition 类，每次添加候选位置时都将其递增 . 当你到达日光时，该字段会告诉你你已经走了多少步 .

    没有出口的迷宫怎么样？也许你应该跟踪你去过的地方 .

    为了回答有关"goodness"和"optimization"的问题，我们需要知道您正在使用哪些约束 . 慢得多慢？这些迷宫有多大？ Premature optimization is the root of all evil.

    回复于
  • 1

    除非只有少量可能的路线（并且您无法确认它是最短路线），否则深度优先不太可能找到最短路线 .

    宽度优先将始终首先找到“a”最短路线，假设您在每个步骤的每个节点处增加相同的距离（可能存在多条相等长度的路径） .

    如果你在没有更多步骤的情况下进行迭代，那么迷宫就不可能了 .

    记录实际路线的最简单方法可能是用距离远距离“标记”每个位置，然后当你到达出口时，你可以反复跟踪路线（从完成到开始），反复步行到相邻的位置 . 到目前为止记录的距离较小，直到你回到起点（当然，记录路线） .

    根据迷宫的维度，如果您已经知道出口的位置，您可以通过从开始点和结束点开始做广度直到搜索重合来减少查找路径所需的步骤数（如果不被认为是“作弊”） .

    回复于

相关问题