Banner-dethi-1090_logo1
Banner-dethi-1090_logo2

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

    ViOLET Chào mừng năm học mới

    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