Thuật toán Dijkstra Vs Tìm kiếm Chi phí Đồng nhất (Thời gian comlexity)

Question

Câu hỏi của tôi như sau: Theo các nguồn khác nhau, thuật toán của Dijkstra không là gì ngoài một biến thể của Tìm kiếm Chi phí Đồng nhất. Chúng ta biết rằng thuật toán của Dijkstra tìm đường đi ngắn nhất giữa một nguồn và tất cả các đích (nguồn đơn). Tuy nhiên, chúng ta luôn có thể sửa đổi Dijkstra để tìm đường đi ngắn nhất giữa trạng thái START và trạng thái GOAL (khi mục tiêu được xuất hiện từ hàng đợi ưu tiên, chúng ta chỉ dừng lại); nhưng làm như vậy, trường hợp xấu nhất sẽ vẫn tìm đường đi ngắn nhất từ ​​START đến tất cả các nút khác (giả sử mục tiêu là nút xa nhất trong biểu đồ).

Nếu chúng ta thực hiện thuật toán Dijkstra sử dụng heap ưu tiên min, thời gian chạy sẽ là O (V log V + E), trong đó E là số cạnh và V số đỉnh.

Vì Tìm kiếm chi phí thống nhất giống với Dijkstra (triển khai hơi khác nhau), thì thời gian chạy của UCS phải giống với Dijkstra, phải không? Tuy nhiên, theo lớp AI của tôi, Tìm kiếm chi phí thống nhất là số mũ ở trường hợp xấu nhất và phải mất O (b ^{1 + [C */ε]}), trong đó C * là chi phí của giải pháp tối ưu. (b là hệ số phân nhánh)

Làm cách nào để cả hai thuật toán giống nhau trong khi chúng có thời gian chạy khác nhau? Là thời gian chạy như nhau, nhưng cách chúng ta nhìn vào nó là khác nhau?

tôi sẽ đánh giá cao sự giúp đỡ của bạn :) :) Cảm ơn bạn

Answer 1

Là lần chạy như nhau, nhưng cách chúng ta nhìn vào nó là khác nhau?

Có. Tìm kiếm chi phí đồng nhất có thể được sử dụng trên các đồ thị vô cùng lớn, mà thuật toán gốc của Dijkstra sẽ không bao giờ chấm dứt. Trong những tình huống như vậy, không sử dụng định nghĩa độ phức tạp theo các điều kiện V và E vì cả hai có thể là vô hạn và kết quả là hình lớn-O vô nghĩa.