Cách lấy đường dẫn trong thuật toán "tìm kiếm chi phí thống nhất"?

Question

Tôi đã trải qua thuật toán của tìm kiếm chi phí thống nhất và mặc dù tôi có thể hiểu toàn bộ quy trình xếp hàng ưu tiên nhưng tôi không thể hiểu giai đoạn cuối cùng của thuật toán.

Nếu chúng ta xem at this graph, sau khi áp dụng thuật toán, tôi sẽ có khoảng cách tối thiểu cho mỗi nút, nhưng giả sử tôi muốn biết đường dẫn từ A đến G (giống như ví dụ), tôi sẽ tính toán như thế nào?

Answer 1

Thông thường bạn bắt đầu với tổng chi phí vô hạn cho mỗi nút chưa được khám phá. Sau đó, bạn có thể điều chỉnh thuật toán một chút để lưu người tiền nhiệm:

for each of node's neighbours n 
    if n is not in explored 
     if n is not in frontier 
      frontier.add(n) 
      set n's predecessor to node 
     elif n is in frontier with higher cost 
      replace existing node with n 
      set n's predecessor to node 

Sau đó bạn chỉ có thể kiểm tra trình tự của người tiền nhiệm, bắt đầu từ mục tiêu của mình.

Answer 2

Visit để biết thêm https://www.youtube.com/watch?v=9vNvrRP0ymw

Insert the root into the queue 
While the queue is not empty 
     Dequeue the maximum priority element from the queue 
     (If priorities are same, alphabetically smaller path is chosen) 
     If the path is ending in the goal state, print the path and exit 
     Else 
      Insert all the children of the dequeued element, with the cumulative costs as priority