Implementazione dell'algoritmo di Dijkstra in Python
Ho implementato Dijkstra's algorithmper la mia ricerca un modello economico, utilizzando Python. Nella mia ricerca sto indagando due funzioni e le differenze tra loro. Ogni funzione prende come input due parametri: F(a,b)e Z(a,b).
Ogni cella della matrice è definita come: $$M[a][b]=|F(a,b)-Z(a,b)|$$
Lo scopo di questo è trovare il percorso della minima differenza tra le equazioni che sarà corretto per ogni input a
Le implementazioni online dell'algoritmo di Dijkstra utilizzavano tutte bordi ponderati mentre io ho vertici ponderati.
Pseudo-codice:
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[]
Ingresso:
- Matrice 2d in cui il valore di ciascuna cella è il suo peso
- tupla sorgente (x, y)
Produzione:
matrice della distanza in cui ogni cella contiene la distanza dalla sorgente al vertice (i, j)
matrice precedente in cui ogni cella contiene il suo genitore. Tracciando da (98,98) posso trovare il percorso più breve.
Implementazione:
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
Qualche opinione sulla sua correttezza?
Risposte
Il tuo codice sembra generalmente corretto, ma ignora srce cerca solo in direzione positiva. Inoltre, può essere pulito e ottimizzato in modo significativo.
Prima alcuni commenti generali:
- Usa nomi di variabili completi nel codice che esprimano significato / scopo. Non vi è alcun costo significativo per l'utilizzo di nomi significativi, ma possono rendere il codice molto più facile da digerire.
- Sii consapevole delle caratteristiche e degli standard della lingua ospitante. Evita di riutilizzare i nomi dei comandi incorporati (ad esempio
min) e cerca di aderire agli standard dello stile di codifica . - Evita a
numpymeno che non utilizzi effettivamente le sue funzionalità integrate. L'utilizzonumpy.arrayper l'accesso diretto è solitamente più lento dilist/set/ ... perché i valori vengono convertiti in oggetti Python completi ad ogni accesso.
Non fare supposizioni sulle caratteristiche dei tuoi dati. In particolare, evita questi:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Questi falliscono per i grafici con distanza> 99999 o più di 1000 elementi. Calcolali per il tuo input o usa veri limiti superiori.
Poiché i numeri hanno un "massimo" ben definito, possiamo usarlo in sicurezza:
INFINITY = float('int')
Poiché l'input graphè una matrice nxn, possiamo semplicemente interrogare la sua dimensione.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Cominciamo con vertex in Q with min dist[u]/ dijkstra_get_min. Il tuo algoritmo è corretto, ma possiamo sfruttare il fatto che il builtin di Python minconsente già pesi personalizzati. Il for vertex in Q:diventa l'argomento principale min, il if dist[vertex[0], vertex[1]] <= min:diventa il peso key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
L' Dijkstraalgoritmo è composto da due parti: inizializzazione e ricerca. Il tuo codice diventa più chiaro se dividiamo queste due parti: la tua linea dist[0][0] = 0è la transizione dall'una all'altra.
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
Lo scopo dell'inizializzazione è che ogni punto ha lo stesso valore. Ciò significa che possiamo creare direttamente le matrici con il loro valore finale. Inoltre, poiché l'algoritmo non utilizza il "nodo precedente", possiamo inizializzarlo su un segnaposto economico.
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
Invece di tracciare i nodi visitati come list ( [..., ...]) usiamo set ( {..., ...}). Un set non è ordinato e supporta O (1) test di appartenenza, rispetto ai test di appartenenza all'elenco O (n). Ciò lo rende più adatto per la contabilità dei nodi visitati / non visitati.
Per cercare nel grafico, visiteremo ripetutamente i vicini. Questa è una parte fondamentale che può essere facilmente sbagliata - a meno che l'implementazione di Graph non lo fornisca, può essere utile implementarla esplicitamente.
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
]
Il nucleo dell'algoritmo rimane logicamente lo stesso: regoliamo alcuni nomi per essere più pronunciati (ad esempio u-> node, v-> neighbour). Usiamo il preparato neighboursinvece dell'espressione lunga.
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
A questo punto, il codice dovrebbe essere più veloce e più facile da mantenere. Il difetto più evidente che abbiamo ancora è la gestione esplicita delle dimensioni. Invece di accedere manualmente a ciascuna dimensione, sarebbe meglio se potessimo accedere direttamente ai punti.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Questo può essere "risolto" utilizzando dizionari ( {point: value, ...}) invece di elenchi annidati ( [[value, ...], ...]). Uno svantaggio immediato è che questo scambia la memoria con la semplicità.
Tuttavia, può essere utilizzato per ridurre effettivamente l'utilizzo della memoria: i dizionari possono essere naturalmente sparsi, permettendoci semplicemente di non memorizzare campi indeterminati. Poiché qualsiasi nodo visitato diventa irrilevante per le distanze, possiamo anche eliminare i distancesnodi che sono già elaborati.
[x for x in range(1, 1001)]può essere scritto come solo list(range(1, 1001)).
Sarebbe bene dare 1001un nome anche a questo.
Allo stesso modo, [0 for x in RANGE_ARR]può essere scritto come [0] * len(RANGE_ARR). La moltiplicazione di qualsiasi tipo di sequenza per un numero intero ripete gli elementi all'interno della sequenza. Come bonus, da alcuni rapidi benchmark che ho appena fatto, è anche più di 10 volte più veloce:
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
Tieni presente però che non dovresti usarlo quando il tipo di elemento è mutabile (come [[0]] * 5). La moltiplicazione di una sequenza crea più riferimenti allo stesso oggetto; non fa copie.
Sembra che Qdovrebbe essere un set. Non ti interessa l'ordine e l'unica cosa per cui lo usi è monitorare l'appartenenza a un set. I set saranno molto più veloci qui. Le uniche due modifiche necessarie sono:
Q = set()
. . .
Q.add((i, j))
L'unico cambiamento che posso vedere è che dijkstra_get_mintecnicamente si basa sull'ordine di Q. Se due elementi con gli stessi valori minimi sono in Q, il tuo algoritmo sceglie l'ultima istanza. Poiché gli insiemi possono usare un ordine diverso, questo può cambiare il vertice che viene restituito.
Sembra che MAX_DISTANCEdebba essere un numero arbitrariamente grande di cui tutto il resto sarà inferiore. Potresti provare a usare np.infper quello. Codificando il limite superiore, si rischia che il problema "cresca" più tardi e potenzialmente superi quel limite massimo; causando un comportamento errato.