Реализация алгоритма Дейкстры на Python
Я реализовал Dijkstra's algorithmсвое исследование по экономической модели, используя Python. В своем исследовании я исследую две функции и различия между ними. Каждая функция принимает на вход два параметра: F(a,b)и Z(a,b).
Каждая ячейка матрицы определяется как: $$M[a][b]=|F(a,b)-Z(a,b)|$$
Цель этого - найти путь минимальной разницы между уравнениями, который будет правильным для каждого ввода. a
Все онлайн-реализации алгоритма Дейкстры использовали взвешенные ребра, тогда как у меня были взвешенные вершины.
Псевдокод:
function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u: // only v that are still in Q
alt ← dist[u] + length(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]
Вход:
- 2d массив, где значение каждой ячейки - это ее вес
- исходный кортеж (x, y)
Вывод:
матрица расстояний, где каждая ячейка содержит расстояние от источника до вершины (i, j)
матрица prev, в которой каждая ячейка содержит своего родителя. Отслеживая от (98,98), я могу найти кратчайший путь.
Реализация:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
def dijkstra_get_min(Q, dist):
min = MAX_DISTANCE + 1
u = None
for vertex in Q:
if dist[vertex[0], vertex[1]] <= min:
min = dist[vertex[0], vertex[1]]
u = vertex
return u
def dijkstra(graph, src=(0, 0)):
dist = np.array([np.array([0 for x in RANGE_ARR], dtype=float) for y in RANGE_ARR])
prev = np.array([np.array([(0, 0) for x in RANGE_ARR], dtype='i,i') for y in RANGE_ARR])
Q = []
for i in RANGE_ARR_0:
for j in RANGE_ARR_0:
dist[i, j] = MAX_DISTANCE
prev[i, j] = (0, 0)
Q.append((i, j))
dist[0][0] = 0
while Q:
u = dijkstra_get_min(Q, dist)
Q.remove(u)
moves = [x for x in ( (u[0], u[1] + 1), (u[0] + 1, u[1]), (u[0] + 1, u[1] + 1) ) if x in Q]
for v in moves:
alt = dist[u[0]][u[1]] + graph[v[0]][v[1]]
if alt < dist[v[0]][v[1]]:
dist[v[0], v[1]] = alt
prev[v[0], v[1]] = u
return dist, prev
Есть какие-нибудь мнения о его правильности?
Ответы
Ваш код выглядит в целом правильным, но игнорирует srcи ищет только в положительном направлении. Кроме того, его можно значительно очистить и оптимизировать.
Сначала несколько общих комментариев:
- Используйте в коде полные имена переменных, которые выражают смысл / цель. Использование значимых имен не требует значительных затрат, но они могут значительно облегчить усвоение кода.
- Помните об особенностях и стандартах основного языка. Избегайте повторного использования имен встроенных функций (например,
min) и старайтесь придерживаться стандартов стиля кодирования . - Избегайте,
numpyесли на самом деле не используете его встроенные функции. Использованиеnumpy.arrayдля прямого доступа обычно медленнее, чемlist/set/ ... потому что значения преобразуются в полные объекты Python при каждом доступе.
Не делайте предположений об особенностях ваших данных. В частности, избегайте этого:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Они не работают для графиков с расстоянием> 99999 или более 1000 элементов. Либо вычислите их для своего ввода, либо используйте истинные верхние границы.
Поскольку числа имеют четко определенный «максимум», мы можем безопасно использовать это:
INFINITY = float('int')
Поскольку входные данные graphпредставляют собой матрицу размера nxn, мы можем просто запросить ее размер.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Начнем с vertex in Q with min dist[u]/ dijkstra_get_min. Ваш алгоритм правильный, но мы можем использовать тот встроенный Python, который minуже позволяет настраивать веса. То for vertex in Q:становится основным аргументом min, а if dist[vertex[0], vertex[1]] <= min:становится весом key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
DijkstraАлгоритм состоит из двух частей - инициализация и поиска. Ваш код станет более понятным, если мы разделим эти две части - ваша строка dist[0][0] = 0- это переход от одной к другой.
def dijkstra(graph, src=(0, 0)):
# dist, prev, Q
distances, prev_nodes, unvisited = dijkstra_initial(len(graph))
# set starting point
distances[src[0]][src[1]] = 0
dijkstra_search(graph, distances, prev_nodes, unvisited)
return distances, prev_nodes
Цель инициализации - чтобы каждая точка имела одно и то же значение. Это означает, что мы можем напрямую создавать матрицы с их окончательным значением. Кроме того, поскольку алгоритм не использует «предыдущий узел», мы можем инициализировать его дешевым заполнителем.
def dijkstra_initial(size):
distances = [[INFINITY] * size for _ in range(size)]
prev_nodes = [[None] * size for _ in range(size)]
unvisited = {(x, y) for x in range(size) for y in range(size)}
# dist, prev, Q
return distances, prev_nodes, unvisited
Вместо отслеживания посещенных узлов в виде списка ( [..., ...]) мы используем set ( {..., ...}). Набор неупорядочен и поддерживает тесты членства O (1) по сравнению с тестами членства в списке O (n). Это делает его более подходящим для учета посещенных / непосещенных узлов.
Для поиска по графу мы будем неоднократно посещать соседей. Это ключевая часть, которую легко сделать неправильно - если реализация Graph не предоставляет ее, может быть целесообразно реализовать явно.
def neighbours(node):
x, y = node
return [
(x + x_offset, y + y_offset)
for x_offset in (-1, 0, 1)
for y_offset in (-1, 0, 1)
if not (x_offset == y_offset == 0) # reject node itself
]
Суть алгоритма логически остается прежней: мы настраиваем некоторые имена, чтобы они были более говорящими (например, u-> node, v-> neighbour). Мы используем подготовленное neighboursвместо длинного выражения.
def dijkstra_search(graph, distances, prev_nodes, unvisited):
while unvisited:
node = dijkstra_get_min(unvisited, dist)
unvisited.remove(node)
for neighbour in neighbours(node):
if neighbour not in unvisited:
continue
alt = distances[node[0]][node[1]] + graph[neighbour[0]][neighbour[1]]
if alt < distances[neighbour[0]][neighbour[1]]:
distances[neighbour[0]][neighbour[1]] = alt
prev_nodes[neighbour[0]][neighbour[1]] = node
На этом этапе код должен быть быстрее и проще в обслуживании. Самый вопиющий недостаток, который у нас все еще есть, - это явная обработка размеров. Вместо ручного доступа к каждому измерению было бы лучше, если бы мы могли напрямую обращаться к точкам.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Это можно «исправить», используя словари ( {point: value, ...}) вместо вложенных списков ( [[value, ...], ...]). Непосредственным недостатком является то, что память жертвуется на простоту.
Однако его можно использовать для фактического уменьшения использования памяти - словари могут быть естественно разреженными, что позволяет нам просто не хранить неопределенные поля. Поскольку любой посещаемый узел становится неактуальным для расстояний, мы можем даже очистить distancesот узлов, которые уже обработаны.
[x for x in range(1, 1001)]можно записать как просто list(range(1, 1001)).
Было бы хорошо дать и этому 1001имя.
Аналогично [0 for x in RANGE_ARR]можно записать как [0] * len(RANGE_ARR). При умножении любого типа последовательности на целое число элементы в последовательности повторяются. В качестве бонуса, по результатам небольшого тестирования, которое я только что провел, он также более чем в 10 раз быстрее:
from timeit import timeit
N = int(1e6)
TRIALS = int(1e3)
print(timeit(lambda: [0] * N, number=TRIALS), "seconds")
print(timeit(lambda: [0 for x in range(N)], number=TRIALS), "seconds")
2.9889957 seconds
38.1463017 seconds
Имейте в виду, что вы не должны использовать это, если тип элемента изменяемый (например, [[0]] * 5). Умножение последовательности создает несколько ссылок на один и тот же объект; он не копирует.
Похоже Qдолжен быть набор. Вы не заботитесь о порядке, и единственное, для чего вы его используете, - это отслеживать членство в наборе. Сеты здесь будут проходить значительно быстрее. Требуются только два изменения:
Q = set()
. . .
Q.add((i, j))
Единственное изменение, которое я вижу в этом процессе, dijkstra_get_minтехнически зависит от порядка Q. Если в Q находятся два элемента с одинаковыми минимальными значениями, ваш алгоритм выбирает последний экземпляр. Поскольку наборы могут использовать другой порядок, это может изменить возвращаемую вершину.
Похоже, MAX_DISTANCEдолжно быть какое-то произвольно большое число, которое все остальное будет меньше. Вы можете попробовать использовать np.infдля этого. Жестко запрограммировав верхний предел, вы рискуете, что проблема «вырастет» позже и потенциально превысит этот максимум; вызывая ошибочное поведение.