tailieunhanh - Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p7

Tham khảo tài liệu 'giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình poisson với tham số p7', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Bảng Nút init. A 0 B 5 C 1 E 11 D 6 A 0 - A 0 - B 0 - C 0 - E 0 - D 0 - B B - 5 A C 5 A E 4 C D 4 C B 4 C F C - 1 A 1 A D 1 A B 1 A F 1 A D - - 6 B 6 B 6 B 6 B E - - 11 B 11 B 11 B 11 B F - - - - 13 E 10 D B 4 F 10 E 10 D 5 F 9 A 0 - F 0 - E 0 - D 0 - F 0 - B 4 C E 4 C D 4 C 4 C 4 C C 1 A D 1 A 1 A 1 A 1 A D 5 B 5 B 5 B 5 B 5 B E 10 B 10 B 10 B 10 B 10 B F 10 D 10 D 10 D 9 D 9 D Thuật toán có thể viết như sau array n -Bellman n root dist dcl dist n n pred n sp_dist n in_queue n scan_queue queue void - Scan i in queue i - FALSE for j 1 to n if sp_dist j sp_diat i dist i j sp_dist j - sp_diat i dist i j pred j - i if not in_queue j Push scan_queue j in_queue j - TRUE sp_dist - INFINITY pred - -1 in queue -FALSE initialize_queue scan_queue sp_dist root - 0 Push scan_queue root in queue -TRUE 67 while not Empty scan_queue i - Pop scan_queue Scan i return pred Một hàng đợi chuẩn được sử dụng quá trình trên. Có thể sử dụng dãy in_queue để theo dõi nút nào đang hiện có trong hàng đợi. Theo quá trình được viết ở trên thì thuật toán Bellman là một quá trình tìm kiếm theo chiều rộng. Người ta đã chứng minh được rằng trong trường hợp xấu nhất một nút được quét n-1 lần. Vì vậy quá trình quét trong trường hợp xấu nhất có độ phức tạp là O n với n là số lượng các nút. Từ đó suy ra rằng độ phức tạp của toàn bộ thuật toán là O n3 . Tuy nhiên trong thực tế các nút không thường xuyên được quét lại nhiều lần. Trong hầu hết các trường hợp thực tế số lần quét trung bình trên một nút là rất nhỏ tối đa là 3 hoặc 4 ngay cả khi mạng có hàng ngàn nút. Nếu bậc trung bình của nút nhỏ điều này thường xảy ra trong các mạng thực tế thì thời gian cho việc tìm kiếm nút chưa quét bé nhất là phần có ảnh hưởng nhất của thuật toán Dijkstra. Vì vậy trong thực tế thuật toán Bellman được xem là nhanh hơn so với thuật toán Dijkstra mặc dù độ phức tạp trong trường hợp xấu nhất của thuật toán Bellman lớn hơn. Tương tự có thể cải tiến độ phức tạp của thủ tục Scan bằng cách duy trì một danh sách kề cận cho