Tìm kiếm Đề thi, Kiểm tra

Quảng cáo

Quảng cáo

Quảng cáo

Hướng dẫn sử dụng thư viện

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (04) 66 745 632
  • 0166 286 0000
  • contact@bachkim.vn

lý thuyết hệ thống- DHQN-Thầy Nguyễn Hồng Anh

Nhấn vào đây để tải về
Hiển thị toàn màn hình
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Nguyễn Văn Bạo
Ngày gửi: 15h:29' 27-01-2015
Dung lượng: 96.0 KB
Số lượt tải: 6
Số lượt thích: 0 người

Bài tập: Tìm đường đi ngắn nhất
x1->x3
 x1->x4
x1->x5

x1
x2
x3
x4
x5
x6

x1

10

5
8


x2
10

20
16



x3

20

25
22
12

x4
5
16
25

2


x5
8

22
2

14

x6


12

14



Bài giải:
Bước 1: với mọi xi ≠ x1, p = x1
X1 nhận được nhãn cố định
1) Vòng 1:
Bước 2: tất cả các nhãn đều tạm thời
Đầu tiên với x2: 


Bước 3: tương ứng với x4
Bước 4: nút x4 nhận được nhãn cố định
L(x4) = 5+; p = x4
Bước 5:Còn có những nút mang nhãn tạm thời, vì vậy chuyển sang bước 2.
2) Vòng 2:
Bước 2:  x1đã được dán nhãn cố định
Tất cả các nhãn đều là tạm thời



Bước 3: tương ứng với x5
Bước 4: nút x5 nhận được nhãn cố định
l(x5) = 7+ ; p = x5
Bước 5: còn nhãn tạm thời, chuyển sang bước 2.
3) Vòng 3
Bước 2: x1,x4 đã được dán nhãn cố định
=21
Bước 3: tương ứng với x2
Bước 4: nút x2 nhận nhãn cố định
L(x2) = 10+ ; p = x2
Bước 5: còn nhãn tạm thời, chuyển sang bước 2.
4) Vòng 4
Bước 2: x4 đã được dán nhãn cố định
=30
Bước 3: tương ứng với x6
Bước 4: nút x6 nhận nhãn cố định
L(x6) = 21+ ; p = x6
Bước 5: còn nhãn tạm thời, chuyển sang bước 2.
5) Vòng 5
Bước 2: x5 đã được dán nhãn cố định
=30
Bước 3: tương ứng với x3
Bước 4: nút x3 nhận nhãn cố định
L(x3) = 30+ ; p = x3













Để tìm lộ trình ngắn nhất từ S đến các nút còn lại ta dùng quá trình lùi liên tiếp theo quan hệ:
l(x’i) + C(x’i, xi) = l(xi)
Trong đó x’i là nút trực tiếp nằm trước nút xi trên đường đi ngắn nhất từ S đến xi.
Tìm đường ngắn nhất từ x1->x3
Ta sữ dụng quá trình lùi liên tiếp, đặt xi = x3 tìm nút x’3 nằm trực tiếp trước nút x3 trên đường ngắn nhất từ nút x1 đến x3; x’3 cần thỏa mãn điều kiện:
l(x’3) + C(x’3, x3) = l(x3) = 30
Đỉnh x4,x2 thỏa mãn đk này
Tiếp tục sử dụng quá trình lùi liên tiếp với xi = x4. Nút x’4 nằm trực tiếp trước x4 trên đường ngắn nhất từ x1 đến x3 cấn thỏa mãn đk:
l(x’4) + C(x’4, x4) = l(x4) = 5
Đỉnh duy nhất thỏa mãn điều kiện này là x1
Ta thấy đường từ x2 về x1 lớn hơn x4 về x1 . Như vậy đường ngắn nhất từ x1 đến x3 là: x1 –x4 – x3.
Tìm đường ngắn nhất từ x1->x4
Ta sữ dụng quá trình lùi liên tiếp, đặt xi = x4 tìm nút x’4 nằm trực tiếp trước nút x4 trên đường ngắn nhất từ nút x1 đến x4; x’4 cần thỏa mãn điều kiện:
l(x’3) + C(x’3, x3) = l(x3) = 5
Đỉnh duy nhất thỏa mãn điều kiện này là x1
Như vậy đường ngắn nhất từ x1 đến x4 là: x1 –x4
Tìm đường ngắn nhất từ x1->x5
Ta sữ dụng quá trình lùi liên tiếp, đặt xi = x5 tìm nút x’5 nằm trực tiếp trước nút x5trên đường ngắn nhất từ nút x1 đến x5; x’5 cần thỏa mãn điều kiện:
l(x’5) + C(x’5, x5) = l(x5) = 7
Đỉnh x4 thỏa mãn đk này
Tiếp tục sử dụng quá trình lùi liên tiếp với xi = x4. Nút x’4 nằm trực tiếp trước x4 trên đường ngắn nhất từ x1 đến x5 cấn thỏa mãn đk:
l(x’4) + C(x’4, x4) = l(x4) = 5
Đỉnh duy nhất thỏa mãn điều kiện này là x1
Như vậy đường ngắn nhất từ x1 đến x3 là: x1 –x4 – x5.


 
Gửi ý kiến