Nghiên Cứu Phát Triển Thuật Toán Metaheuristic Giải Bài Toán Cây Steiner Nhỏ Nhất

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.

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.

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ế.

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ế.

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ế.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 đó.

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.

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ý.