Chương 1: Trình bày tổng quan về cơ sở lý thuyết bài toán Cây Steiner nhỏ nhất với các nội dung: Một số định nghĩa, định lý cơ bản liên quan; các dạng của bài toán Cây Steiner nhỏ nhất; sơ lược một số hướng tiếp cận. Tiếp theo, khảo sát một số thuật toán metaheuristic giải bài toán Cây Steiner nhỏ nhất, cụ thể như: Giới thiệu sơ đồ một số thuật toán metaheuristic thường gặp như: thuật toán local search, thuật toán leo đồi, thuật toán tìm kiếm lân cận biến đổi, thuật toán bầy ong; các tiêu chí đánh giá chất lượng thuật toán metaheuristic; khảo sát kết quả một số thuật toán heuristic, metaheuristic hiện biết giải bài toán Cây Steiner nhỏ nhất; định hướng ứng dụng bài toán Cây Steiner nhỏ nhất cho thiết kế hệ thống mạng và cuối cùng là giới thiệu hệ thống dữ liệu thực nghiệm chuẩn và mở rộng cho bài toán. - Chương 2: Đề xuất 2 thuật toán heuristic mới SPT-Steiner, PD-Steiner và 2 thuật toán heuristic cải tiến i-SPT-Steiner, i-PD-Steiner giải bài toán Cây Steiner nhỏ nhất. Thuật toán heuristic SPT-Steiner dựa trên ý tưởng cơ bản của bài toán tìm cây đường đi ngắn nhất và thuật toán heuristic PD-Steiner là sự kết hợp ý tưởng chính của thuật toán Prim và Dijkstra.
Hai thuật toán heuristic cải tiến i-SPT-Steiner 6 và i-PD-Steiner dựa trên ý tưởng thay thế thuật toán Dijkstra bằng thuật toán Dial (một biến thể của thuật toán Dijkstra) trong việc tìm đường đi ngắn nhất. Các thuật toán đề xuất đã được cài đặt thực nghiệm trên hệ thống dữ liệu thực nghiệm chuẩn và mở rộng là các đồ thị thưa có kích thước lên đến 100000 đỉnh. Kết quả thực nghiệm cho thấy, thuật toán đề xuất hiệu quả hơn một số thuật toán giải gần đúng đã được công bố trên một số bộ dữ liệu, nhất là đối với các đồ thị thưa có kích thước lớn. - Chương 3: Đề xuất 3 thuật toán metaheuristic giải bài toán Cây Steiner nhỏ nhất; các thuật toán này lần lượt dựa trên khung thuật toán metaheuristic gồm: Thuật toán Bees, Hill climbing search và Variable neighborhood search.
Luận án cũng đề xuất một số chiến lược tìm kiếm lân cận cho bài toán Cây Steiner nhỏ nhất. Các thuật toán đề xuất này đã được cài đặt thực nghiệm trên hệ thống dữ liệu thực nghiệm chuẩn; kết quả thực nghiệm cho thấy thuật toán đề xuất cho lời giải với chất lượng tốt hơn một số thuật toán heuristic và metaheuristic hiện biết trên một số bộ dữ liệu. Luận án cũng phân tích ưu nhược điểm của từng thuật toán cụ thể và qua đó định hướng phạm vi áp dụng vào thực tế cho từng thuật toán đề xuất. Trong phần Kết luận, luận án trình bày những kết quả đạt được và định hướng phát triển cho nghiên cứu trong tương lai khi áp dụng kết quả luận án vào thực tiễn.
TỔNG QUAN VỀ BÀI TOÁN CÂY STEINER NHỎ NHẤT VÀ ĐỊNH HƯỚNG ỨNG DỤNG CHO THIẾT KẾ HỆ THỐNG MẠNG Chương này trình bày tổng quan những vấn đề nghiên cứu của luận án. Thứ nhất tổng quan về bài toán Cây Steiner nhỏ nhất. Thứ hai tiếp cận thuật toán metaheuristic giải bài toán Cây Steiner nhỏ nhất. Thứ ba khảo sát một số thuật toán tiêu biểu giải bài toán Cây Steiner nhỏ nhất.
Thứ tư định hướng ứng dụng bài toán Cây Steiner nhỏ nhất cho thiết kế hệ thống mạng và cuối cùng là đề xuất lựa chọn dữ liệu thực nghiệm. Từ kết quả nghiên cứu tổng quan và khảo sát phân tích, đánh giá một số thuật toán tiêu biểu giải bài toán Cây Steiner nhỏ nhất, cho thấy hướng tiếp cận bằng thuật toán metaheuristic là rất khả thi và hiệu quả. Chương này được tổng hợp từ các công trình [CT1], [CT6] và [CT8] trong danh mục các công trình nghiên cứu của tác giả. Một số định nghĩa Định nghĩa 1.
Cây Steiner Cho G = (V(G), E(G)) là một đơn đồ thị vô hướng liên thông, có trọng số 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 với e E(G). Cho L là tập con các đỉnh của V(G), cây T đi qua tất cả các đỉnh trong L được gọi là Cây Steiner ứng với tập L trên đồ thị G. Tập L được gọi là tập terminal, các đỉnh thuộc tập L được gọi là đỉnh terminal. Đỉnh thuộc cây T mà không thuộc tập L được gọi là đỉnh Steiner [14].
Chi phí Cây Steiner 8 Cho T = (V(T), E(T)) là một Cây Steiner của đồ thị G. Chi phí của cây T, ký hiệu là C(T), là tổng trọng số của các cạnh thuộc cây T, tức là C(T) = eE(T) w(e) [14]. Cây Steiner nhỏ nhất Cho đồ thị G được mô tả như trên, bài toán tìm Cây Steiner có chi phí nhỏ nhất được gọi là bài toán Cây Steiner nhỏ nhất (Steiner minimal trees problem – SMT); hoặc được gọi ngắn gọn là bài toán Cây Steiner (Steiner trees problem) [14][16]. SMT là bài toán lý thuyết đồ thị thuộc dạng tối ưu tổ hợp [5][3].
Trong trường hợp tổng quát, SMT đã được chứng minh thuộc lớp NP-hard [14][52]. Khác với bài toán cây khung nhỏ nhất (Minimum spanning tree problem); Cây Steiner chỉ cần đi qua tất cả các đỉnh thuộc tập terminal L và có thể thêm một số đỉnh khác nữa thuộc tập V(G) chứ không nhất thiết phải đi qua tất cả các đỉnh của đồ thị G [14]. Định lý về số đỉnh Steiner Cho đồ thị G và tập terminal L, Cây Steiner T của L có p đỉnh thì số đỉnh Steiner của T không vượt quá p - 2 [1]. Cạnh cầu Steiner Cho đồ thị G và tập terminal L, cạnh euv được gọi là cạnh cầu Steiner của G nếu khi loại cạnh euv thì tập các đỉnh terminal L không cùng thuộc về một thành phần liên thông [1].
Đồ thị rút gọn Steiner Cho đồ thị G và tập terminal L, G’ được gọi là đồ thị rút gọn Steiner của G nếu số đỉnh và số cạnh của G’ nhỏ hơn hoặc bằng số đỉnh và số cạnh của G và trong G’ tồn tại ít nhất một Cây Steiner nhỏ nhất ứng với tập terminal L của đồ thị G. Để ngắn gọn, trong định nghĩa này từ đồ thị được hiểu là đơn đồ thị, vô hướng, liên thông và có trọng số không âm. Cho một đồ thị G có 9 đỉnh và 10 cạnh như Hình 1.1 và tập terminal L = {2, 8, 9}. Minh họa một đồ thị G vô hướng liên thông có trọng số Khi đó, Cây Steiner nhỏ nhất tìm được ứng với tập terminal L trên đồ thị G là T có V(T) = {2, 3, 4, 6, 8, 9} và E(T) = {(2, 3), (3, 4), (4, 6), (4, 8), (6, 9)} như được minh họa ở Hình 1.2; cây T có tập đỉnh Steiner là {3, 4, 6} và có chi phí là 25.
Cây Steiner nhỏ nhất ứng với tập terminal L của đồ thị G 1. Một số dạng của bài toán Cây Steiner nhỏ nhất Bài toán Cây Steiner nhỏ nhất hiện được nghiên cứu ở các dạng sau đây: - Thứ nhất là bài toán Cây Steiner với khoảng cách Euclide. Trong mặt phẳng tọa độ OXY, cho đồ thị G = (V(G), E(G)) và tập đỉnh L V. Cần tìm cây đi qua tất 10 cả các đỉnh thuộc tập L và có tổng độ dài là nhỏ nhất, cho phép thêm vào một số điểm phụ (điểm Steiner) được lấy từ các đỉnh thuộc V.
Khoảng cách Euclide giữa hai điểm P1 (x1, y1) và P2 (x2, y2) là độ dài đoạn thẳng nối hai đỉnh P1, P2 [11][16][33][41][63]. - Thứ hai là bài toán Cây Steiner với khoảng cách chữ nhật. Trong mặt phẳng tọa độ OXY cho đồ thị G = (V(G), E(G)) và tập đỉnh L V. Hãy tìm cây đi qua tất cả các đỉnh thuộc tập L và có tổng độ dài là nhỏ nhất, cho phép thêm vào một số điểm phụ (điểm Steiner) được lấy từ các đỉnh thuộc V.
Khoảng cách chữ nhật (rectilinear distance) giữa hai điểm P1 (x1, y1) và P2 (x2, y2) là d (P1, P2) = |x1 x2| + |y1 y2| [32][35][87]. - Thứ ba là bài toán Cây Steiner với khoảng cách ngẫu nhiên. Khoảng cách giữa các đỉnh là trọng số của các cạnh; và đây là phạm vi nghiên cứu về bài toán Cây Steiner nhỏ nhất của tác giả trong đề tài này. Có hai trường hợp đặc biệt đối với bài toán SMT là giải được trong thời gian đa thức; đó là khi L = V(G) và khi |L| = 2.
Tổng quan các nghiên cứu liên quan đến bài toán Cây Steiner nhỏ nhất Hiện tại, trong nước đã có một số công trình nghiên cứu về bài toán Cây Steiner nhỏ nhất như của tác giả Vũ Đình Hòa [1], Trần Lê Thủy [7],. Trên thế giới đã có nhiều công bố liên quan đến bài toán Cây Steiner nhỏ nhất; trong số đó có luận án của tác giả Martin Zachariasen [53], luận án của tác giả Tobias Polzin [78], luận án của tác giả Pieter Oloff De Wet [61], luận án của tác giả Xinhui Wang [84], luận án của tác giả Jon William Van Laarhoven [46], luận án của tác giả Zhiliu Zhang [87],… 11 Hiện tại, ở Việt Nam chưa có luận án tiến sĩ kỹ thuật chuyên ngành nghiên cứu về bài toán này. Có nhiều hướng tiếp cận giải bài toán Cây Steiner nhỏ nhất như các thuật toán rút gọn đồ thị, các thuật toán tìm lời giải đúng, các thuật toán tìm lời giải gần đúng cận tỉ lệ, các thuật toán heuristic và các thuật toán metaheuristic [8][30][45][51][54] [86],. - Các thuật toán rút gọn đồ thị Một số công trình về rút gọn đồ thị cho bài toán Cây Steiner nghiên cứu các kỹ thuật nhằm giảm thiểu kích thước của đồ thị như công trình của Jeffrey H.Kingston và Nicholas Paul Sheppard [44], công trình của Thorsten Koch và Alexander Martin [77], công trình của C.
Souza [15],… Ý tưởng chung của các thuật toán rút gọn đồ thị là nhằm đến hai mục tiêu: Thứ nhất là gia tăng số lượng các đỉnh thuộc tập terminal; Thứ hai là loại bỏ các đỉnh của đồ thị mà nó chắc chắn không thuộc về Cây Steiner nhỏ nhất cần tìm. Chất lượng các thuật toán giải bài toán SMT phụ thuộc vào độ lớn của hệ số n |L|; do vậy mục đích của các thuật toán rút gọn đồ thị là làm giảm thiểu tối đa hệ số n |L|. Các thuật toán rút gọn đồ thị được xem là bước tiền xử lý dữ liệu quan trọng để nâng cao chất lượng lời giải bài toán SMT; và công đoạn này càng cần thiết đối với các thuật toán tìm lời giải đúng như quy hoạch động hoặc nhánh cận.