Bài giảng Toán rời rạc: Chương 6.3 - ThS. Trần Quang Khải

Bài giảng Toán rời rạc: Chương 6.3 cung cấp cho người học những kiến thức như: Bài toán tìm đường đi ngắn nhất; Giới thiệu bài toán TSP. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 6.3 - ThS. Trần Quang KhảiTOÁ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ảiToán rời rạc: 2011-2012 Đồ thị có trọng số Weighted graphLà đồ thị mà mỗi cạnh được gán một số (nguyênhoặ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 ExampleToán rời rạc: 2011-2012 Chương 6: Đồ thị 15 ExampleToá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ảiToá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ànhphố, tìm đường đi ngắn nhất có thể sao chomỗ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ị ...