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