Triển khai thuật toán Dijkstra bằng Python
Tôi đã triển khai Dijkstra's algorithmcho nghiên cứu của mình về mô hình Kinh tế, sử dụng Python. Trong nghiên cứu của mình, tôi đang điều tra hai chức năng và sự khác biệt giữa chúng. Mọi hàm nhận hai tham số đầu vào: F(a,b)và Z(a,b).
Mọi ô của ma trận được định nghĩa là: $$M[a][b]=|F(a,b)-Z(a,b)|$$
Mục đích của việc này là tìm ra đường đi của sự khác biệt nhỏ nhất giữa các phương trình sẽ đúng cho mọi đầu vào a
Các triển khai trực tuyến của thuật toán Dijkstra đều sử dụng các cạnh có trọng số trong khi tôi có các đỉnh có trọng số.
Mã giả:
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[]
Đầu vào:
- Mảng 2d trong đó mỗi giá trị ô là trọng số của nó
- nguồn tuple (x, y)
Đầu ra:
ma trận khoảng cách trong đó mỗi ô chứa khoảng cách từ nguồn đến đỉnh (i, j)
ma trận trước trong đó mỗi ô chứa cha của nó. Bằng cách theo dõi từ (98,98), tôi có thể tìm thấy con đường ngắn nhất.
Thực hiện:
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
Bất kỳ ý kiến về tính đúng đắn của nó?
Trả lời
Mã của bạn nhìn chung là đúng, nhưng bỏ qua srcvà chỉ tìm kiếm theo hướng tích cực. Ngoài ra, nó có thể được dọn dẹp và tối ưu hóa đáng kể.
Một số nhận xét chung đầu tiên:
- Sử dụng tên biến đầy đủ trong mã thể hiện ý nghĩa / mục đích. Không có chi phí đáng kể để sử dụng những cái tên có ý nghĩa, nhưng chúng có thể làm cho mã dễ hiểu hơn nhiều.
- Lưu ý về các tính năng và tiêu chuẩn của ngôn ngữ máy chủ. Tránh sử dụng lại tên của nội trang (ví dụ
min) và cố gắng tuân thủ các tiêu chuẩn về kiểu mã hóa . - Tránh
numpytrừ khi thực sự sử dụng các tính năng có sẵn của nó. Sử dụngnumpy.arrayđể truy cập trực tiếp thường chậm hơnlist/set/ ... vì các giá trị được chuyển đổi thành các đối tượng Python đầy đủ trên mỗi lần truy cập.
Đừng đưa ra giả định về các tính năng của dữ liệu của bạn. Cụ thể, hãy tránh những điều sau:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Các lỗi này không thành công đối với đồ thị có khoảng cách> 99999 hoặc hơn 1000 phần tử. Tính toán chúng cho đầu vào của bạn hoặc sử dụng giới hạn trên thực sự.
Vì các số có giá trị "tối đa" được xác định rõ ràng, chúng tôi có thể sử dụng điều này một cách an toàn:
INFINITY = float('int')
Vì đầu vào graphlà ma trận nxn, chúng ta chỉ có thể truy vấn kích thước của nó.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Hãy để chúng tôi bắt đầu với vertex in Q with min dist[u]/ dijkstra_get_min. Thuật toán của bạn phù hợp, nhưng chúng tôi có thể khai thác rằng nội trang của Python minđã cho phép các trọng số tùy chỉnh. Đối số for vertex in Q:trở thành đối số chính min, if dist[vertex[0], vertex[1]] <= min:trở thành trọng số key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
Các Dijkstrathuật toán bao gồm hai phần - Không khởi động và tìm kiếm. Mã của bạn trở nên rõ ràng hơn nếu chúng tôi chia hai phần này - dòng của bạn dist[0][0] = 0là sự chuyển đổi từ phần này sang phần khác.
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
Mục đích của khởi tạo là mọi điểm đều có cùng giá trị. Điều này có nghĩa là chúng ta có thể tạo trực tiếp các ma trận với giá trị cuối cùng của chúng. Ngoài ra, vì thuật toán không sử dụng "nút trước", chúng tôi có thể khởi tạo nó thành một trình giữ chỗ rẻ tiền.
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
Thay vì theo dõi các nút đã truy cập dưới dạng danh sách ( [..., ...]), chúng tôi sử dụng tập hợp ( {..., ...}). Một tập hợp là không có thứ tự và hỗ trợ kiểm tra thành viên O (1), so với kiểm tra thành viên O (n) danh sách. Điều này làm cho nó phù hợp hơn cho việc ghi sổ các nút đã truy cập / chưa truy cập.
Để tìm kiếm thông qua biểu đồ, chúng tôi sẽ đi thăm các hàng xóm nhiều lần. Đây là một phần quan trọng có thể dễ dàng thực hiện sai - trừ khi việc triển khai Graph cung cấp nó, thì việc triển khai một cách rõ ràng là rất đáng giá.
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
]
Cốt lõi của thuật toán vẫn giữ nguyên về mặt logic: Chúng tôi điều chỉnh một số tên để dễ nói hơn (ví dụ u-> node, v-> neighbour). Chúng tôi sử dụng sự chuẩn bị neighboursthay vì cách diễn đạt dài dòng.
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
Tại thời điểm này, mã sẽ nhanh hơn và dễ bảo trì hơn. Lỗ hổng rõ ràng nhất mà chúng tôi vẫn có là việc xử lý rõ ràng các kích thước. Thay vì truy cập thủ công từng thứ nguyên, sẽ tốt hơn nếu chúng ta có thể truy cập trực tiếp vào các điểm.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Điều này có thể được "khắc phục" bằng cách sử dụng từ điển ( {point: value, ...}) thay vì danh sách lồng nhau ( [[value, ...], ...]). Một nhược điểm ngay lập tức là điều này đánh đổi bộ nhớ vì sự đơn giản.
Tuy nhiên, nó có thể được sử dụng để thực sự giảm việc sử dụng bộ nhớ - các từ điển có thể thưa thớt một cách tự nhiên, cho phép chúng ta không cần lưu trữ các trường chưa xác định. Vì bất kỳ nút nào đã truy cập trở nên không liên quan đến khoảng cách, chúng tôi thậm chí có thể xóa distancescác nút đã được xử lý.
[x for x in range(1, 1001)]có thể được viết như là chỉ list(range(1, 1001)).
Sẽ rất tốt nếu 1001đặt tên cho nó.
Tương tự, [0 for x in RANGE_ARR]có thể được viết là [0] * len(RANGE_ARR). Nhân bất kỳ kiểu dãy nào với một số nguyên sẽ lặp lại các phần tử trong dãy. Như một phần thưởng, từ một số điểm chuẩn nhanh mà tôi vừa làm, nó cũng nhanh hơn gấp 10 lần:
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
Tuy nhiên , hãy lưu ý rằng bạn không nên sử dụng điều này khi loại phần tử có thể thay đổi (như [[0]] * 5). Nhân một chuỗi sẽ tạo ra nhiều tham chiếu đến cùng một đối tượng; nó không tạo ra các bản sao.
Có vẻ như Qphải là một tập hợp. Bạn không quan tâm đến thứ tự, và điều duy nhất bạn sử dụng nó để theo dõi thành viên của một tập hợp. Bộ sẽ nhanh hơn đáng kể ở đây. Hai thay đổi duy nhất cần thiết là:
Q = set()
. . .
Q.add((i, j))
Sự thay đổi duy nhất tôi có thể thấy việc thực hiện này dijkstra_get_minvề mặt kỹ thuật là dựa vào thứ tự của Q. Nếu hai phần tử có cùng giá trị nhỏ nhất nằm trong Q, thuật toán của bạn sẽ chọn trường hợp cuối cùng. Vì các bộ có thể sử dụng một thứ tự khác, điều này có thể thay đổi đỉnh được trả về.
Có vẻ như MAX_DISTANCElà một số lượng lớn tùy ý mà mọi thứ khác sẽ ít hơn. Bạn có thể muốn thử sử dụng np.infcho điều đó. Bằng cách mã hóa cứng giới hạn trên, bạn có nguy cơ vấn đề "phát triển" về sau và có khả năng vượt quá mức tối đa đó; gây ra hành vi sai lầm.