Implementasi algoritma Dijkstra dengan Python
Saya telah menerapkan Dijkstra's algorithmuntuk penelitian saya tentang model Ekonomi, menggunakan Python. Dalam penelitian saya, saya menyelidiki dua fungsi dan perbedaan di antara keduanya. Setiap fungsi mengambil dua parameter sebagai masukan: F(a,b)dan Z(a,b).
Setiap sel dari matriks didefinisikan sebagai: $$M[a][b]=|F(a,b)-Z(a,b)|$$
Tujuannya adalah untuk menemukan jalur selisih minimal antara persamaan yang akan benar untuk setiap masukan a
Implementasi online dari algoritma Dijkstra semuanya menggunakan tepi berbobot sedangkan saya memiliki simpul berbobot.
Kode semu:
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[]
Memasukkan:
- Array 2d di mana setiap nilai sel adalah bobotnya
- sumber tupel (x, y)
Keluaran:
matriks jarak dimana setiap sel berisi jarak dari sumber ke simpul (i, j)
matriks prev dimana setiap sel berisi induknya. Dengan menelusuri kembali dari (98,98) saya dapat menemukan jalur terpendek.
Penerapan:
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
Ada pendapat tentang kebenarannya?
Jawaban
Kode Anda secara umum terlihat benar, tetapi mengabaikan srcdan hanya mencari ke arah yang positif. Selain itu, dapat dibersihkan dan dioptimalkan secara signifikan.
Beberapa komentar umum terlebih dahulu:
- Gunakan nama variabel lengkap dalam kode yang mengungkapkan arti / tujuan. Tidak ada biaya yang signifikan untuk menggunakan nama yang bermakna, tetapi mereka dapat membuat kode lebih mudah dicerna.
- Waspadai fitur dan standar bahasa tuan rumah. Hindari menggunakan kembali nama bawaan (misalnya
min) dan mencoba untuk mengikuti standar gaya pengkodean . - Hindari
numpykecuali benar-benar menggunakan fitur bawaannya. Penggunaannumpy.arrayuntuk akses langsung biasanya lebih lambat darilist/set/ ... karena nilai diubah menjadi objek Python penuh pada setiap akses.
Jangan membuat asumsi tentang fitur data Anda. Secara khusus, hindari ini:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Ini gagal untuk grafik dengan jarak> 99999 atau lebih dari 1000 elemen. Hitunglah untuk masukan Anda, atau gunakan batas atas yang sebenarnya.
Karena angka memiliki "maksimum" yang terdefinisi dengan baik, kita dapat menggunakan ini dengan aman:
INFINITY = float('int')
Karena inputnya graphadalah matriks nxn, kita bisa menanyakan ukurannya.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Mari kita mulai dengan vertex in Q with min dist[u]/ dijkstra_get_min. Algoritme Anda tepat, tetapi kami dapat mengeksploitasi bahwa bawaan Python minsudah memungkinkan bobot khusus. Itu for vertex in Q:menjadi argumen utama min, if dist[vertex[0], vertex[1]] <= min:menjadi bobot key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
The Dijkstraalgoritma terdiri dari dua bagian - inisialisasi dan pencarian. Kode Anda menjadi lebih jelas jika kami membagi dua bagian ini - baris Anda dist[0][0] = 0adalah transisi dari satu bagian ke bagian lainnya.
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
Tujuan dari inisialisasi adalah agar setiap titik memiliki nilai yang sama. Ini berarti kita dapat langsung membuat matriks dengan nilai akhirnya. Selain itu, karena algoritme tidak menggunakan "node sebelumnya", kita dapat menginisialisasinya ke placeholder yang murah.
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
Alih-alih melacak node yang dikunjungi sebagai list ( [..., ...]), kami menggunakan set ( {..., ...}). Satu set tidak berurutan dan mendukung tes keanggotaan O (1), dibandingkan dengan tes keanggotaan daftar O (n). Ini membuatnya lebih cocok untuk pembukuan node yang dikunjungi / belum dikunjungi.
Untuk mencari melalui grafik, kita akan mengunjungi tetangga berulang kali. Ini adalah bagian penting yang dapat dengan mudah dilakukan kesalahan - kecuali jika implementasi Grafik menyediakannya, implementasi secara eksplisit dapat bermanfaat.
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
]
Inti dari algoritme tetap sama secara logis: Kami menyesuaikan beberapa nama agar lebih berbicara (misalnya u-> node, v-> neighbour). Kami menggunakan preparasi, neighboursbukan ekspresi panjang.
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
Pada titik ini, kode harus lebih cepat dan lebih mudah dikelola. Cacat paling mencolok yang masih kami miliki adalah penanganan dimensi secara eksplisit. Daripada mengakses setiap dimensi secara manual, akan lebih baik jika kita bisa mengakses poin secara langsung.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Ini bisa "diperbaiki" dengan menggunakan kamus ( {point: value, ...}) daripada daftar bertingkat ( [[value, ...], ...]). Kelemahan langsungnya adalah bahwa ini memperdagangkan memori untuk kesederhanaan.
Namun, ini dapat digunakan untuk benar-benar mengurangi penggunaan memori - kamus bisa sangat jarang, memungkinkan kita untuk tidak menyimpan bidang yang belum ditentukan. Karena setiap node yang dikunjungi menjadi tidak relevan untuk jarak, kita bahkan dapat menghapus distancesnode yang sudah diproses.
[x for x in range(1, 1001)]dapat ditulis sebagai adil list(range(1, 1001)).
Akan bagus untuk memberi 1001nama itu juga.
Demikian pula, [0 for x in RANGE_ARR]dapat ditulis sebagai [0] * len(RANGE_ARR). Mengalikan jenis urutan apa pun dengan bilangan bulat akan mengulangi elemen dalam urutan tersebut. Sebagai bonus, dari beberapa pembandingan cepat yang baru saja saya lakukan, juga lebih dari 10x lebih cepat:
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
Berhati-hatilah karena Anda tidak boleh menggunakan ini ketika tipe elemen bisa berubah (seperti [[0]] * 5). Mengalikan urutan menghasilkan banyak referensi ke objek yang sama; itu tidak membuat salinan.
Sepertinya Qharus satu set. Anda tidak peduli tentang pesanan, dan satu-satunya hal yang Anda gunakan untuk melacak keanggotaan set. Set akan jauh lebih cepat di sini. Hanya dua perubahan yang diperlukan adalah:
Q = set()
. . .
Q.add((i, j))
Satu-satunya perubahan yang saya dapat lihat adalah pembuatan ini secara dijkstra_get_minteknis bergantung pada urutan Q. Jika dua elemen dengan nilai minimum yang sama ada di Q, algoritme Anda mengambil contoh terakhir. Karena himpunan dapat menggunakan urutan yang berbeda, ini dapat mengubah simpul apa yang dikembalikan.
Sepertinya MAX_DISTANCEitu dimaksudkan untuk menjadi sejumlah besar sewenang-wenang bahwa segala sesuatu yang lain akan kurang dari. Anda mungkin ingin mencoba menggunakan np.infuntuk itu. Dengan melakukan hardcode pada batas atas, Anda berisiko masalah "berkembang" nanti dan berpotensi melebihi batas maksimum itu; menyebabkan perilaku yang salah.