Реализация поиска на графе Python

Структуры данных

Первое, что нужно сделать, это выбрать способ представления данного графа в сценарии на языке Python. Одно из решений заключается в использовании встроенных типов данных и функций поиска. Сценарий, представленный в примере 18.16, создает контрольный граф просто как словарь: каждое состояние является ключом словаря со списком ключей узлов, в которые можно из него попасть (то есть его дуг). В этом файле также определена функция, с помощью которой мы выполним несколько поисков на графе.

Пример 18.16. PP4E\Dstruct\Classics\gtestfunc.py

"представление графа в виде словаря"

[‘B‘, ‘E‘, ‘G‘],

[‘C‘], # направленный циклический граф

[‘D‘, ‘E‘], # хранится в виде словаря

[‘F‘], # ‘ключ’ ведет к [узлам]

[‘C’, ‘F’, ‘G’],

[ ], [‘A’] }

def tests(searcher): # функция поиска

print(searcher(‘E’, ‘D’, Graph)) # отыскивает все пути от ‘E’ до ‘D’ for x in [‘AG’, ‘GF’, ‘BA’, ‘DA’]:

print(x, searcher(x[0], x[1], Graph))

Теперь напишем два модуля, реализующие фактические алгоритмы поиска. Они не зависят от формы графа, в котором производится поиск (он передается им в качестве аргумента). Первая функция поиска, представленная в примере 18.17, для обхода графа использует ре кур сию.

Пример 18.17. PP4E\Dstruct\Classics\gsearch1.py

"находит все пути на графе из начальной точки в конечную"

def search(start, goal, graph):

solns = []

generate([start], goal, solns, graph) # выборка всех путей solns.sort(key=lambda x: len(x)) # сортировка по длине пути return solns

Вторая функция поиска, представленная в примере 18.18, использует рассматривавшуюся выше реализацию сте ка путей, которые должны быть продолжены, на основе дерева кортежей.

Пример 18.18. PP4E\Dstruct\Classics\gsearch2.py

"поиск на графе, вместо рекурсии использует стек путей"

def search(start, goal, graph):

solns = generate(([start], []), goal, graph)

solns.sort(key=lambda x: len(x))

return solns

else: for arc in graph[state]: # добавить все продолжения

if arc not in front:

paths = (front + [arc]), paths return solns

if __name__ == ‘__main__’: import gtestfunc gtestfunc.tests(search)

Обе функции запоминают посещавшиеся узлы, чтобы избежать циклов. Если продолжение оказывается в текущем пути, то возникает цикл. Полученный список решений сортируется по увеличению длины с помощью метода списка sort и его необязательного аргумента key, выполняющего преобразования исходных значений. Чтобы проверить модули поиска, просто запустите их; программный код самотестирования вызывает подготовленный тест поиска в модуле gtestfunc:

C:\…\PP4E\Dstruct\Classics> python gsearch1.py

[[‘E’, ‘C’, ‘D’], [‘E’, ‘G’, ‘A’, ‘B’, ‘C’, ‘D’]]

AG [[‘A’, ‘G’], [‘A’, ‘E’, ‘G’], [‘A’, ‘B’, ‘C’, ‘E’, ‘G’]]

GF [[‘G’, ‘A’, ‘E’, ‘F’], [‘G’, ‘A’, ‘B’, ‘C’, ‘D’, ‘F’],

[‘G’, ‘A’, ‘B’, ‘C’, ‘E’, ‘F’], [‘G’, ‘A’, ‘E’, ‘C’, ‘D’, ‘F’]]

BA [[‘B’, ‘C’, ‘E’, ‘G’, ‘A’]]

DA []

C:\…\PP4E\Dstruct\Classics> python gsearch2.py

[[‘E’, ‘C’, ‘D’], [‘E’, ‘G’, ‘A’, ‘B’, ‘C’, ‘D’]]

AG [[‘A’, ‘G’], [‘A’, ‘E’, ‘G’], [‘A’, ‘B’, ‘C’, ‘E’, ‘G’]]

GF [[‘G’, ‘A’, ‘E’, ‘F’], [‘G’, ‘A’, ‘E’, ‘C’, ‘D’, ‘F’], [‘G’, ‘A’, ‘B’, ‘C’, ‘E’, ‘F’], [‘G’, ‘A’, ‘B’, ‘C’, ‘D’, ‘F’]]

BA [[‘B’, ‘C’, ‘E’, ‘G’, ‘A’]]

DA []

Эти модули выводят списки возможных путей через контрольный граф — я перенес две строки, чтобы облегчить его чтение (здесь также можно было бы использовать модуль Python pprint форматированного вывода). Обратите внимание, что обе функции во всех тестах находят одинаковые пути, но порядок нахождения может быть различным. Порядок путей, возвращаемых модулем gsearch2, зависит от того, как и когда продолжения добавляются в его стек пути — попробуйте проследить порядок следования путей в выводе, чтобы понять, как это происходит.

Использованная литература:

Марк Лутц — Программирование на Python, 4-е издание, II том, 2011