Thạc Sĩ 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

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






Tóm tắt luận văn
Họ và tên học viên: Phan Như Minh
Lớp: Hệ thống thông tin Khoá: 21
Cán bộ hướng dẫn: PGS.TS. Nguyễn Thiện Luận
Tê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.
Tóm tắt: Nghiêu cứu ứng dụng logic mờ trong tin học và thuật toán tìm đường đi ngắn nhất có cung là trọng số xác định từ đó xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất có cung với số mờ dạng khoảng.
Đưa ra mô phỏng thuật toán giải bài toán tìm đường đi ngắn nhất với trọng số là số mờ dạng khoảng từ giải thuật Dijsktra và lý thuyết mờ quy hoạch tuyến tính dạng khoảng.
Ø Kiểm tra hàm liên thuộc.
Ø Tìm ra tất cả các đường đi từ các cung mờ.
Ø Tìm ra độ dài cung mờ nhỏ nhất giá trị Lmin.
Ø Tính ra độ tương tự.
Ø Tìm ra đường đi ngắn nhất từ các cung mờ với độ tương tự cao nhất.