Tóm tắt 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 /> 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 /> TÓM TẮT LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN<br /> <br /> Hà Nội – 2016<br /> <br /> Giới thiệu chung<br /> Động lực nghiên cứu<br /> Hiện nay, chúng ta đang sống trong thời đại bùng nổ về công nghệ<br /> công tin cũng như bùng nổ về các mạng xã hội. Một số mạng điển hình<br /> như mạng xã hội (Facebook, Twitter), mạng sinh học, mạng phân tán nội<br /> dung, mạng lưới giao thông, mạng thông tin… có số lượng dữ liệu tăng<br /> nhanh chóng mặt. Để giải quyết những thách thức về mặt dữ liệu lớn trên,<br /> có rất nhiều phương pháp tiếp cận, trong đó phương pháp tiếp cận dựa trên<br /> đồ thị được cho là trực quan và phù hợp nhất [8]. Với việc sử dụng lý<br /> thuyết đồ thị, với các đỉnh biểu diễn các thực thể và các cạnh biểu diễn<br /> mối liên hệ giữa chúng. Trong đồ thị, tìm đường đi (ngắn nhất) là vấn đề<br /> tìm sự kết nối giữa hai đỉnh của một đồ thị và đảm bảo đường đi đó là ngắn<br /> nhất dựa trên một số yêu cầu cho trước. Đây là vấn đề nền tảng và cơ bản<br /> được áp dụng trong rất nhiều ứng dụng thực tế như tìm đường đi ngắn nhất<br /> giữa hai địa điểm sử dụng GPS hay tìm mối liên kết giữa hai người trên<br /> mạng xã hội [6]. Vấn đề này bình thường rất đơn giản, nhưng trong bối<br /> cảnh số lượng các đỉnh, cạnh của đồ thị rất lớn (vài triệu đỉnh) và thay đổi<br /> nhanh (thêm cạnh, bớt cạnh), làm thế nào để tối ưu hóa quá trình tìm đường<br /> đi ngắn nhất là một thách thức lớn [21].<br /> Mục tiêu và nội dung chính của luận văn<br /> Với mục tiêu trên, luận văn này sẽ trình bày giải pháp để cải thiện<br /> hiệu năng quá trình tối ưu truy vấn trên đồ thị động, quy mô lớn có hướng,<br /> không trọng số. Phương pháp tối ưu dựa trên các ý tưởng: cấu trúc dữ liệu<br /> phù hợp, tối ưu không gian tìm kiếm và cài đặt phù hợp.<br /> Tổ chức luận văn<br /> Nội dung của luận văn sẽ được tổ chức như sau:<br /> Mở đầu: Đặt vấn đề<br /> Chương 1: Giới thiệu về cơ sở lý thuyết, các vấn đề liên quan đến đồ<br /> thị và bài toán tìm đường đi ngắn nhất trong đồ thị.<br /> Chương 2: Trình bày bài toán, cách tiếp cận và phương pháp giải<br /> quyết bài toán.<br /> Chương 3: Thực nghiệm và kết quả đạt được.<br /> Kết luận chung: Kết luận và đưa ra hướng phát triển tiếp theo.<br /> 1<br /> <br /> Chương 1. Cơ sở lý thuyết và các vấn đề liên quan<br /> 1.1. Đồ thị<br /> Trước khi tìm hiểu về lý thuyết đồ thị, chúng ta cùng xét một ví dụ về<br /> một mạng xã hội nhỏ [7] sau:<br /> <br /> Hình 1.1: Mạng xã hội<br /> <br /> Đây là ví dụ cơ bản về đồ thị. Tên người chính là các đỉnh, và mỗi<br /> đường liên kết giữa hai người chính là các cạnh. Chúng ta thường biểu<br /> diễn sự liên kết giữa hai đỉnh u và v bởi cặp (u, v). Bởi vì quan hệ “biết<br /> nhau” ở đây là quan hệ hai chiều, nên đây là ví dụ của đồ thị vô hướng.<br /> Trong đồ thị vô hướng thì cạnh (u, v) tương tự như cạnh (v, u). Trong đồ<br /> thị có hướng, thì quan hệ “biết nhau” không còn là hai chiều nữa, một<br /> người A biết người B nhưng chưa chắc người B đã biết người A.<br /> Nhìn trên đồ thị, An và Sơn có thể biết nhau thông qua Linh và Hạnh.<br /> Đây đường đi ngắn nhất giữa hai đỉnh An và Sơn. Chúng ta đánh dấu<br /> đường đi ngắn nhất này trong Hình 1.2.<br /> <br /> Hình 1.2: Đường đi trong mạng xã hội<br /> <br /> Khi đường đi xuất phát từ một đỉnh và quay lại chính nó, chúng ta gọi<br /> đó là một chu trình. Ví dụ từ An Bình tới Cường, Linh rồi cuối cùng quay<br /> 2<br /> <br /> lại An. Thực ra, có chu trình ngắn hơn đó là từ An qua Bình tới Linh rồi<br /> quay lại An.<br /> <br /> Hình 1.3: Chu trình trong mạng xã hội<br /> <br /> Trong mạng xã hội, chúng ta có thể sử dụng một trọng số để xác định<br /> mức độ biết nhau giữa hai người. Một ví dụ cụ thể khác về đồ thị có trọng<br /> số chính là bản đồ đường đi. Giả sử tất cả đều là đường hai chiều, thì bản<br /> đồ đường đi này cũng là một đồ thị vô hướng, giá trị trọng số chính là số<br /> biểu diễn khoảng cách giữa các thành phố. Ví dụ Hình 1.4 mô tả khoảng<br /> cách giữa một số tỉnh thành phía Bắc nước Việt Nam.<br /> <br /> Hình 1.4: Bản đồ khoảng cách một số tỉnh thành phía Bắc<br /> <br /> Trong trường hợp bản đồ đường đi, nếu chúng ta muốn tìm đường đi<br /> ngắn nhất giữa các vị trí, chúng ta phải tìm kiếm đường đi qua các vị trí<br /> trung gian sao cho tổng trọng số là nhỏ nhất. Ví dụ ở bản đồ Hình 1.4,<br /> đường đi ngắn nhất từ Hà Nội tới Hạ Long, sẽ qua Hải Dương, Hải Phòng.<br /> Tổng cộng đoạn đường đi này có chiều dài 163km.<br /> Mối quan hệ giữa hai đỉnh không phải lúc nào cũng là hai chiều. Lấy<br /> ví dụ, trong bản đồ đường đi, chúng ta có thể gặp đường đi một chiều. Để<br /> 3<br /> <br /> biểu diễn sự có hướng này, các cạnh được thêm dấu mũi tên ở cuối và đồ<br /> thị này được gọi là đồ thị có hướng. Ví dụ Hình 1.5 mô tả một mạng xã<br /> hội có hướng. Dễ nhận thấy, đồ thị ở Hình 1.5 không có chu trình, khi đó<br /> đồ thị được gọi là có hướng không chu trình.<br /> <br /> Hình 1.5: Mạng xã hội có hướng<br /> <br /> Như chúng ta thấy, đồ thị có rất nhiều ứng dụng trong biểu diễn các<br /> sự vật, mối quan hệ giữa các sự vật đó trong thế giới thực. Phần tiếp theo,<br /> luận văn sẽ trình bày một số lý thuyết nền tảng về đồ thị.<br /> 1.1.1. Giới thiệu đồ thị<br /> Đồ thị (G), kí hiệu là G = (V, E) bao gồm một tập các đỉnh (V) và tập<br /> các cạnh (E). Trong đó mỗi cạnh E nối giữa hai đỉnh thuộc tập các đỉnh<br /> (V) và được kí hiệu là E = (u, v) (Đỉnh u nối với đỉnh v). Ví dụ về đồ thị<br /> được đưa ra ở Hình 1.6.<br /> <br /> Hình 1.6: Đồ thị<br /> <br /> Đồ thị được phân loại dựa như sau: Đơn đồ thị vô hướng, Đa đồ thị<br /> vô hướng, Giả đồ thị vô hướng, Đơn đồ thị có hướng, Đa đồ thị có hướng.<br /> 1.1.2. Một số thuật ngữ cơ bản<br /> Bậc của đỉnh<br /> Bậc của đỉnh v trong đồ thị G = (V, E) ký hiệu deg(v) là số các cạnh<br /> liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của<br /> 4<br /> <br />