Все уникальные пути BFS - самый эффективный способ отслеживания посещенных узлов? - PullRequest
Новая
       41

Все уникальные пути BFS - самый эффективный способ отслеживания посещенных узлов?

0 голосов
/ 12 января 2019

Я реализовал BFS в Python3, чтобы найти все уникальные пути от начальной координаты до конечной координаты в лабиринте, но я не уверен, что наиболее эффективный способ проверить, посещался ли узел в данной итерации.

Я попробовал как стандартную реализацию списка для отслеживания ранее пройденных узлов, так и реализацию OrderedDict. Мой вопрос в шаге "valid_neighbors" и проверке, существует ли уже сосед в пройденном пути.

При стандартной реализации списка поиск будет O (n), где n - длина пройденного пути. С реализацией OrderedDict, поиск должен быть примерно O (1) (по моему пониманию), но OrderedDict пересматривается на каждой итерации, что является дорогой операцией O (n). 

from collections import deque, OrderedDict, namedtuple
from typing import List

Coordinate = namedtuple('Coordinate', ('x', 'y'))

def bfs_matrix(maze: List[List[int]],
                      start: Coordinate,
                      end: Coordinate) -> List[List[Coordinate]]:
    """First path is the shortest."""
    queue: deque[OrderedDict[Coordinate, Coordinate]] = deque()

    queue.append(OrderedDict({start: start}))
    paths: List[OrderedDict[Coordinate, Coordinate]] = []

    while queue:
        path: OrderedDict[Coordinate, Coordinate] = queue.popleft()
        # path: List[Coordinate] = queue.popleft()
        # node: Coordinate = path[-1]
        node: Coordinate = next(reversed(path))
        # visited = set(path)
        if node == end:
            paths.append(path)
        else:
            neighbors = map(Coordinate,
                            (node.x-1, node.x+1, node.x, node.x),
                            (node.y, node.y, node.y-1, node.y+1))
            valid_neighbors = [C for C in neighbors if
                               0 <= C.x < len(maze) and 
                               0 <= C.y < len(maze[0]) and
                               C not in path]

            for neighbor in valid_neighbors:
                # new_path: List[Coordinate] = list(path)
                new_path: OrderedDict[Coordinate, Coordinate] = OrderedDict(path)
                # new_path.append(neighbor)
                new_path[neighbor] = neighbor
                queue.append(new_path)
    return paths

Я получаю все уникальные пути, используя этот алгоритм, и он, кажется, работает довольно быстро, но мне интересно, есть ли лучший способ проверить условие членства для недавно пройденных узлов.

...