Xem mẫu
- TOÁN RỜI RẠC
Chương 6:
Đồ thị
Giảng viên: ThS. Trần Quang Khải
- Nội dung (phần 3)
1. Bài toán tìm đường đi ngắn nhất:
Giải thuật Dijsktra.
2. Giới thiệu bài toán TSP.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 2
- Chương 6
Bài toán tìm đường đi
ngắn nhất
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc: 2011-2012
- Đồ thị có trọng số
Weighted graph
Là đồ thị mà mỗi cạnh được gán một số (nguyên
hoặc thực) với ngụ ý nào đó.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 4
- Đồ thị có trọng số
Liên quan:
Thời gian.
Khoảng cách.
Chi phí.
…
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 5
- Đồ thị có trọng số
Độ dài (length) của đường đi có trọng số:
Tổng trọng số của các cạnh trên đường đi.
Đường đi ngắn nhất: đường đi có độ dài nhỏ
nhất trong số các đường đi có thể có.
Lưu ý:
Khác với khái niệm độ dài là tổng số cạnh.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 6
- Bài toán tìm đường đi ngắn nhất
Shortest path problems:
Tìm ra đường đi có độ dài nhỏ nhất giữa 2 đỉnh
s (source) và t (destination).
Các thuật toán:
Dijsktra (giữa 2 đỉnh, không cạnh âm).
Floyd-Warshall (mọi cặp đỉnh).
Bellman-Ford (có cạnh âm).
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 7
- Bài toán tìm đường đi ngắn nhất
Nhận xét:
Có thể bỏ bớt các cạnh bội, chỉ giữ lại cạnh có trọng
số nhỏ nhất.
Có thể bỏ đi các khuyên có trọng số không âm.
Nếu có khuyên trọng số âm: có thể không có lời giải.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 8
- Bài toán tìm đường đi ngắn nhất
Biểu diễn đồ thị dạng ma trận kề:
aij =
Trọng số cạnh nhỏ nhất nối i đến j nếu có.
0 nếu không có cạnh nối i đến j nếu có.
Phải kiểm tra giá trị 0 trong ma trận.
Tổng quát hơn: thay 0 bằng +∞.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 9
- Nguyên lý Bellman
Gọi P là đường đi ngắn nhất từ i đến j, k là một
đỉnh nằm giữa i và j trên P thì:
Đường đi P1 từ i đến k cũng chính là đường đi ngắn
nhất từ i đến k.
Đường đi P2 từ k đến j cũng chính là đường đi ngắn
nhất từ k đến j.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 10
- Thuật toán Dijsktra
Ý tưởng:
Giải thuật Dijsktra chủ yếu
dựa trên nguyên lý gán
nhãn (labeling).
Tác giả: Edsger Dijkstra
Công bố: 1959
Edsger Wybe Dijkstra
1930 - 2002
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 11
- Thuật toán Dijsktra
Điều kiện:
Đồ thị G = (V, E).
Có hướng hoặc vô hướng.
Không có cạnh âm.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 12
- Thuật toán Dijsktra
Ý tưởng:
Dựa trên một dãy các bước lặp:
Bắt đầu từ tập chỉ chứa đỉnh xuất phát a.
Mỗi bước lặp thêm 1 đỉnh vào tập đỉnh đã ghé qua.
Gán nhãn cho các đỉnh trong mỗi bước lặp:
Nhãn của đỉnh w là độ dài của đường đi ngắn nhất
từ a đến nó (thông qua các đỉnh trong tập đã thăm).
Bước lặp tiếp:
Chọn một đỉnh đã được gán nhãn (có giá trị nhãn
nhỏ nhất) để tiếp tục.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 13
- Thuật toán Dijsktra
Ví dụ: tìm đường đi từ s đến t.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 14
- Example
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 15
- Example
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 16
- Thuật toán Dijsktra
Cài đặt thuật toán Dijsktra:
Trình bày - Nhóm (thời gian: tuần 9):
1. Liêu Tấn Đạt - MSSV: 1131200001.
2. Hoàng Trung Thành - MSSV: 1131200016.
3. Lê Trọng Hà - MSSV: 1131200006.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 17
- Chương 6
Bài toán TSP
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc: 2011-2012
- Bài toán TSP
The travelling salesman problem:
“Cho một danh sách các thành phố và
khoảng cách đường đi giữa mỗi cặp thành
phố, tìm đường đi ngắn nhất có thể sao cho
mỗi thành phố được ghé qua đúng một lần”.
Defined by W. R. Hamilton (1800s)
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 19
- Bài toán TSP
The travelling salesman problem:
Bài toán “lớn+khó” (NP-hard) trong tối ưu tổ hợp
(combinatorial optimization).
Được nghiên cứu trong vận trù học (operations research) và
khoa học máy tính lý thuyết (theoretical computer science).
Nguồn gốc thật sự: unknown.
Toán rời rạc: 2011-2012 Chương 6: Đồ thị 20
nguon tai.lieu . vn
