intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Cuchoami2510 | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST
Báo xấu
17
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. TOÁN RỜI RẠC Chương 6: Đồ thị Giảng viên: ThS. Trần Quang Khải
  2. 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
  3. 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
  4. Đồ 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
  5. Đồ 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
  6. Đồ 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. Example Toán rời rạc: 2011-2012 Chương 6: Đồ thị 15
  16. Example Toán rời rạc: 2011-2012 Chương 6: Đồ thị 16
  17. 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
  18. 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
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
550=>1