Implementação do algoritmo de Dijkstra em Python
Implementei Dijkstra's algorithmpara minha pesquisa um modelo econômico, usando Python. Em minha pesquisa, estou investigando duas funções e as diferenças entre elas. Cada função leva como entrada dois parâmetros: F(a,b)e Z(a,b).
Cada célula da matriz é definida como: $$M[a][b]=|F(a,b)-Z(a,b)|$$
O objetivo disso é encontrar o caminho de diferença mínima entre as equações que serão corretas para cada entrada a
As implementações online do algoritmo de Dijkstra usaram arestas ponderadas, enquanto eu tenho vértices ponderados.
Pseudo-código:
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[]
Entrada:
- 2d array onde o valor de cada célula é o seu peso
- tupla de origem (x, y)
Resultado:
matriz de distância onde cada célula contém distância da fonte ao vértice (i, j)
matriz anterior onde cada célula contém seu pai. Rastreando de (98,98), posso encontrar o caminho mais curto.
Implementação:
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
Alguma opinião sobre a sua correção?
Respostas
Seu código parece geralmente correto, mas ignora srce pesquisa apenas na direção positiva. Além disso, pode ser limpo e otimizado significativamente.
Alguns comentários gerais primeiro:
- Use nomes completos de variáveis em código que expressem significado / propósito. Não há custo significativo para usar nomes significativos, mas eles podem tornar o código muito mais fácil de digerir.
- Esteja ciente dos recursos e padrões do idioma host. Evite reutilizar os nomes de builtins (por exemplo
min) e tente aderir aos padrões de estilo de codificação . - Evite, a
numpymenos que realmente use seus recursos embutidos. Usarnumpy.arraypara acesso direto é geralmente mais lento do quelist/set/ ... porque os valores são convertidos em objetos Python completos em cada acesso.
Não faça suposições sobre os recursos de seus dados. Especificamente, evite:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Eles falham para gráficos com distância> 99999 ou mais de 1000 elementos. Calcule-os para sua entrada ou use limites superiores verdadeiros.
Como os números têm um "máximo" bem definido, podemos usar isso com segurança:
INFINITY = float('int')
Como a entrada graphé uma matriz nxn, podemos apenas consultar seu tamanho.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Vamos começar com vertex in Q with min dist[u]/ dijkstra_get_min. Seu algoritmo é adequado, mas podemos explorar que o builtin do Python minjá permite pesos personalizados. O for vertex in Q:torna-se o principal argumento para min, if dist[vertex[0], vertex[1]] <= min:torna-se o peso key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
O Dijkstraalgoritmo consiste em duas partes - inicialização e pesquisa. Seu código fica mais claro se dividirmos essas duas partes - sua linha dist[0][0] = 0é a transição de uma para a outra.
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
O objetivo da inicialização é que todos os pontos tenham o mesmo valor. Isso significa que podemos criar diretamente as matrizes com seu valor final. Além disso, como o algoritmo não usa o "nó anterior", podemos inicializá-lo para um marcador barato.
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
Em vez de rastrear os nós visitados como uma lista ( [..., ...]), usamos um set ( {..., ...}). Um conjunto é desordenado e suporta testes de associação O (1), em comparação com testes de associação da lista O (n). Isso o torna mais adequado para a contabilidade de nós visitados / não visitados.
Para pesquisar no gráfico, visitaremos os vizinhos repetidamente. Esta é uma parte importante que pode ser facilmente executada de forma errada - a menos que a implementação do Graph forneça, pode valer a pena implementar explicitamente.
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
]
O núcleo do algoritmo permanece logicamente o mesmo: ajustamos alguns nomes para serem mais falantes (por exemplo u-> node, v-> neighbour). Usamos neighboursa expressão preparada em vez da expressão longa.
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
Neste ponto, o código deve ser mais rápido e fácil de manter. A falha mais gritante que ainda temos é o manuseio explícito das dimensões. Em vez de acessar manualmente cada dimensão, seria melhor se pudéssemos acessar diretamente os pontos.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Isso pode ser "consertado" usando dicionários ( {point: value, ...}) em vez de listas aninhadas ( [[value, ...], ...]). Uma desvantagem imediata é que isso troca memória por simplicidade.
No entanto, pode ser usado para realmente reduzir o uso de memória - os dicionários podem ser naturalmente esparsos, permitindo-nos simplesmente não armazenar campos indeterminados. Uma vez que qualquer nó visitado se torna irrelevante para distâncias, podemos até mesmo limpar os distancesnós que já foram processados.
[x for x in range(1, 1001)]pode ser escrito da mesma forma list(range(1, 1001)).
Seria bom dar 1001um nome a isso também.
Da mesma forma, [0 for x in RANGE_ARR]pode ser escrito como [0] * len(RANGE_ARR). Multiplicar qualquer tipo de sequência por um inteiro repete os elementos dentro da sequência. Como um bônus, a partir de um rápido benchmarking que acabei de fazer, também é mais de 10 vezes mais rápido:
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
Esteja ciente de que você não deve usar isso quando o tipo de elemento for mutável (como [[0]] * 5). Multiplicar uma sequência cria várias referências ao mesmo objeto; não faz cópias.
Parece que Qdeveria ser um conjunto. Você não se preocupa com a ordem e a única coisa que a utiliza é para rastrear a associação de um conjunto. Os conjuntos serão significativamente mais rápidos aqui. As únicas duas mudanças necessárias são:
Q = set()
. . .
Q.add((i, j))
A única mudança que posso ver é que dijkstra_get_mintecnicamente depende da ordem de Q. Se dois elementos com os mesmos valores mínimos estão em Q, seu algoritmo escolhe a última instância. Como os conjuntos podem usar uma ordem diferente, isso pode alterar o vértice que é retornado.
Parece que MAX_DISTANCEse destina a ser um número arbitrariamente grande e todo o resto será menor. Você pode querer tentar usar np.infpara isso. Ao codificar o limite superior, você corre o risco de o problema "crescer" mais tarde e potencialmente exceder esse máximo; causando comportamento errôneo.