Bài giảng Toán rời rạc: Bài 9 - TS. Nguyễn Văn Hiệu

Bài 9 "Bài toán đường đi ngắn nhất trên đồ thị" thuộc bài giảng Toán rời rạc cung cấp cho các bạn những kiến thức về bài toán đường đi ngắn nhất trên đồ thị, thuật toán Ford-Bellman, thuật toán Dijkstra, thuật toán Floyd.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Bài 9 - TS. Nguyễn Văn Hiệu BÀI 9BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn 1Nội dung• Giới thiệu 0• Bài toán 8 A 4• Thuật toán Ford-Bellman 2• Thuật toán Dijkstra 8 7 2 1 3 B C D• Thuật toán Floyd 3 9 5 8 2 5 E F Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2Giới thiệu Có nhiều cách đi giữa hai điểm  Chọn ngắn nhất theo d(u,v)=? nghĩa cự ly,  Chọn đường đi nhanh nhất theo nghĩa thời gian G = (V , E) mi j =1  Chọn đường đi rẽ nhất theo chi phí,  Chọn gửi dữ liệu nhanh mi j >0 nhất. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3Bài toán Cho G = (V, E) là đồ thị có trọng lượng. s ∈ V và t ∈ V. Hãy tìm đường đi có tổng trọng lượng nhỏ • Đường đi ngắn nhất từ Etna đến nhất từ s đến t. Oldtown là: Etna – Bangor – Orono – OldTown • Đường đi ngắn nhất từ Hermae đến Etna là: Hermae – Hampdea – Bangor - Etna Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4Bài toánĐiều kiện bài toán Phải tồn tại đường đi từ s  Trong đồ thị không tồn tại đến t: chu trình âm  Đồ thị vô hướng liên thông  Đồ thị có hướng: không tồn  Đồ thị có hướng liên thông tại chu trình âm. mạnh  Đồ thị vô hướng: không tồn  Đồ thị vô hướng, s và t nằm tại cạnh âm. trong cùng một thành phần liên thông  Đồ thị có hướng, có tồn tại đường đi từ s đến tBài toánNhận xét Nếu v là đỉnh trung gian trên đường đi ngắn nhất từ s đến t thì đường đi từ s đến v phải là ngắn nhất và đường đi từ v đến t cũng phải là ngắn nhất. Do đó, để tối ưu, người ta mở rộng bài toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại của đồ thị.Thuật toán Ford-BellmanÝ tưởng• Dò tìm bằng cách thử đi qua các đỉnh trung gian Nếu phát hiện đường đi qua đỉnh trung gian ngắn hơn đường đi hiện tại thì sẽ cập nhật đường đi mới, đồng thời chỉnh sửa các thông tin liên quan.• Sử dụng hai mảng – Mảng d[v]: Lưu trữ độ dài đường if d[v] > d[u] + c[u,v] then đi ngắn nhất hiện tại từ s đến v. { d[v] = d[u] + c[u,v]; – Mảng T[v]: Lưu trữ đỉnh nằm Truoc[v] = u; } trước v trên đường đi ngắn nhất hiện tại.Thuật toán Ford-Bellman• * Khởi tạo * for v  V d[v]:= c[s,v]; T[v]:=s;• * Bắt đầu * d[s]:=0; for k:=1; k ≤ n-2 k 1 2 3 4 5 for v  V{ s} for u  V 0,1 1,1  ,1  ,1 3,1 if d[v] > d[u] + c[u,v] d[v]:=d[u]+c[u,v]; 1 0,1 1,1 4,2 4,2 -1,3 T[v]:=u; 2 0,1 1,1 4,2 3,5 -1,3 3 0,1 1,1 4,2 3,5 -1,3Thuật toán Ford-Bellman k 1 2 3 4 5 6 0,1 1,1  ,1  ,1 ,1 ,1 1 0,1 1,1 6 ,2 3 ,2 7,4 7,3 2 0,1 1,1 4 ,4 3 ,2 7,4 5,3 3 0,1 1,1 4 ,4 3 ,2 6,6 5,3S=1 4 0,1 1,1 4 ,4 3 ,2 6,6 5,3Thuật toán Ford-BellmanNhận xét: Cải tiến:• Áp dụng được cho mọi • Không thể cải tiến tốt trường hợp hơn cho trường hợp• Chi phí tính toán lớn do tổng quát dùng 3 vòng lặp lồng nhau • Chỉ có thể làm tốt hơn• Thường lãng phí một số bước sau cùng cho một số trường hợp riêng ...