Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất

Mục đích của luận án là phát triển một số thuật toán gần đúng dạng metaheuristic giải bài toán MRCST cho chất lượng lời giải tốt hơn so với các thuật toán có cùng cỡ thời gian tính hoặc đòi hỏi thời gian tính ít hơn khi so sánh với các thuật toán có chất lượng lời giải tương đương hoặc đưa ra lời giải tốt nhất mới cho một số bộ dữ liệu thực nghiệm chuẩn.
Nội dung trích xuất từ tài liệu:
Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHAN TẤN QUỐC CÁC THUẬT TOÁN GẦN ĐÚNG GIẢI BÀI TOÁNCÂY KHUNG VỚI CHI PHÍ ĐỊNH TUYẾN NHỎ NHẤT Chuyên ngành: Khoa học máy tính Mã số: 62480101TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội –2015 Công trình được hoàn thành tại: Trường Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: PGS.TS. Nguyễn Đức Nghĩa Phản biện 1: PGS.TS. Nguyễn Xuân Hoài Phản biện 2: TS. Nguyễn Đức Dũng Phản biện 3: TS. Hoàng Tuấn Hảo Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ cấp Trường họp tại Trường Đại học Bách khoa Hà Nội Vào hồi …….. giờ, ngày ….. tháng ….. năm ………Có thể tìm hiểu luận án tại: 1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam MỞ ĐẦUTối ưu hóa mạng liên quan đến nhiều lĩnh vực như toán ứng dụng,khoa học máy tính, vận trù học, kỹ thuật, mạng truyền thông,…Nhiều bài toán thực tế trong lĩnh vực mạng truyền thông, chẳng hạnnhư các bài toán Optimal Communication Spanning Trees, SteinerMinimal Trees, Bounded Diameter Minimum Spanning Trees -BDMST, Minimum Routing Cost Spanning Trees thuộc lớp bài toánNP-khó hoặc NP-đầy đủ.Minimum Routing Cost Spanning Trees-MRCST là một bài toán tốiưu đồ thị nổi tiếng và có nhiều ứng dụng quan trọng trong lĩnh vựcmạng truyền thông và trong tin sinh học. Bài toán này lần đầu tiênđược giới thiệu bởi T. C. Hu vào năm 1974 qua công trình“Optimum communication spanning trees”.Mô hình toán học của bài toán MRCST có thể phát biểu như sau:Cho G là một đồ thị vô hướng liên thông có chi phí định tuyếnkhông âm trên cạnh. Giả sử T là một cây khung của G. Chi phí địnhtuyến cho mỗi cặp đỉnh trên T được định nghĩa là tổng các chi phíđịnh tuyến trên các cạnh của đường đi đơn nối chúng trên T và chiphí định tuyến của T được định nghĩa là tổng của tất cả các chi phíđịnh tuyến giữa mọi cặp đỉnh của T. Bài toán MRCST đặt ra là tìmmột cây khung có chi phí định tuyến nhỏ nhất trong số tất cả cáccây khung của G. Bài toán MRCST đã được chứng minh thuộc lớpbài toán NP-khó.Việc đề xuất thuật toán dạng metaheuristic giải bài toán MRCST cóý nghĩa quan trọng, một mặt, nhằm giải quyết những bài toán ứngdụng thực tiễn vừa nêu; mặt khác, còn là cơ sở để giải quyết nhữngbài toán cây khung tối ưu dạng NP-khó khác trên đồ thị.Bài toán MRCST đã thu hút được sự quan tâm nghiên cứu của nhiềunhà khoa học trong hơn bốn mươi năm qua. Hiện nay đã có hàngloạt thuật toán giải bài toán MRCST được đề xuất theo các hướng:tìm lời giải đúng, tìm lời giải gần đúng cận tỉ lệ, heuristic,metaheuristic.Mục đích của luận án là phát triển một số thuật toán gần đúng dạngmetaheuristic giải bài toán MRCST cho chất lượng lời giải tốt hơnso với các thuật toán có cùng cỡ thời gian tính hoặc đòi hỏi thờigian tính ít hơn khi so sánh với các thuật toán có chất lượng lời giải 1tương đương hoặc đưa ra lời giải tốt nhất mới cho một số bộ dữ liệuthực nghiệm chuẩn.Các kết quả nghiên cứu của luận án đã được công bố ở 4 bài báo tạpchí và 2 bài báo hội nghị chuyên ngành.Luận án được trình bày trong 5 chương.Luận án đã phân tích được ưu nhược điểm của từng thuật toán đốivới từng loại dữ liệu thực nghiệm cụ thể và qua đó định hướngphạm vi áp dụng cho từng thuật toán đề xuất.Phụ lục của luận án ghi nhận kết quả thực nghiệm của các côngtrình nghiên cứu liên quan cho đến thời điểm hiện tại. Chương 1. TỔNG QUANChương này giới thiệu tổng quan về bài toán MRCST, các ứng dụngcủa bài toán MRCST, khảo sát các thuật toán giải bài toán MRCST,các tiêu chí đánh giá chất lượng một thuật toán giải gần đúng và hệthống dữ liệu thực nghiệm chuẩn được sử dụng cho bài toánMRCST.1.1.BÀI TOÁN MRCST1.1.1.Một số định nghĩaCho G = (V(G), E(G)) là một đồ thị vô hướng, liên thông, có trọngsố không âm trên cạnh; trong đó V(G) là tập gồm n đỉnh, E(G) làtập gồm m cạnh, w(e) là trọng số của cạnh e, e  E(G).Định nghĩa 1.1 (Chi phí định tuyến giữa một cặp đỉnh). Cho T =(V(T), E(T)) là một cây khung của G, trọng số trên cạnh e được hiểulà chi phí định tuyến của cạnh e, ta gọi chi phí định tuyến (routingcost) của một cặp đỉnh (u,v) trên T, ký hiệu là dT(u,v), là tổng chiphí định tuyến của các cạnh trên đường đi đơn (duy nhất) nối đỉnh uvới đỉnh v trên cây T.Định nghĩa 1.2 (Chi phí định tuyến của một cây khung). Cho T =(V(T), E(T)) là một cây khung của G, chi phí định tuyến của T, kýhiệu là C(T), là tổng chi phí định tuyến giữa mọi cặp đỉnh thuộc câyT, tức là: C (T )   u ,vV (T ) dT (u, v). ...