迷宫寻路实现（BFS）没有给出正确的路径

Question

我正在尝试获得带球的迷宫的最短路径：球一直滚动直到撞到墙上。我使用 Dijkstra 算法使用 heapq 作为优先级队列。但是，结果我得到了一条非最佳路径。

这是我的示例输入代码：

maze = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0],
        [0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0],
        [0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0],
        [0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1],
        [1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
        [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0],
        [0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0],
        [0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
        [0, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

start = (0, 0)
end = (22, 22)

def shortestDistance(maze: List[List[int]], start: List[int], destination: List[int]):
    start, destination = tuple(start), tuple(destination)
    row, col = len(maze), len(maze[0])
    moves = [(-1, 0), (0, 1), (0, -1), (1, 0)]
    dstr = ['u', 'r', 'l', 'd']

    class Point:
        def __init__(self, distance, coordinates, directions):
            self.distance = distance
            self.coordinates = coordinates
            self.directions = directions

        def __eq__(self, p):
            if self.distance == p.distance:
                return self.__lt__(self, p)

            return self.distance - p.distance

        def __lt__(self, p):
            return len(self.directions) - len(p.directions)


    heap = [(Point(0, start, ""))]
    visited = set()
    while heap:
        point = heapq.heappop(heap)
        dist = point.distance
        node = point.coordinates
        directions = point.directions

        if node in visited: continue
        if node == destination:
            return directions

        visited.add(node)

        for idx, move in enumerate(moves):
            dx, dy = move
            newX = node[0]
            newY = node[1]
            distance = dist
            newDirections = directions
            while 0 <= newX + dx < row and 0 <= newY + dy < col and maze[newX + dx][newY + dy] == 0:
                newX += dx
                newY += dy
                distance += 1
                if (newX, newY) == destination:
                    break

            if (newX, newY) not in visited:
                heapq.heappush(heap, Point(distance, (newX, newY), newDirections + dstr[idx]))

    return "Impossible"


path = shortestDistance(maze, start, end)
print(path)

思路是比较距离，如果相等，则选择方向变化较少的路径。

我目前得到 rdrludlrdrudludldldr（即右-下-右-左-...）作为输出，但在索引 2 处找到的序列“rl”没有意义：“右" 后不应跟"左"，"上" 后也不应跟"下"，反之亦然。这样的顺序显然不是最佳的，因为可以省略这两个动作中的第一个动作以使球在同一位置并移动更短的距离。

这个迷宫的预期输出是drururdrdrurdrd。

为什么我没有得到最短路径？

Answer 1

问题是 __lt__ 函数没有做它应该做的事情。

它应该 return 一个布尔值，当 self 被认为小于 p 时为真。由于您目前 return 一个整数结果，通常是非零的，您会遇到这样的情况，即一对 (p, q) 点同时具有 p < q 和 q < p 为真...这导致不稳定的行为。

你可以这样定义它：

def __lt__(self, p):
    return ((self.distance, len(self.directions), self.directions) < 
          < (p.distance, len(p.directions), p.directions))

通过此更改，returned 路径为

rdrdldldrdr

简化

您可以使用命名元组，而不是创建 class Point，这会使一切变得更容易（也更快）。您只需要更改“属性”的顺序，以便这些点以所需的方式进行比较，即 directions 应该在 coordinates 之前并且方向字符串的长度应该有自己的属性:

from collections import namedtuple

# change order of properties so comparison works as intended
Point = namedtuple("Point", "distance, length, directions, coordinates")

然后在调用 Point:

的地方进行适当的更改

heap = [Point(0, 0, "", start)]
# ...
heapq.heappush(heap, Point(distance, len(newDirections) + 1, newDirections + dstr[idx], (newX, newY)))

迷宫寻路实现（BFS）没有给出正确的路径

Maze pathfinding implementation (BFS) not giving correct path

python

algorithm

maze

breadth-first-search

path-finding

简化