TAILIEUCHUNG - Giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p7

Giả thiết hệ thống mạng không được kiểm soát, nghĩa là tất cả các gói tin đều có thể truy cập tài nguyên của mạng, và bộ đệm tại các nút X, Y và Z có thể được sử dụng bởi bất kỳ gói tin nào. Giả thiết môi trường truyền không có lỗi, lúc này các gói tin không bị sai nhưng vẫn có thể phải được truyền lại nếu nó bị nút mạng hủy do không còn dung lượng bộ đệm để lưu gói tin tạm thời trước khi xử lý. Giả thiết khi gói tin bị mất. | 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

• Kĩ thuật Viễn thông
• kỹ thuật cơ điện
• thủ thuật cơ điện
• giáo trình xây dựng
• kỹ năng học cơ điện
• phương pháp học cơ điện
• thủ thuậgiáo trình kế toán
• kỹ thuật kế toán
• thủ thuật kế toán
• phương pháp học kế toán
• bí quyết học kế toánt cơ điện
• giáo trình cơ điện