Dijkstra algoritmasının Python'da uygulanması
Dijkstra's algorithmPython kullanarak Ekonomik bir model üzerine araştırmam için uyguladım . Araştırmamda iki işlevi ve aralarındaki farkları araştırıyorum. Her işlev girdi olarak iki parametre alır: F(a,b)ve Z(a,b).
Matrisin her hücresi şu şekilde tanımlanır: $$M[a][b]=|F(a,b)-Z(a,b)|$$
Bunun amacı, her girdi için doğru olacak denklemler arasındaki minimum farkın yolunu bulmaktır. a
Dijkstra algoritmasının çevrimiçi uygulamaları ağırlıklı kenarlar kullanıyordu, oysa ben ağırlıklı köşelerim var.
Sözde kod:
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[]
Giriş:
- Her hücrenin değerinin ağırlığı olduğu 2d dizisi
- kaynak demeti (x, y)
Çıktı:
her hücrenin kaynaktan tepe noktasına (i, j) olan mesafeyi içerdiği mesafe matrisi
her hücrenin ebeveynini içerdiği prev matris. (98,98) 'den izleyerek en kısa yolu bulabilirim.
Uygulama:
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
Doğruluğu hakkında herhangi bir fikriniz var mı?
Yanıtlar
Kodunuz genel olarak doğru görünür, ancak yok sayar srcve yalnızca pozitif yönde arama yapar. Ek olarak, önemli ölçüde temizlenebilir ve optimize edilebilir.
Önce bazı genel yorumlar:
- Anlam / amaç ifade eden kodda tam değişken adlarını kullanın. Anlamlı isimler kullanmanın önemli bir maliyeti yoktur, ancak kodun sindirilmesini çok daha kolay hale getirebilirler.
- Ev sahibi dilin özelliklerinden ve standartlarından haberdar olun. Yerleşiklerin adlarını yeniden kullanmaktan kaçının (örn.
min) Ve kodlama stili standartlarına uymaya çalışın . numpyYerleşik özelliklerini gerçekten kullanmadıkça kaçının .numpy.arrayDoğrudan erişim için kullanmak genellikle / / ... ' den daha yavaştır çünkü değerler her erişimde tam Python nesnelerine dönüştürülür.listset
Verilerinizin özellikleri hakkında varsayımlarda bulunmayın. Özellikle şunlardan kaçının:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Bunlar, uzaklığı 99999 veya 1000'den fazla olan grafiklerde başarısız olur. Bunları girişiniz için hesaplayın veya gerçek üst sınırları kullanın.
Sayıların iyi tanımlanmış bir "maksimum" u olduğundan, bunu güvenle kullanabiliriz:
INFINITY = float('int')
Girdi graphbir nxn matrisi olduğundan, boyutunu sorgulayabiliriz.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Bize ile başlayalım vertex in Q with min dist[u]/ ' dijkstra_get_min. Algoritmanız doğru, ancak Python'un yerleşikinin minzaten özel ağırlıklara izin verdiğinden yararlanabiliriz . for vertex in Q:Birincil bağımsız değişken hale gelir min, if dist[vertex[0], vertex[1]] <= min:ağırlık haline gelir key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
DijkstraBaşlatma ve arama - algoritması iki bölümden oluşmaktadır. Bu iki parçayı ayırırsak kodunuz daha net hale gelir - hattınız dist[0][0] = 0birinden diğerine geçiştir.
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
İlklendirmenin amacı, her noktanın aynı değere sahip olmasıdır. Bu, matrisleri doğrudan nihai değerleriyle oluşturabileceğimiz anlamına gelir. Ayrıca, algoritma "önceki düğümü" kullanmadığından , onu ucuz bir yer tutucuyla başlatabiliriz.
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
Ziyaret edilen düğümleri liste ( [..., ...]) olarak izlemek yerine set ( {..., ...}) kullanıyoruz. Bir küme sırasızdır ve liste O (n) üyelik testlerine kıyasla O (1) üyelik testlerini destekler. Bu, ziyaret edilen / ziyaret edilmeyen düğümlerin muhasebesi için daha uygun hale getirir.
Grafikte arama yapmak için komşuları tekrar tekrar ziyaret edeceğiz. Bu, kolayca yanlış yapılabilecek önemli bir parçadır - Grafik uygulaması bunu sağlamadıkça, açıkça uygulanması faydalı olabilir.
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
]
Algoritmanın çekirdeği mantıksal olarak aynı kalır: Bazı isimleri daha fazla konuşacak şekilde ayarlıyoruz (örneğin u-> node, v-> neighbour). neighboursUzun ifade yerine hazırlanmış olanı kullanıyoruz .
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
Bu noktada, kodun hem daha hızlı hem de bakımı daha kolay olması gerekir. Halen sahip olduğumuz en göze batan kusur, boyutların açık bir şekilde ele alınmasıdır. Her bir boyuta manuel olarak erişmek yerine, noktalara doğrudan erişebilmemiz daha iyi olur.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Bu, {point: value, ...}yuvalanmış listeler ( [[value, ...], ...]) yerine sözlükler ( ) kullanılarak "düzeltilebilir" . Hemen bir dezavantajı, bunun basitlik için hafızayı değiştirmesidir.
Bununla birlikte, bellek kullanımını fiilen azaltmak için kullanılabilir - sözlükler doğal olarak seyrek olabilir, bu da bizim belirsiz alanları depolamamamıza izin verir. Ziyaret edilen herhangi bir düğüm mesafeler için önemsiz hale distancesgeldiğinden, önceden işlenmiş düğümlerden bile kurtulabiliriz.
[x for x in range(1, 1001)]adil olarak yazılabilir list(range(1, 1001)).
Buna da 1001bir isim vermek iyi olur .
Benzer şekilde [0 for x in RANGE_ARR]olarak yazılabilir [0] * len(RANGE_ARR). Herhangi bir dizi türünün bir tamsayı ile çarpılması, dizi içindeki öğeleri tekrar eder. Bonus olarak, az önce yaptığım bazı hızlı karşılaştırmalardan 10 kat daha hızlı:
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
Unutmayın ki öğe türü değiştirilebilir (gibi [[0]] * 5) olduğunda bunu kullanmamalısınız . Bir diziyi çarpmak, aynı nesneye birden çok başvuru oluşturur; kopya çıkarmaz.
QBir set olmalı gibi görünüyor . Siparişi önemsemiyorsunuz ve onu kullandığınız tek şey bir setin üyeliğini takip etmektir. Setler burada önemli ölçüde daha hızlı olacaktır. İhtiyaç duyulan sadece iki değişiklik:
Q = set()
. . .
Q.add((i, j))
Bu yaptığını görebildiğim tek değişiklik dijkstra_get_minteknik olarak sırasına dayanıyor Q. Aynı minimum değerlere sahip iki öğe Q'da ise, algoritmanız son örneği seçer. Kümeler farklı bir sıra kullanabileceğinden, bu, döndürülen tepe noktasını değiştirebilir.
Görünüşe göre MAX_DISTANCE, diğer her şeyin daha az olacağı, keyfi olarak büyük bir sayı olması gerekiyor. Bunun için kullanmayı denemek isteyebilirsiniz np.inf. Üst limiti kodlayarak, problemi daha sonra "büyüme" ve potansiyel olarak bu maksimum değeri aşma riskini alırsınız; hatalı davranışa neden olur.