Luận Văn Nghiên cứu xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mở dạng khoảng

MỤC LỤC

Trang

Trang phụ bìa

Nhiệm vụ luận văn

Mục lục

Tóm tắt luận văn

Danh mục hình vẽ

Danh mục bảng:

MỞ ĐẦU 1

Chương I

LÝ THUYẾT ĐỒ THỊ VÀ THUẬT TOÁN GIẢI BÀI

TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT CÓ TRỌNG SỐ XÁC ĐỊNH


1.1. Khái niệm cơ bản về lý thuyết đồ thị 5

1.1.1. Các định nghĩa về đồ thị: 5

1.1.2. Bậc của đồ thị. 8

1.1.3. Biểu diễn đồ thị bằng ma trận 10

1.1.4. Tính liên thông 11

1.1.5. Đường đi Euler và đồ thị Euler 17

1.1.6. Bài toán người phát thư Trung Hoa: 21

1.1.7. Đường đi Hamilton và đồ thị Hamilton 23

1.2. Đồ thị có trọng số và bài toán tìm đường đi ngắn nhất 28

1.2.1. Bài toán tìm đường đi ngắn nhất: 29

1.2.2. Thuật toán Dijkstra: 30

1.2.3. Bài toán áp dụng: 31

1.2.3. Thuật toán Floyd: 33






Chương 2

LÝ THUYẾT MỜ VÀ ỨNG DỤNG

BÀI TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG KHOẢNG

2.1. Khái niệm tập mờ 36

2.1.1. Định nghĩa tập mờ 36

2.1.2. Một số khái niệm của tập mờ 38

2.1.3. Các ví dụ về tập mờ 39

2.2. Các phép toán trên tập mờ 41

2.2.1. Các phép toán trên tập hợp. 41

2.2.2. Khái niệm hàm liên thuộc 42

2.3. Mệnh đề và công thức 43

2.3.1. Khái niệm mệnh đề 43

2.3.2. Các kí hiệu 43

2.3.3. Các phép toán trên mệnh đề 44

2.3.4. Các tính chất 47

2.4. Suy luận xấp xỉ dựa trên logic mờ 48

2.5. Ứng dụng logic mờ xây dựng bài toán tối ưu mờ 50

2.5.1. Tối ưu mờ 50

Chương 3

XÂY DỰNG GIẢI THUẬT GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT BIỂU DIỄN CUNG ĐƯỜNG ĐI LÀ SỐ MỜ DẠNG KHOẢNG


3.1. Mô hình bài toán 55

3.2. Ví dụ 56

3.3. Bài toán tìm đường đi ngắn nhất có các cung mờ 56

3.3.1. Xây dựng tập mờ 57

3.3.2. Miền xác định của tập mờ: 57

3.3.3. Miền tin cậy của tập mờ 58

3.3.4. Miền biên của tập mờ 58

3.4. Khái niệm số mờ 58

3.4.1. Định nghĩa số mờ 58

3.4.2. Số mờ dạng tam giác: 59

3.4.3. Số mờ dạng hình thang: 59

3.5. Một số phương pháp giải quyết bài toán 61

3.5.1. Phép toán thực hiện trên số mờ tam giác. 61

3.6. Ví dụ áp dụng bài toán: 62

Chương 4

CÀI ĐẶT THỬ NGHIỆM

4.1. Một số giao diện của chương trình 64

4.1.1. Giao diện chính của chương trình 64

4.1.2. Các bước thực hiện chương trình. 64

4.1.3. Các chức năng chính của chương trình 64

4.1.3. Các chức năng chính của chương trình 65

4.2. Cài đặt – thử nghiệm 69

4.3. Đánh giá hiệu quả thuật toán đã xây dựng 71

KẾT LUẬN VÀ KIẾN NGHỊ 72

1. Kết luận 72

2. Kiến nghị 73

TÀI LIỆU THAM KHẢO 74


DANH MỤC HÌNH VẼ


Hình 1.1 Đơn đồ thị, giả đồ thị 6

Hình 1.2. Đồ thị có hướng và Đa đồ thị có hướng 7

Hình 1.3. Bậc của đồ thị 8

Hình 1.4. Bậc của đồ thị có hướng 9

Hình 1.5. Biểu diễn đồ thị bằng ma trận liền kề 10

Hình 1.6. Biểu diễn đồ thị bằng ma trận liền kề 10

Hình 1.7. Biểu diễn đồ thị bằng ma trận liên thuộc 11

Hình 1.8. Biểu diễn đường đi sơ cấp 12

Hình 1.9. Biểu diễn đồ thị G và G’ 12

Hình 1.10. Biểu diễn các đỉnh cắt là v, w, s và các cầu là (x,v), (w,s). 13

Hình 1.11. Đồ thị G là liên thông mạnh đồ thị G’ là liên thông yếu 15

Hình 1.12. Biểu diễn Đường đi Euler và đồ thị Euler 17

Hình 1.13. Đồ thị Euler và đồ thị nửa Euler 18

Hình 1.14. Xây dựng đường đi 18

Hình 1.15. Xây dựng đường đi 19

Hình 1.16. Xây dựng đường đi 20

Hình 1.17. Xây dựng đường đi GT và G 22

Hình 1.18. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị 24

Hình 1.19. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị 25

Hình 1.20. Đồ thị Hamilton 27

Hình 1. 21. Đồ thị phân đôi 28

Hình 1.22. Tìm đường đi ngắn nhất d(a,v) của đồ thị 29





Hình 2.1. Tập mờ 34

Hình 2. 2. Đồ thị hàm liên thuộc của tập mờ 35

Hình 2.3. Miền của tập mờ 37

Hình 2.4. Đồ thị đánh giá 38

Hình 2. 5. Đồ thị đánh giá nhiệt độ 38

Hình 2.6. Ví dụ hàm liên thuộc 41

Bảng 2.7. Mô hình suy diễn xấp sỉ 48

Bảng 1.8. Suy luận xấp xỉ 46

Bảng 1.9. Bảng điều kiện suy diễn xấp sỉ 47

Hình 3.1. Đồ thị G(u,v) có hướng 54

Hình 3.2. Miền biên của tập mờ 56

Hình 3.3. Số mờ dạng tam giác 57

Hình 3.4. Số mờ dạng hình thang 58

Hình 3.4.Biểu diễn số mờ dạng hình thang 58

Hình 3.5.Tìm đường đi ngắn nhất 60

Hình 4.1. Giao diện chính của chương trình 62

Hình 4.2. Các bước thực hiện 62

Hình 4.3. Mô phỏng thuật toán 63

Hình 4.4. Chọn số đỉnh 63

Hình 4.5. Chọn cung đường đi 64

Hình 4.6. Nhập các cung a, b, c và thông báo 64

Hình 4.7. Tìm tất cả các đường đi 65

Hình 4.7. Tính giá trị Lmin 65

Hình 4.8. Bảng độ tương tự 66

Hình 4.9. Bảng thông báo kết quả tìm được 66

Hình 4.10. Chọn đỉnh nhập dữ liệu 67

Hình 4.11. Kết quả kiểm tra xây dựng hàm liên 67

Hình 4.12. Kết quả tất cả các đường đi 68

Hình 4.13. Bảng kết quả tìm Lmin 68

Hình 4.14. Bảng kết quả độ tương tự 68

Hình 4.15. Bảng kết quả đường đi ngắn nhất 68




DANH MỤC BẢNG


Bảng 1.1. Kết quả tính toán theo thuật toán Dijkstra 31

Bảng 2.1. Phép phủ định 42

Bảng 2.2. Phép hoặc 43

Bảng 2.3. Phép nhân logic 43

Bảng 2.4. Phép cộng XOR 44

Bảng 2.5. Phép kéo theo 44

Bảng 2.6. Phép tương đương 45

Bảng 2.7. Bảng chân lý 45

Bảng 2.8. Suy luận xấp xỉ 46

Bảng 2.9. Bảng điều kiện suy diễn xấp sỉ 47

Bảng 3.1. Độ tương tự giữa hai số mờ 60







MỞ ĐẦU

1. Lý do chọn đề tài

Trong những năm gần đây, các phương pháp tối ưu hoá ngày càng được áp dụng sâu rộng và hiệu quả vào các ngành giao thông vận tải, mạng viễn thông, kinh tế, kỹ thuật, công nghệ thông tin và các ngành khoa học khác. Các phương pháp tối ưu là công cụ đắc lực giúp người làm quyết định có những giải pháp tốt nhất về định lượng và định tính.

Một trong những lớp bài toán tối ưu đầu tiên được nghiên cứu là thuật toán giải bài toán tìm đường đi ngắn nhất có trọng số xác định.

Bài toán tìm đường đi ngắn nhất là vấn đề quan trọng trong lý thuyết đồ thị, nó đã được nghiên cứu từ lâu và có nhiều ứng dụng trong nhiều ngành khoa học nói chung, khoa học máy tính và hệ thống thông tin nói riêng. Nhiều giải thuật (Dijkstra, Bellman-Ford, Floyd .) đã được phát triển để tìm đường đi ngắn nhất và ngày nay đã được nhiều nhà nghiên cứu nhằm cải tiến xây dựng giải thuật giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng.

Bài toán tìm đường đi ngắn nhất cũng được phát triển rộng rãi và trở thành một chuyên ngành toán học từ những năm 1950. Giải đáp những câu hỏi đặt ra mà tìm đường đi ngắn nhất với các cạnh có trọng số xác định.

Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có thuật toán do E. Dijkstra, nhà toán học người Hà Lan, đề xuất năm 1959. Trong báo cáo này mà tôi sẽ trình bày, người ta giả sử đồ thị là vô hướng các trọng số là dương.

Chỉ cần thay đổi đôi chút là có thể giải được bài toán tìm đường đi ngắn nhất trong đồ thị có hướng.

Phương pháp của thuật toán Dijkstra là: Xác định tuần tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn.


Nhưng câu hỏi cần đặt ra là nếu trọng số đã cho được biểu diễn là một cung mở thuộc khoảng ( a,b) thì sao?

Nếu trọng số có khoảng nằm ở đường biên trái thì có thể các phương án là chấp nhận được.

Nếu trọng số có khoảng nằm ở đường biên phải thì khó có thể chấp nhận được đó là đường đi tối ưu, do vậy ta chưa thể khẳng định được đó là đường đi ngắn nhất vì giả sử bên cạnh cung đó còn có các cung khác liền kề và có trọng số gần như tương đương thì sao?

Nếu áp dụng giải thuật ( Dijkstra, Bellman-Ford, Floyd .) thì rất khó mới có thể tìm ra được theo hướng đi ngắn nhất và tối ưu.

Ví dụ : Trong một chuyến đi du lịch từ thành phố A đến thành phố E

Vẫn biết rằng : A có thể đi hai đường.

A đi qua B rồi lại từ B đi đến D sau đó đến E.

A đi qua C rồi lại từ C đi đến D sau đó đến E.

Giả sử : Đường đi từ A B và A C là một cung được biểu diễn là một cung mờ dạng khoảng thì sao?

Để giải quyết bài toán trên: Nhờ ứng dụng logic mờ trong tin học. Bài toán tối ưu bài toán quy hoạch tuyến tính dạng khoảng sẽ giúp ta giải quyết vấn đề này.

Một phương án chấp nhận được được gọi là nghiệm hữu hiệu nếu không tồn tại một phương án chấp nhận được khác tốt hơn nó, ít nhất là theo một mục tiêu, còn các mục tiêu khác không tồi hơn.

Tuy nhiên, khối lượng tính toán của các thuật toán này tăng nhanh khi kích thước của bài toán tìm đường đi ngắn nhất với các cung khoảng mờ cho đường đi là quá lớn (tức số ràng buộc của miền chấp nhận, số chiều của không gian quyết định và số hàm mục tiêu) tăng.

Trong những năm gần đây nhiều nhà toán học đã chuyển sang nghiên cứu giải quyết bài toán tìm đường đi ngắn nhất có trọng số là các cung mờ dạng khoảng. Trong báo cáo này, tôi sẽ trình bày thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng.

Vì những lý do trên, tôi chọn đề tài “Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng.” làm đề tài nghiên cứu của mình.

2. Mục đích nghiên cứu

Nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng.

Giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng.

3. Phạm vi nghiên cứu

Trên cơ sở nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng.

Dừng lại ở khâu Tìm đường đi ngắn nhất với các dữ liệu về có trọng số dạng khoảng.

4. Phương pháp nghiên cứu

Nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng.

Giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng.

Xây dựng phần mềm thử nghiệm.

Phân tích đánh giá kết quả để ứng dụng thực tế.



Nội dung của luận văn được trình bày trong 4 chương.

Chương 1. Lý thuyết đồ thị và thuật toán giải bài toán tìm đường đi ngắn nhất có trọng số xác định

Chương 2. Lý thuyết mờ và ứng dụng bài toán quy hoạch tuyến tính dạng khoảng.

Chương 3. Xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất biểu diễn cung đường đi là số mờ dạng khoảng.

Chương 4. Cài đặt thử nghiệm.