Блог

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

Спасибо за ваше терпение и понимание, ниже приведен код:

 map = {(0, 0): [(1, 0), (0, 1)],
   (0, 1): [(1, 1), (0, 2)],
   (0, 2): [(1, 2), (0, 3)],
   (0, 3): [(1, 3), (0, 4)],
   (0, 4): [(1, 4), (0, 5)],
   (0, 5): [(1, 5)],
   (1, 0): [(2, 0), (1, 1)],
   (1, 1): [(2, 1), (1, 2)],
   (1, 2): [(2, 2), (1, 3)],
   (1, 3): [(2, 3), (1, 4)],
   (1, 4): [(2, 4), (1, 5)],
   (1, 5): [(2, 5)],
   (2, 0): [(3, 0), (2, 1)],
   (2, 1): [(3, 1), (2, 2)],
   (2, 2): [(3, 2), (2, 3)],
   (2, 3): [(3, 3), (2, 4)],
   (2, 4): [(3, 4), (2, 5)],
   (2, 5): [(3, 5)],
   (3, 0): [(4, 0), (3, 1)],
   (3, 1): [(4, 1), (3, 2)],
   (3, 2): [(4, 2), (3, 3)],
   (3, 3): [(4, 3), (3, 4)],
   (3, 4): [(4, 4), (3, 5)],
   (3, 5): [(4, 5)],
   (4, 0): [(5, 0), (4, 1)],
   (4, 1): [(5, 1), (4, 2)],
   (4, 2): [(5, 2), (4, 3)],
   (4, 3): [(5, 3), (4, 4)],
   (4, 4): [(5, 4), (4, 5)],
   (4, 5): [(5, 5)],
   (5, 0): [(5, 1)],
   (5, 1): [(5, 2)],
   (5, 2): [(5, 3)],
   (5, 3): [(5, 4)],
   (5, 4): [(5, 5)],
   (5, 5): []}

visited = []
path = []
routes = []


def goal_test(node):
    if node == (5, 5):
        return True
    else:
        return False


found = False


def dfs(visited, graph, node):
    global routes
    visited = visited   [node]
    if goal_test(node):
        routes = routes   [visited]
    else:
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)


dfs(visited, map, (0, 0))
print(len(routes))
for route in routes:
    print(route)
  

В этой реализации используется несколько плохих практик:

• map это собственная функция Python, поэтому создавать переменную с таким именем — плохая идея.

• visited не нужно инициализировать в глобальной области: вызывающий объект не заинтересован в этом, поскольку он играет роль только в самом алгоритме DFS

• routes также не нужно инициализировать пустой список, и это плохо, что dfs изменяет эту глобальную переменную. Вместо dfs этого следует вернуть эту информацию вызывающей стороне. Это делает один dfs вызов автономным, поскольку он возвращает возможные маршруты от текущего узла к целевому. Вызывающий абонент должен расширить маршруты в этой возвращаемой коллекции дополнительным узлом.

• Тело goal_test должно быть записано как return node == (5, 5) . Это if ... else просто преобразование логического значения в то же логическое значение.

• Функция goal_test кажется излишней, когда вы можете просто передать аргумент dfs функции, представляющей целевой узел. Это также делает его более универсальным, поскольку вам не нужно жестко кодировать целевое местоположение внутри функции.

• path и found инициализируются, но никогда не используются.

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

• dfs будет посещать одну и ту же ячейку несколько раз, поскольку ее можно найти по разным путям (например, например (2,2) ), и поэтому оттуда он будет выполнять тот же поиск в DFS, который он уже выполнял раньше. Это можно было бы сделать немного более эффективным, сохранив результат, полученный при предыдущем посещении этой ячейки, т. Е. Мы могли бы использовать запоминание. Выигрыш невелик, так как большая часть времени тратится на создание и копирование путей. Выигрыш (от использования запоминания) был бы значительным, если бы функция только подсчитывала количество путей, а не строила их.

Вот реализация, которая касается вышеупомянутых моментов. Он использует функцию-оболочку, чтобы скрыть использование запоминания для вызывающего абонента и уменьшить количество аргументов, которые необходимо передать dfs :

 def search(graph, source, target):
    # Use memoization to avoid repetitive DFS from same node, 
    #  Also used to mark a node as visited, to avoid runnning in cycles
    memo = dict()  # has routes that were already collected

    def dfs(node):
        if node not in memo:  # not been here before
            if node == target:
                memo[node] = [[target]]
            else:
                # Mark with None that this node is on the current path
                #   ...avoiding infinite recursion on a cycle
                memo[node] = None  # temporary value while not yet back from recursion
                memo[node] = [
                    [node]   route 
                        for neighbour in graph[node]
                            for route in dfs(neighbour) 
                                if route
                ]
        return memo[node]

    return dfs(source)

graph = {(0, 0): [(1, 0), (0, 1)],
    # ...etc ... 
}

routes = search(graph, (0, 0), (5, 5))

print(len(routes))
for route in routes:
    print(route)