Python: сохранение ранее посещенных координат двоичного массива для AStar

Question

Я создаю алгоритм A* в python и пытаюсь выяснить, как сохранить местоположения, которые мой алгоритм ранее посещал, в двоичном массиве, таком как приведенный ниже.

nmap = np.array([
    [0,0,0,0],
    [1,1,1,0],
    [0,0,0,0],
    [1,0,1,1],
    [0,0,0,0]
    ])

Единственный способ, которым я могу придумать, - сохранить местоположение ранее посещенных двоичных чисел через координаты. Например,

nmap[0][0]

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

Answer 1

Самый очевидный выбор - это Set, Это дает амортизированную производительность поиска O(1). Вы можете добавить посещенные узлы в visitedSet используя add метод, и вы можете проверить, есть ли узел в вашем visitedSet с использованием in оператор:

>>> from sets import Set
>>> visitedSet = Set()
>>> visitedSet.add( (1,2) )
>>> print( (0,0) in visitedSet )
False
>>> print( (1,2) in visitedSet)
True

Answer 2

Для этого вы можете легко сохранить индексы в координатах в списке кортежей:

visited = [(0,0), (2,0)...]