Tại sao thuật toán Dijkstra sử dụng phím giảm? thuật toán

Question

Dijkstra được dạy cho tôi là như sau

while pqueue is not empty: 
    distance, node = pqueue.delete_min() 
    if node has been visited: 
     continue 
    else: 
     mark node as visited 
    if node == target: 
     break 
    for each neighbor of node: 
     pqueue.insert(distance + distance_to_neighbor, neighbor) 

Nhưng tôi đã làm một số đọc về các thuật toán, và rất nhiều các phiên bản tôi thấy sử dụng giảm-key như trái ngược với chèn.

Tại sao điều này và sự khác biệt giữa hai cách tiếp cận là gì?

Answer 1

Lý do sử dụng phím giảm thay vì nút chèn lại là giữ số lượng nút trong hàng đợi ưu tiên nhỏ, do đó giảm tổng số lượng hàng đợi ưu tiên nhỏ và chi phí của mỗi số dư hàng đợi ưu tiên thấp.

Khi triển khai thuật toán Dijkstra để chèn lại các nút vào hàng đợi ưu tiên với các ưu tiên mới, một nút được thêm vào hàng đợi ưu tiên cho mỗi cạnh m trong biểu đồ. Điều này có nghĩa là có các hoạt động enqueue m và hoạt động dequeue m trên hàng đợi ưu tiên, cho tổng thời gian chạy của O (m T _e + m T _d), trong đó T _e là thời gian cần thiết để đưa vào hàng đợi ưu tiên và T _d là thời gian cần thiết để dequeue từ hàng đợi ưu tiên.

Khi triển khai thuật toán Dijkstra hỗ trợ khóa giảm, hàng ưu tiên giữ các nút bắt đầu bằng n nút trong đó và trên mỗi bước của thuật toán sẽ xóa một nút. Điều này có nghĩa là tổng số lượng heap dequeues là n. Mỗi nút sẽ có phím giảm được gọi là nó có khả năng một lần cho mỗi cạnh dẫn vào nó, vì vậy tổng số phím giảm được thực hiện nhiều nhất là m. Điều này cho phép một thời gian chạy của (n T _e + n T _d + m T _k), trong đó T _k là thời gian cần thiết để gọi giảm-key.

Vậy hiệu ứng này có ảnh hưởng gì đến thời gian chạy? Điều đó phụ thuộc vào hàng đợi ưu tiên bạn sử dụng. Dưới đây là một bảng nhanh chóng mà khoe hàng đợi ưu tiên khác nhau và các runtimes tổng thể của hiện thực giải thuật khác nhau Dijkstra:

Queue   | T_e | T_d | T_k | w/o Dec-Key | w/Dec-Key 
---------------+--------+--------+--------+-------------+--------------- 
Binary Heap |O(log N)|O(log N)|O(log N)| O(M log N) | O(M log N) 
Binomial Heap |O(log N)|O(log N)|O(log N)| O(M log N) | O(M log N) 
Fibonacci Heap | O(1) |O(log N)| O(1) | O(M log N) | O(M + N log N) 

Như bạn có thể thấy, với hầu hết các loại hàng đợi ưu tiên, có thực sự không phải là một sự khác biệt trong tiệm cận thời gian chạy và phiên bản giảm khóa không có khả năng làm tốt hơn nhiều. Tuy nhiên, nếu bạn sử dụng thực thi Fibonacci heap của hàng đợi ưu tiên, thì thuật toán của Dijkstra sẽ hiệu quả hơn khi sử dụng phím giảm.

Tóm lại, sử dụng phím giảm, cộng với hàng đợi ưu tiên tốt, có thể làm mất thời gian chạy tiệm cận của Dijkstra vượt quá những gì có thể nếu bạn tiếp tục làm đồ uống và đồ uống. Bên cạnh điểm này, một số thuật toán nâng cao hơn, chẳng hạn như Thuật toán Đường dẫn Ngắn nhất của Gabow, sử dụng thuật toán Dijkstra làm chương trình con và dựa nhiều vào việc thực hiện khóa giảm. Họ sử dụng thực tế là nếu bạn biết trước khoảng cách hợp lệ, bạn có thể xây dựng một hàng đợi ưu tiên siêu hiệu quả dựa trên thực tế đó.

Hy vọng điều này sẽ hữu ích!

Answer 2

Năm 2007, đã có một bài báo nghiên cứu sự khác biệt về thời gian thực hiện giữa việc sử dụng phiên bản khóa giảm và phiên bản chèn.Xem http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Kết luận cơ bản của họ không sử dụng phím giảm cho hầu hết các biểu đồ. Đặc biệt đối với đồ thị thưa thớt, khóa không giảm nhanh hơn đáng kể so với phiên bản giảm khóa. Xem giấy để biết thêm chi tiết.