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

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.
Nội dung trích xuất từ tài liệu:
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 BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ PHAN NHƯ MINH 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 Chuyên ngành: Hệ thống thông tin LUẬN VĂN THẠC SĨ KỸ THUẬT Hà Nội - Năm 2011 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI HỌC VIỆN KỸ THUẬT QUÂN SỰCán bộ hướng dẫn chính: PGS.TS. Nguyễn Thiện LuậnCán bộ chấm phản biện 1: ...................................................................Cán bộ chấm phản biện 2: ...................................................................Luận văn thạc sĩ được bảo vệ tại: HỘI ĐỒNG CHẤM LUẬN VĂN THẠC SĨ HỌC VIỆN KỸ THUẬT QUÂN SỰ Ngày tháng năm 2011HỌC VIỆN KỸ THUẬT QUÂN SỰ CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG SAU ĐẠI HỌC Độc lập – Tự do – Hạnh phúc Hà Nội, ngày 12 tháng 05 năm 2011 NHIỆM VỤ LUẬN VĂN THẠC SĨHọ tên học viên: PHAN NHƯ MINH Giới tính: NamNgày, tháng, năm sinh: 23/09/1978 Nơi sinh: Vĩnh PhúcChuyên ngành: Hệ thống thông tin Mã số: 60 48 05I- 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ấtvới dữ liệu mờ dạng khoảng.II- NHIỆM VỤ VÀ NỘI DUNG: Trên cơ sở nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụngcho 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ạngkhoảng. Đặt ra và giải quyết bài toán tìm đường đi ngắn nhất với độ dài cáccung là số mờ dạng khoảngIII- NGÀY GIAO NHIỆM VỤ: 12/10/2010IV- NGÀY HOÀN THÀNH NHIỆM VỤ: 05/05/2011V- CÁN BỘ HƯỚNG DẪN: PGS.TS. Nguyễn Thiện Luận CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN QL CHUYÊN NGÀNHPGS.TS. Nguyễn Thiện Luận Nội dung và đề cương luận văn thạc sĩ đã được Hội đồng chuyên ngành thông qua. Ngày tháng năm 2011 TRƯỞNG PHÒNG SĐH TRƯỞNG KHOA QL NGÀNH MỤC LỤC TrangTrang 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 ............................................ 16 1.1.6. Bài toán người phát thư Trung Hoa:.................................... 20 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: ............................................................. 29 1.2.3. Bài toán áp dụng: ................................................................. 30 1.2.3. Thuật toán Floyd:................................................................. 33 Chương 2 LÝ THUYẾT MỜ ...