Luận văn Thạc sĩ Hệ thống thông tin: Tối ưu hóa truy vấn tìm đường ngắn nhất trên đồ thị động quy mô lớn

Nội dung của luận văn sẽ được tổ chức như sau: Chương 1) Giới thiệu về cơ sở lý thuyết, các vấn đề liên quan đến đồ thị và bài toán tìm đường đi ngắn nhất trong đồ thị. Chương 2) Trình bày bài toán, cách tiếp cận và phương pháp giải quyết bài toán. Chương 3) Thực nghiệm và kết quả đạt được. Cuối cùng kết luận và đưa ra hướng phát triển tiếp theo.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Hệ thống thông tin: Tối ưu hóa truy vấn tìm đường ngắn nhất trên đồ thị động quy mô lớn ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM HẢI ĐĂNG TỐI ƯU HÓA TRUY VẤN TÌM ĐƯỜNG NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG QUY MÔ LỚN LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN Hà Nội – 2016 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRANG PHỤ BÌA PHẠM HẢI ĐĂNG TỐI ƯU HÓA TRUY VẤN TÌM ĐƯỜNG NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG QUY MÔ LỚN Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Nguyễn Ngọc Hóa Hà Nội – 2016 2 LỜI CẢM ƠN Để có thể hoàn thiện được luận văn thạc sỹ của mình, trước tiên, tôi xin bày tỏ lòng biết ơn sâu nhất tới thầy – PGS.TS. Nguyễn Ngọc Hóa (bộ môn Các hệ thống thông tin – trường Đại học Công nghệ – Đại học Quốc gia Hà Nội). Sự gần gũi, khích lệ và nhiệt tình hướng dẫn của thầy là nguồn động lực rất lớn đối với tôi trong suốt thời gian thực hiện luận văn. Tôi cũng xin được gửi lời cảm ơn chân thành nhất tới tất cả các thầy, cô trong bộ môn Các hệ thống thông tin, cũng như các thầy, cô trong khoa Công nghệ thông tin – trường Đại học Công nghệ – Đại học Quốc gia Hà Nội đã nhiệt tình giảng dạy, cung cấp cho chúng tôi những kiến thức, kinh nghiệm không chỉ trong học tập mà còn trong cuộc sống hàng ngày. Đồng thời tôi cũng xin được gửi lời cảm ơn đến cha mẹ, người thân trong gia đình, các bạn học viên, đồng nghiệp đã giúp đỡ, động viên, tạo điều kiện tốt nhất cho tôi trong suốt khóa học tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội để tôi có thể hoàn thiện tốt luận văn thạc sỹ của mình. Hà Nội, tháng 11 năm 2016 Học viên Phạm Hải Đăng 3 LỜI CAM ĐOAN Tôi xin cam đoan luận văn tốt nghiệp “Tối ưu hóa truy vấn tìm đường ngắn nhất trên đồ thị động quy mô lớn” là công trình nghiên cứu thực sự của bản thân, được thực hiện trên cơ sở nghiên cứu lý thuyết, kiến thức chuyên ngành, nghiên cứu khảo sát tình hình thực tiễn và dưới sự hướng dẫn khoa học của PGS.TS. Nguyễn Ngọc Hóa. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn. Những phần tham chiếu, trích dẫn trong luận văn đều được nêu rõ trong phần tài liệu tham khảo. Các số liệu, kết quả trình bày trong luận văn là hoàn toàn trung thực. Nếu sai tôi xin chịu hoàn toàn trách nhiệm và chịu mọi kỷ luật của khoa và nhà trường đề ra. Hà Nội, tháng 11 năm 2016 Học viên Phạm Hải Đăng 4 MỤC LỤC TRANG PHỤ BÌA ................................................................................................ 1 LỜI CẢM ƠN ....................................................................................................... 2 LỜI CAM ĐOAN ................................................................................................. 3 MỤC LỤC ............................................................................................................ 4 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ........................................... 6 DANH MỤC CÁC BẢNG ................................................................................... 7 DANH MỤC CÁC HÌNH VẼ .............................................................................. 8 Giới thiệu chung.................................................................................................... 9 Động lực nghiên cứu ......................................................................................... 9 Mục tiêu và nội dung chính của luận văn ......................................................... 9 Tổ chức luận văn ............................................................................................... 9 Chương 1: Cơ sở lý thuyết và các vấn đề liên quan ........................................... 10 1.1. Đồ thị ....................................................................................................... 10 1.1.1. Giới thiệu đồ thị ................................................................................ 13 1.1.2. Một số thuật ngữ cơ bản ................................................................... 14 1.1.3. Biểu diễn đồ thị ................................................................................. 15 1.1.4. Các thuật toán tìm kiếm trên đồ thị và ứng dụng .............................. 18 1.2. Bài toán tìm đường đi ngắn nhất .............................................................. 21 1.3. Tổng kết chương ...................................................................................... 27 Chương 2: Bài toán, cách tiếp cận và phương pháp giải quyết .......................... 28 2.1. Định nghĩa bài toán .................................................................................. 28 2.2. Các vấn đề liên quan ................................................................................ 29 2.3. Cách tiếp cận giải quyết bài toán ............................................................. 34 2.4. Cấu trúc dữ liệu phù hợp.......................................................................... 34 2.5. Tối ưu quá trình thêm và xóa cạnh của đồ thị.......................................... 37 2.5.1. Thêm mới một cạnh .......................................................................... 37 2.5.2. Xóa đi một cạnh ................................................................................ 39 2.6. Tối ưu quá trình xử lý truy vấn tìm đường ngắn nhất .............................. 40 2.6.1. Cải thiện thuật toán tìm đường đi ngắn nhất từ hai hướng ............... 40  ...