I. Tổng Quan Về Bài Toán Cây Steiner Nhỏ Nhất Giới Thiệu
Bài toán Cây Steiner Nhỏ Nhất (SMT) là một trong những bài toán quan trọng nhất trong thiết kế mạng truyền thông. Mạng truyền thông được mô hình hóa bằng đồ thị vô hướng, liên thông và có trọng số. Bài toán SMT là bài toán tối ưu tổ hợp, được quan tâm nghiên cứu từ những năm 70 của thế kỷ trước để áp dụng cho thiết kế hệ thống mạng và nhiều ứng dụng quan trọng khác trong khoa học và kỹ thuật. Phần lớn các bài toán tối ưu là bài toán thuộc lớp NP-hard, không thể giải trong thời gian đa thức. Chỉ với bài toán quy mô nhỏ thì có thể giải bằng các phương pháp toán chính xác. Các bài toán khác được giải quyết bằng phương pháp xấp xỉ để tạo ra một giải pháp đủ tốt trong một thời gian hợp lý, đó là phương pháp heuristic và metaheuristic. Ứng dụng bài toán Cây Steiner trong khoa học kỹ thuật nói chung đã được nghiên cứu và công bố trong nhiều công trình. Tuy nhiên, do bản chất đây là bài toán tối ưu thuộc lớp NP-hard nên cho đến nay, bài toán vẫn tiếp tục được nghiên cứu nhằm tìm lời giải tối ưu hơn cho các ứng dụng thực tế, đặc biệt là ứng dụng trong thiết kế hệ thống mạng.
1.1. Định Nghĩa Bài Toán Cây Steiner Nhỏ Nhất SMT
Mô hình toán học của bài toán Cây Steiner Nhỏ Nhất có thể phát biểu như sau: 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 của L. 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. 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. Trong trường hợp tổng quát, bài toán SMT đã được chứng minh thuộc lớp bài toán NP-hard.
1.2. Ứng Dụng Thực Tế Của Bài Toán Cây Steiner Nhỏ Nhất
Bài toán SMT có nhiều ứng dụng quan trọng trong một số lĩnh vực khoa học và kỹ thuật, cụ thể như: Bài toán thiết kế mạng truyền thông, bài toán thiết kế vi mạch cỡ cực lớn VLSI (Very large scale integrated), tin sinh học, các bài toán liên quan đến hệ thống mạng với chi phí nhỏ nhất. Bài toán SMT vẫn thu hút được sự nghiên cứu của nhiều nhà khoa học trong hàng chục năm qua. Hiện nay, đã có hàng loạt thuật toán giải bài toán SMT được đề xuất và có thể chia chúng thành các hướng tiếp cận sau: Các thuật toán rút gọn đồ thị, các thuật toán cận tỉ lệ, các thuật toán tìm lời giải đúng, các thuật toán heuristic và metaheuristic.
II. Thách Thức Giải Bài Toán Cây Steiner Nhỏ Nhất NP khó
Bài toán Cây Steiner Nhỏ Nhất thuộc lớp NP-khó, việc tìm kiếm lời giải tối ưu trong thời gian đa thức là bất khả thi đối với các bài toán có kích thước lớn. Điều này đặt ra thách thức lớn trong việc phát triển các thuật toán hiệu quả để giải quyết bài toán này trong thực tế. Các phương pháp tiếp cận truyền thống thường gặp khó khăn trong việc tìm kiếm lời giải chấp nhận được trong thời gian hợp lý. Do đó, việc nghiên cứu và phát triển các thuật toán metaheuristic trở nên vô cùng quan trọng để vượt qua những hạn chế này.
2.1. Độ Phức Tạp Tính Toán Của Bài Toán Cây Steiner
Do tính chất NP-khó của bài toán, độ phức tạp tính toán tăng lên đáng kể khi kích thước bài toán tăng. Các thuật toán tìm kiếm vét cạn không khả thi đối với các bài toán có số lượng đỉnh và cạnh lớn. Việc tìm kiếm lời giải tối ưu đòi hỏi thời gian tính toán lớn, gây khó khăn trong việc ứng dụng vào thực tế.
2.2. Hạn Chế Của Các Thuật Toán Tìm Lời Giải Chính Xác
Các thuật toán tìm lời giải chính xác, như thuật toán nhánh cận, có thể tìm được lời giải tối ưu, nhưng chỉ hiệu quả với các bài toán có kích thước nhỏ. Khi kích thước bài toán tăng lên, thời gian tính toán tăng lên theo cấp số mũ, khiến các thuật toán này trở nên không thực tế.
2.3. Yêu Cầu Về Chất Lượng Lời Giải Trong Thực Tế
Trong nhiều ứng dụng thực tế, việc tìm kiếm lời giải gần tối ưu trong thời gian ngắn quan trọng hơn việc tìm kiếm lời giải tối ưu tuyệt đối. Các thuật toán metaheuristic cung cấp một sự cân bằng giữa chất lượng lời giải và thời gian tính toán, làm cho chúng trở thành lựa chọn phù hợp cho nhiều bài toán thực tế.
III. Thuật Toán Heuristic Mới Giải Bài Toán Cây Steiner SMT
Luận án đề xuất hai thuật toán heuristic mới: SPT-Steiner và PD-Steiner để giải bài toán SMT. Các thuật toán này được cài đặt thực nghiệm trên 98 bộ dữ liệu (gồm có 78 bộ dữ liệu là các đồ thị thưa trong hệ thống dữ liệu thực nghiệm chuẩn và 20 bộ dữ liệu mở rộng là các đồ thị thưa kích thước lớn lên đến 10000 đỉnh - steinf). Từ kết quả thực nghiệm, luận án tiến hành so sánh, đánh giá chi tiết hiệu quả của hai thuật toán heuristic đề xuất mới với thuật toán heuristic MST-Steiner đã được công bố trước đó. Hai thuật toán đề xuất bởi luận án cho chất lượng lời giải tốt hơn thuật toán MST-Steiner trên một số bộ dữ liệu. Thời gian chạy của các thuật toán SPT-Steiner và PD-Steiner chậm hơn so với thuật toán MST-Steiner.
3.1. Thuật Toán SPT Steiner Dựa Trên Cây Đường Đi Ngắn Nhất
Thuật toán SPT-Steiner dựa trên ý tưởng tìm cây đường đi ngắn nhất. Thuật toán này xây dựng cây Steiner bằng cách kết nối các đỉnh terminal thông qua các đường đi ngắn nhất giữa chúng. Quá trình này lặp lại cho đến khi tất cả các đỉnh terminal được kết nối vào một cây duy nhất. Sau đó, các cạnh dư thừa được loại bỏ để tạo ra cây Steiner cuối cùng.
3.2. Thuật Toán PD Steiner Kết Hợp Prim và Dijkstra
Thuật toán PD-Steiner là sự kết hợp ý tưởng chính của thuật toán Prim và Dijkstra. Thuật toán này bắt đầu từ một đỉnh terminal ngẫu nhiên và mở rộng cây Steiner bằng cách thêm các đỉnh và cạnh sao cho tổng chi phí là nhỏ nhất. Thuật toán sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ cây hiện tại đến các đỉnh terminal chưa được kết nối.
3.3. So Sánh SPT Steiner và PD Steiner với MST Steiner
Kết quả thực nghiệm cho thấy các thuật toán SPT-Steiner và PD-Steiner cho chất lượng lời giải tốt hơn thuật toán MST-Steiner trên một số bộ dữ liệu. Tuy nhiên, thời gian chạy của các thuật toán SPT-Steiner và PD-Steiner chậm hơn so với thuật toán MST-Steiner. Điều này cho thấy sự đánh đổi giữa chất lượng lời giải và thời gian tính toán.
IV. Cải Tiến Heuristic Giải Bài Toán SMT Đồ Thị Thưa Lớn
Luận án đề xuất hai thuật toán heuristic cải tiến: i-SPT-Steiner và i-PD-Steiner giải bài toán SMT trong trường hợp đồ thị thưa kích thước lớn. Hai thuật toán heuristic cải tiến i-SPT-Steiner và i-PD-Steiner được cài đặt thực nghiệm và so sánh, đánh giá tính hiệu quả trên 80 bộ dữ liệu là các đồ thị thưa kích thước lớn lên đến 100000 đỉnh. Hai thuật toán heuristic cải tiến cho chất lượng lời giải tốt hơn hoặc tương đương thuật toán MST-Steiner trên một số bộ dữ liệu. Thời gian chạy của thuật toán i-PD-Steiner nhanh hơn so với thuật toán MST-Steiner và thuật toán i-SPT- Steiner. Thời gian chạy của thuật toán i-SPT-Steiner chậm hơn so với thuật toán MST-Steiner và thuật toán i-PD-Steiner.
4.1. Thuật Toán i SPT Steiner Cải Tiến SPT Steiner
Thuật toán i-SPT-Steiner là phiên bản cải tiến của thuật toán SPT-Steiner. Cải tiến chính nằm ở việc sử dụng thuật toán Dial (một biến thể của thuật toán Dijkstra) để tìm đường đi ngắn nhất. Thuật toán Dial hiệu quả hơn thuật toán Dijkstra trong trường hợp đồ thị thưa, giúp giảm thời gian tính toán.
4.2. Thuật Toán i PD Steiner Cải Tiến PD Steiner
Thuật toán i-PD-Steiner là phiên bản cải tiến của thuật toán PD-Steiner. Tương tự như i-SPT-Steiner, i-PD-Steiner sử dụng thuật toán Dial thay vì Dijkstra để tìm đường đi ngắn nhất. Điều này giúp cải thiện hiệu suất của thuật toán trên các đồ thị thưa kích thước lớn.
4.3. Đánh Giá Hiệu Quả Của Các Thuật Toán Cải Tiến
Kết quả thực nghiệm cho thấy các thuật toán i-SPT-Steiner và i-PD-Steiner hiệu quả hơn trong việc giải bài toán SMT trên các đồ thị thưa kích thước lớn. Thuật toán i-PD-Steiner có thời gian chạy nhanh hơn so với i-SPT-Steiner và MST-Steiner, trong khi vẫn duy trì chất lượng lời giải tốt.
V. Thuật Toán Metaheuristic Mới Giải Bài Toán Steiner SMT
Luận án đề xuất mới ba thuật toán metaheuristic dạng cá thể, quần thể giải bài toán SMT đó là: thuật toán Bees-Steiner, thuật toán tìm kiếm lân cận biến đổi VNS và thuật toán tìm kiếm leo đồi Hill climbing search (HCSMT). Ngoài ra, luận án cũng đề xuất 2 chiến lược tìm kiếm lân cận: Tham lam và có xác suất; đồng thời sử dụng chúng trong lược đồ thuật toán tìm kiếm lân cận biến đổi, nhằm nâng cao hơn nữa chất lượng cho các thuật toán metaheuristic.
5.1. Thuật Toán Bees Steiner Dựa Trên Bầy Ong
Thuật toán Bees-Steiner là một thuật toán metaheuristic dựa trên hành vi tìm kiếm thức ăn của bầy ong. Thuật toán này sử dụng một quần thể các con ong để khám phá không gian tìm kiếm và tìm ra lời giải tốt nhất cho bài toán SMT. Các con ong được chia thành các nhóm khác nhau, mỗi nhóm chịu trách nhiệm khám phá một vùng khác nhau của không gian tìm kiếm.
5.2. Thuật Toán Tìm Kiếm Lân Cận Biến Đổi VNS
Thuật toán VNS là một thuật toán metaheuristic dựa trên ý tưởng thay đổi cấu trúc lân cận trong quá trình tìm kiếm. Thuật toán này sử dụng một tập hợp các cấu trúc lân cận khác nhau và chuyển đổi giữa chúng để khám phá không gian tìm kiếm một cách hiệu quả hơn. Luận án đề xuất hai chiến lược tìm kiếm lân cận: Tham lam và có xác suất, để sử dụng trong thuật toán VNS.
5.3. Thuật Toán Hill Climbing Search HCSMT
Thuật toán HCSMT là một thuật toán metaheuristic đơn giản dựa trên ý tưởng leo đồi. Thuật toán này bắt đầu từ một lời giải ban đầu và liên tục cải thiện nó bằng cách di chuyển đến các lời giải lân cận tốt hơn. Thuật toán dừng lại khi không còn lời giải lân cận nào tốt hơn lời giải hiện tại.
VI. Đánh Giá Thuật Toán Metaheuristic Giải Bài Toán SMT
Các thuật toán metaheuristic đề xuất mới này được cài đặt thực nghiệm trên hệ thống dữ liệu thực nghiệm chuẩn và so sánh hiệu quả với các thuật toán metaheuristic khác hiện biết. Kết quả so sánh cho thấy các thuật toán metaheuristic đề xuất mới cho chất lượng lời giải tốt hơn hoặc bằng các thuật toán metaheuristic công bố trước đó trên một số bộ dữ liệu. Chất lượng của các thuật toán metaheuristic phụ thuộc chủ yếu vào các chiến lược tìm kiếm lân cận.
6.1. So Sánh Với Các Thuật Toán Metaheuristic Khác
Kết quả thực nghiệm cho thấy các thuật toán Bees-Steiner, VNS và HCSMT có thể cạnh tranh với các thuật toán metaheuristic khác trong việc giải bài toán SMT. Trong một số trường hợp, các thuật toán đề xuất mới cho chất lượng lời giải tốt hơn hoặc tương đương với các thuật toán đã được công bố trước đó.
6.2. Ảnh Hưởng Của Chiến Lược Tìm Kiếm Lân Cận
Chiến lược tìm kiếm lân cận đóng vai trò quan trọng trong hiệu suất của các thuật toán metaheuristic. Các chiến lược tìm kiếm lân cận hiệu quả có thể giúp thuật toán khám phá không gian tìm kiếm một cách hiệu quả hơn và tìm ra lời giải tốt hơn.
6.3. Ứng Dụng Thực Tế Của Các Thuật Toán Metaheuristic
Các thuật toán metaheuristic có thể được áp dụng để giải quyết nhiều bài toán thực tế liên quan đến Cây Steiner Nhỏ Nhất, chẳng hạn như thiết kế mạng truyền thông, thiết kế vi mạch và tối ưu hóa logistics. Các thuật toán này cung cấp một phương pháp hiệu quả để tìm kiếm lời giải gần tối ưu trong thời gian hợp lý.
