Bài giảng Toán rời rạc - Chương 6: Đồ thị - Phần 3

Giảng viên: ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 6: Đồ thị Toán rời rạc: 2011-2012 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. Chương 6: Đồ thị 2 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Bài toán tìm đường đi ngắn nhất Chương 6 Toán rời rạc: 2011-2012 Đồ thị có trọng số Chương 6: Đồ thị 4 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 Đồ thị có trọng số Liên quan:  Thời gian.  Khoảng cách.  Chi phí.  Chương 6: Đồ thị 5 Toán rời rạc: 2011-2012 Đồ 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. Chương 6: Đồ thị 6 Toán rời rạc: 2011-2012 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). Chương 6: Đồ thị 7 Toán rời rạc: 2011-2012 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. Chương 6: Đồ thị 8 Toán rời rạc: 2011-2012 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 +∞. Chương 6: Đồ thị 9 Toán rời rạc: 2011-2012 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. Chương 6: Đồ thị 10 Toán rời rạc: 2011-2012 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 Chương 6: Đồ thị 11 Edsger Wybe Dijkstra 1930 - 2002 Toán rời rạc: 2011-2012 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. Chương 6: Đồ thị 12 Toán rời rạc: 2011-2012 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. Chương 6: Đồ thị 13 Toán rời rạc: 2011-2012 Thuật toán Dijsktra Ví dụ: tìm đường đi từ s đến t. Chương 6: Đồ thị 14 Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 15 Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 16 Toán rời rạc: 2011-2012 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. Chương 6: Đồ thị 17 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Bài toán TSP Chương 6 Toán rời rạc: 2011-2012 Bài toán TSP Chương 6: Đồ thị 19 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 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. Chương 6: Đồ thị 20 Toán rời rạc: 2011-2012 Bài toán TSP Ứng dụng:  Lập quy hoạch. Ngành hậu cần.  Sản xuất vi mạch.  Xử lý chuỗi DNA. . Chương 6: Đồ thị 21 Toán rời rạc: 2011-2012 Bài toán TSP Chương 6: Đồ thị 22 Toán rời rạc: 2011-2012 Bài toán TSP  Lược sử nghiên cứu (với sự trợ giúp của máy tính):  1950s, 1960s: phổ biến ở châu Âu, châu Mỹ.  Phương pháp mặt phẳng cắt.  1972: Richard Karp chứng minh độ khó của TSP.  Cuối 1970s, đầu 1980s: giải được trường hợp 2392 thành phố (Grötschel, Padberg, Rinaldi).  2005: Cook và cộng sự đã giải được một trường hợp có 33810 thành phố, xuất phát từ một bài toán thiết kế vi mạch. Chương 6: Đồ thị 23 Toán rời rạc: 2011-2012 Bài toán TSP Giải pháp: Các phương pháp “xấp xỉ”, là sự kết hợp giữa:  Lý thuyết đồ thị.  Phương pháp tối ưu hóa trong KHMT: • Giải thuật di truyền. • Các giải thuật tìm kiếm cục bộ (local search): Tabu search, giải thuật leo đồi, giải thuật mô phỏng luyện kim, đế chế đàn kiến, Chương 6: Đồ thị 24 Toán rời rạc: 2011-2012 Bài toán TSP Chương 6: Đồ thị 25 Toán rời rạc: 2011-2012 Bài tập – Giải thuật Dijsktra Chương 6: Đồ thị 26 1 2 a  z? Toán rời rạc: 2011-2012 Bài tập – Giải thuật Dijsktra Chương 6: Đồ thị 27 3 4 f  c? f  g? Toán rời rạc: 2011-2012 Bài tập – Giải thuật Dijsktra Chương 6: Đồ thị 28 5 a  z?