Làm thế nào để cập nhật các yếu tố ưu tiên trong một đống cho thuật toán của Prim?

Question

Tôi đang nghiên cứu Thuật toán của Prim. Có một phần bên trong mã, đỉnh tiếp theo cắt ngang sẽ đến tập hợp các đỉnh thuộc về MST. Trong khi làm điều đó, chúng ta cũng phải 'cập nhật tất cả các đỉnh trong tập khác nằm cạnh đỉnh khởi động'. Đây là một ảnh chụp từ CLRS:

Phần thú vị nằm trong dòng không. 11. Nhưng kể từ khi chúng tôi đang sử dụng một đống ở đây, chúng tôi có quyền truy cập vào chỉ các yếu tố tối thiểu, phải (heap[0])? Vậy làm thế nào để chúng ta tìm kiếm và cập nhật các đỉnh từ heap mặc dù chúng không phải là tối thiểu và do đó chúng ta biết chúng ở đâu ngoại trừ tìm kiếm tuyến tính?

Answer 1

Có thể tạo hàng đợi ưu tiên hỗ trợ hoạt động được gọi là phím giảm, ưu tiên của đối tượng hiện có trong hàng đợi ưu tiên và giảm mức độ ưu tiên đó. Hầu hết các phiên bản của hàng đợi ưu tiên đi kèm với các thư viện hiện có không hỗ trợ hoạt động này, nhưng có thể xây dựng nó theo nhiều cách.

Ví dụ, cho một đống nhị phân, bạn có thể duy trì một cấu trúc dữ liệu phụ trợ ánh xạ từ các phần tử đến vị trí của chúng trong đống nhị phân. Sau đó bạn sẽ cập nhật việc triển khai heap nhị phân sao cho bất cứ khi nào trao đổi được thực hiện, cấu trúc dữ liệu phụ trợ này được cập nhật. Sau đó, để thực hiện khóa giảm, bạn có thể truy cập vào bảng, tìm vị trí của nút trong heap nhị phân, sau đó tiếp tục bước bong bóng.

Heaps dựa trên con trỏ khác như đống nhị thức hoặc heaps Fibonacci hỗ trợ rõ ràng hoạt động này (vùng Fibonacci được thiết kế đặc biệt cho nó). Bạn thường có một bản đồ phụ từ các đối tượng đến nút mà họ chiếm trong heap và sau đó có thể rewire các con trỏ để di chuyển nút xung quanh trong heap.

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

Answer 2

Pointers cho phép hiệu quả tổng hợp cấu trúc dữ liệu

Bạn có một cái gì đó như thế này (sử dụng mã giả C++):

class Node 
    bool visited 
    double key 
    Node* pi 
    vector<pair<Node*, double>> adjacent //adjacent nodes and edge weights 
    //and extra fields needed for PriorityQueue data structure 
    // - a clean way to do this is to use CRTP for defining the base 
    // PriorityQueue node class, then inherit your graph node from that 

class Graph 
    vector<Node*> vertices 

CRTP: http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

Hàng đợi ưu tiên Q trong thuật toán chứa các hạng mục loại Node*, trong đó ExtractMin giúp bạn số Node* với số tiền tối thiểu key.

Lý do bạn không phải thực hiện bất kỳ tìm kiếm tuyến tính nào là vì khi bạn nhận được u = ExtractMin(Q), bạn có Node*. Vì vậy, u->adjacent mang lại cho bạn cả hai số v trong G.Adj[u] và w(u,v) trong thời gian const cho mỗi nút liền kề. Vì bạn có một con trỏ v đến nút hàng đợi ưu tiên (mà làv), bạn có thể cập nhật vị trí của nó trong hàng đợi ưu tiên trong thời gian logarit mỗi nút liền kề (với hầu hết các trường của một hàng đợi ưu tiên).

Để đặt tên cho một số cấu trúc dữ liệu cụ thể, chức năng DecreaseKey(Q, v) được sử dụng bên dưới có độ phức tạp logarit cho vùng Fibonnaci và đống ghép đôi (khấu hao).

• Ghép đống: http://en.wikipedia.org/wiki/Pairing_heap
  • Không quá khó để viết mã chính mình - Wikipedia có hầu hết các mã nguồn
• Fibonacci đống: http://en.wikipedia.org/wiki/Fibonacci_heap giả

More-bê tông cho thuật toán

MstPrim(Graph* G) 
    for each u in G->vertices 
     u->visited = false 
     u->key = infinity 
     u->pi = NULL 
    Q = PriorityQueue(G->vertices) 
    while Q not empty 
     u = ExtractMin(Q) 
     u->visited = true 
     for each (v, w) in u->adjacent 
      if not v->visited and w < v->key 
       v->pi = u 
       v->key = w 
       DecreasedKey(Q, v) //O(log n)