LeetCode的"The Maze II"问题：为什么这个解法会超过时间限制？

Question

我正在尝试解决 LeetCode 的 The Maze II 问题，

但我运行进入 'Time Limit Exceeded' 失败测试：

我的方法是将 Dijkstra 算法与最小优先级队列一起使用，类似于此处描述的内容 (https://leetcode.com/problems/the-maze-ii/discuss/351244/Python3-heapq-priority-queue-beats-100)，所以我有点困惑为什么我的解决方案会超时。

这是我尝试的解决方案：

import collections
import heapq
from typing import List, Tuple, Callable, Optional, Dict, Set


class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        return shortest_distance(
            maze=maze, start=tuple(start), destination=tuple(destination))


def shortest_distance(maze: List[List[int]], start: Tuple[int, int], destination: Tuple[int, int]) -> int:
    distances: Dict[Tuple[int, int], int] = collections.defaultdict(lambda: float('inf'))
    distances[start] = 0

    heap = [(0, start)]
    visited: Set[Tuple[int, int]] = {start}

    while heap:
        distance, coord = heapq.heappop(heap)
        visited.add(coord)

        if coord == destination:
            return distance

        for neighbor, d in get_neighbors(coord, maze):
            distances[neighbor] = min(distances[neighbor], distances[coord] + d)
            if neighbor not in visited:
                heapq.heappush(heap, (distances[neighbor], neighbor))

    return -1


DIRECTIONS: List[Callable[[Tuple[int, int]], Tuple[int, int]]] = [
    lambda coord: (coord[0] - 1, coord[1]),     # up
    lambda coord: (coord[0] + 1, coord[1]),     # down
    lambda coord: (coord[0], coord[1] - 1),     # left
    lambda coord: (coord[0], coord[1] + 1),     # right
]


def get_neighbors(coord: Tuple[int, int], maze: List[List[int]]) -> List[Tuple[Tuple[int, int], int]]:
    return [tup for tup in [
        get_neighbor(coord, maze, direction) for direction in DIRECTIONS]
        if tup[0] is not None]


def get_neighbor(
        coord: Tuple[int, int],
        maze: List[List[int]],
        direction: Callable[[Tuple[int, int]], Tuple[int, int]]) -> Tuple[Optional[Tuple[int, int]], int]:
    dist = -1
    prev, curr = None, coord
    while valid(curr, maze):
        prev, curr = curr, direction(curr)
        dist += 1
    return (prev, dist) if prev != coord else (None, -1)


def valid(coord: Tuple[int, int], maze: List[List[int]]) -> bool:
    return in_bounds(coord, maze) and maze[coord[0]][coord[1]] == 0


def in_bounds(coord: Tuple[int, int], maze: List[List[int]]) -> bool:
    return 0 <= coord[0] < len(maze) and 0 <= coord[1] < len(maze[0])

据我了解，将节点推入堆的时间复杂度为 O(log N)，并且由于图中的每个节点都会发生一次，因此我预计总时间复杂度为 O(N log N)，这似乎应该是一个 'efficient' 解决方案。

这个算法有没有我忽略的低效率？

Answer 1

您假设每个坐标元组只被推送到您的队列一次可能不正确。如果你在它被访问之前从两个不同的相邻位置到达它，你可能会推两次相同的位置。

错误的 ASCII 艺术图：

A B
B C D

如果您从 A 位置开始，您将在处理 A 时将它的两个邻居，即两个 B 位置添加到队列中。然后，在处理它们的共同邻居 C 之前，您将处理 both 个 B 节点。因为每个 B 位置都将其邻居添加到队列中，所以 C 将被添加两次。重复将继续，因为每次处理 C 时，您都会将其邻居 D 添加到堆中。

Dijkstra 算法的通用版本无法轻易避免将位置多次放入队列（因为到节点的新路径可能比您推送但尚未探索的路径短，并且没有在堆中查找和修改值的简单方法）。但是你可以防止一个重复的实例永久存在。只是拒绝处理任何已经访问过的职位：

visited: Set[Tuple[int, int]] = set()        # this set needs to start empty now

while heap:
    distance, coord = heapq.heappop(heap)
    if coord in visited:                     # skip repeat visits
        continue
    visited.add(coord)

我还注意到您的代码可能还有另一个问题（与性能无关）。他们以你生成邻居的方式，你只会在当前路径死胡同时改变方向。例如，我不认为你可以解决这个迷宫（你试图从 S 到 E，.s 是迷宫的开放空间：

S . . 
  E

您的邻居代码会告诉您 S 的唯一邻居是最右边的点，而该位置的唯一邻居是 S（您已经访问过）。你永远不会停在第一排的中间，这样你就可以改变方向下到出口。

LeetCode的"The Maze II"问题：为什么这个解法会超过时间限制？

LeetCode's "The Maze II" problem: why does this solution exceed the time limit?

python

algorithm

heap

dijkstra

shortest-path