- ĐỀ XUẤT THUẬT TOÁN MỚI GIẢI BÀI TOÁN CÂY KHUNG VỚI. - CHI PHÍ ĐỊNH TUYẾN NHỎ NHẤT TRONG TRƯỜNG HỢP ĐỒ THỊ THƯA Phan Tấn Quốc 1. - Hầu hết các đồ thị gặp trong thực tế ứng dụng là đồ thị thưa, trong khi các thuật toán hiệu quả nhất hiện biết giải bài toán MRCST trên đồ thị thưa chưa thực sự hiệu quả - nhất là với các đồ thị thưa có kích thước lớn. - Bài báo này đề xuất một thuật toán mới với tên gọi HCST để giải bài toán MRCST trong trường hợp đồ thị thưa. - Kết quả thực nghiệm trên các đồ thị thưa trong hệ thống dữ liệu thực nghiệm chuẩn cho thấy thuật toán HCST cho chất lượng lời giải tương đương hoặc tốt hơn và với thời gian tính nhanh hơn khi so với các thuật toán tốt nhất hiện biết.. - Bài báo này cũng là công trình đầu tiên công bố kết quả thực nghiệm giải bài toán MRCST cho 20 bộ dữ liệu là các đồ thị thưa có kích thước lớn.. - Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G cần tìm cây khung có chi phí định tuyến nhỏ nhất. - Định nghĩa 3 (Tải định tuyến một cạnh của cây khung [4]) Cho T là một cây khung của đồ thị G.. - Các thuật toán giải đúng phát triển dựa trên phương pháp nhánh cận kết hợp phương pháp sinh cột được đề xuất bởi Matteo Fischetti, Giuseppe Lancia, Paolo Serafini vào năm 2002 [6]. - Một thuật toán gần đúng cận tỉ lệ α nghĩa là trong trường hợp xấu nhất thì lời giải tìm được của thuật toán đó cũng không tệ hơn α lần so với lời giải tối ưu. - tuy nhiên các cận tỉ lệ tìm được của nhiều thuật toán đề xuất trong thực tế thường là kém hơn rất nhiều so với chất lượng lời giải tìm được bởi nhiều thuật toán gần đúng khác dựa trên thực nghiệm [3,4. - điển hình theo hướng này là thuật toán WONG với cận tỉ lệ 2 và có độ phức tạp thời gian tính O(nm + n 2 log n) [4]. - đây là thuật toán định tuyến mạng chạy ổn định trên mọi loại dữ liệu và đã được sử dụng trong thực tế ứng dụng [4,11].. - Các thuật toán heuristic có chất lượng lời giải chấp nhận được với một loại dữ liệu cụ thể nào đó của bài toán. - chẳng hạn như thuật toán ADD được đề xuất bởi Vic Grout vào năm 2005 [12] với độ phức tạp O(n log n) và chỉ tương đối hiệu quả với các đồ thị đồng nhất có kích thước nhỏ [9], thuật toán CAMPOS được đề xuất bởi Rui Campos và Manuel Ricardo vào năm 2008 [11] với độ phức tạp O(m + n log n) và chỉ hiệu quả đối với các đồ thị đầy đủ euclid [9]. - cả hai heuristic này đều không hiệu quả đối với các đồ thị thưa về chất lượng lời giải [9]. - tuy nhiên đây là hai thuật toán nhanh nhất hiện nay trong việc giải bài toán MRCST. - Các thuật toán metaheuristic giải bài toán MRCST đã được đề xuất như các thuật toán di truyền ESCGA [5], BCGA [5], các thuật toán tìm kiếm địa phương SHC [5], PBLS [1], REPRI [8], REPIR [8], TABU [10], các thuật toán ong PABC [2], ABC+LS [2], BEE [9. - tuy nhiên các thuật toán trên chỉ hiệu quả đối với loại đồ thị đầy đủ euclid và đồ thị ngẫu nhiên có kích thước nhỏ (tất cả các thực nghiệm đã công bố hiện nay với đồ thị đầy đủ đều không quá 300 đỉnh). - Trong số các thuật toán đã khảo sát trên, chỉ có các thuật toán WONG, SHC, PBLS, REPRI, REPIR là khả thi đối với các đồ thị thưa có kích thước lớn. - Tiếp theo, chúng tôi sẽ trình bày ngắn gọn ý tưởng của các thuật toán này.. - Thuật toán WONG: Tìm tất cả các cây đường đi ngắn nhất (Shortest Path Tree - SPT) [4] có gốc lần lượt tại các đỉnh của đồ thị, sau đó chọn ra trong số chúng một cây đường đi ngắn nhất có chi phí định tuyến nhỏ nhất [4].. - Thuật toán SHC: Trước hết khởi tạo một cây khung lời giải ngẫu nhiên. - Một lần lặp của thuật toán SHC đòi hỏi thời gian tính O(mn). - Thuật toán SHC ấn định số bước lặp là 10000n. - Thuật toán PBLS: Điểm khác biệt duy nhất của thuật toán PBLS so với thuật toán SHC là PBLS có sử dụng chiến lược đa dạng hóa lời giải - theo nghĩa là thay một số cạnh của cây khung bằng một số cạnh ngẫu nhiên khác. - Thuật toán PBLS ấn định số bước lặp là 50000 và khi chất lượng lời giải không được cải thiện sau 2n bước lặp thì tiến hành đa dạng hóa lời giải. - Một lần lặp của thuật toán PBLS đòi hỏi thời gian tính O(mn). - Thuật toán REPRI: Bắt đầu từ một cây khung T được khởi tạo bằng kết quả của thuật toán WONG.. - Thuật toán dừng nếu trong một lần duyệt qua tất cả các cạnh e T mà không tìm được cạnh e’. - Thuật toán REPIR: Bắt đầu từ một cây khung T được khởi tạo bằng cây khung nhỏ nhất theo thuật toán KRUSKAL hoặc thuật toán PRIM. - Thuật toán dừng nếu trong một lần duyệt qua tất cả các cạnh e G – T mà không cải thiện được chi phí định tuyến của cây khung T [8].. - Tất cả các thuật toán đã khảo sát trên đều có chung cách làm là khi cần thay thế một cạnh nào đó thì phải duyệt qua tập tất cả các cạnh ứng viên để tìm ra cạnh tốt nhất. - chính điều này làm cho các thuật toán trên không khả thi về thời gian khi số cạnh của đồ thị là đủ lớn.. - Bài báo này đề xuất một thuật toán HCST dạng tìm kiếm leo đồi giải bài toán MRCST. - Đề xuất này luôn 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 tốt nhất hiện biết giải bài toán MRCST trên các đồ thị thưa. - Đề xuất này thực sự có ý nghĩa đối với các đồ thị thưa có kích thước lớn.. - 2 ĐỀ XUẤT THUẬT TOÁN HCST GIẢI BÀI TOÁN MRCST TRONG TRƯỜNG HỢP ĐỒ THỊ THƯA. - Thuật toán đề xuất HCST dựa vào chiến lược tìm kiếm lân cận như đã được đề cập trong REPIR [8]. - HCST được bổ sung một số chiến lược mới nhằm tăng chất lượng lời giải và làm cho thuật toán khả thi khi làm việc với các đồ thị thưa có kích thước lớn.. - 2.1 Tạo lời giải ban đầu bằng thuật toán tựa PRIM. - Khác với thuật toán REPIR cho khởi tạo cây khung ban đầu bằng thuật toán tìm cây khung nhỏ nhất của đồ thị theo thuật toán KRUSKAL hoặc thuật toán PRIM. - HCST cho khởi tạo cây khung ngẫu nhiên bằng thuật toán tựa PRIM: Bắt đầu từ cây chỉ gồm một đỉnh nào đó của đồ thị, tiếp theo, thuật toán sẽ thực hiện n-1 bước lặp. - HCST thực hiện chiến lược tìm kiếm lân cận như đã trình bày trong thuật toán REPIR [8].. - Với các đồ thị dày thì HCST làm việc như sau:. - Trong khi đó, trước đây, thuật toán REPIR làm việc kém hiệu quả đối với các đồ thị dày có nhiều đỉnh.. - 2.4 Tăng tính ngẫu nhiên cho thuật toán Hiệu quả của thuật toán HCST có thể được cải thiện khi ta thay đổi thứ tự các cạnh được duyệt trong tập E – T. - 2.5 Cho thực hiện thuật toán nhiều lần trên mỗi bộ dữ liệu. - Thuật toán REPIR thực hiện một lần duy nhất đối với mỗi bộ dữ liệu (do lời giải khởi tạo của REPIR không có tính ngẫu nhiên nên việc chạy nhiều lần sẽ không có tác dụng). - Thuật toán HCST cho thực hiện nhiều lần đối với mỗi bộ dữ liệu.. - 2.6 Sơ đồ thuật toán HCST. - Thuật toán REPIR [8] chỉ nêu ngắn gọn ý tưởng chiến lược tìm kiếm lân cận và không phân tích độ phức tạp tính toán của thuật toán. - Trong bài báo này chúng tôi đã trình bày chi tiết nội dung thuật toán HCST và phân tích độ phức tạp tính toán của thuật toán HCST một cách chi tiết.. - T là cây khung được khởi tạo ngẫu nhiên bằng thuật toán tựa PRIM;. - 2.7 Đánh giá độ phức tạp của HCST Độ phức tạp một lần lặp của thuật toán HCST được đánh giá bởi thời gian tính hai vòng lặp for lồng nhau ở dòng 6 và 10. - Gọi k là giá trị lớn nhất mà vòng lặp while ở dòng 3 có thể thực hiện, thì độ phức tạp một lần lặp của thuật toán HSCT là O(kn 2 m).. - Trong khi các thuật toán SHC, PBLS đưa ra số lần lặp lần lượt là 10000 n 2 m và 50000 nm để đạt được kết quả như công bố (đã được khảo sát ở trên). - thì thuật toán HCST với cách thức tìm lân cận đã nêu có giá trị k khá nhỏ. - Với đồ thị thưa;. - Thời gian tính của các thuật toán HCST nhanh hơn so với nhiều thuật toán metaheuristic khác, đặc biệt là khi làm việc với các đồ thị thưa có kích thước lớn.. - Chúng tôi tiến hành thực nghiệm thuật toán HCST và so sánh chất lượng lời giải và thời gian tính của HCST với các thuật toán tốt nhất hiện biết giải bài toán MRCST trong trường hợp đồ thị thưa như WONG, CAMPOS, SHC, PBLS.. - Do hiện tại chưa có một công trình nào công bố chất lượng lời giải đối với các đồ thị thưa có kích thước lớn, nên chúng tôi đã cài đặt lại các thuật toán WONG, SHC, PBLS trên cùng môi trường thực nghiệm với thuật toán HCST. - Riêng thuật toán CAMPOS chúng tôi được. - Thuật toán HCST được cài đặt bằng ngôn ngữ C. - Thuật toán HCST thực hiện 120 lần đối với mỗi bộ dữ liệu loại steinc, steind. - Các thuật toán SHC, PBLS sử dụng bộ tham số được đề nghị từ các công trình [1,5]. - chỉ riêng tham số số lần lặp tìm kiếm lân cận trong thuật toán SHC được chúng tôi đề nghị là 100000 (do số lần thực hiện việc tìm kiếm lân cận mà tác giả công trình [5] đề nghị là quá lớn: 10000n 2 m). - Hai thuật toán WONG, CAMPOS được cho thực hiện một lần duy nhất.. - Kết quả thực nghiệm của các thuật toán WONG, CAMPOS, SHC, PBLS, HCST trên 20 bộ dữ liệu đồ thị thưa được ghi nhận chi tiết ở Bảng 2 và Bảng 3. - trong đó các thuật toán WONG và CAMPOS ghi nhận các giá trị chi phí định tuyến và thời gian thực hiện tương ứng (Best, Time). - các thuật toán SHC, PBLS, HCST ghi nhận chi phí định tuyến tốt nhất, thời gian trung bình một lần chạy, chi phí định tuyến trung bình và độ lệch chuẩn sau các lần chạy mỗi bộ dữ liệu (Best, Time, Mean, SD).. - Bảng 2: Kết quả thực nghiệm các thuật toán WONG, CAMPOS, SHC trên đồ thị thưa. - Bảng 3: Kết quả thực nghiệm các thuật toán PBLS, HCST trên đồ thị thưa. - Từ kết quả thực nghiệm trên, có thể đánh giá về chất lượng lời giải của thuật toán HCST so với các thuật toán WONG, CAMPOS, SHC, PBLS.. - Thuật toán HCST cho chất lượng lời giải tốt hơn các thuật toán WONG, CAMPOS trên 100% bộ dữ liệu.. - Thuật toán HCST cho chất lượng lời giải tốt hơn thuật toán SHC trên 25% bộ dữ liệu, bằng thuật toán SHC trên 70% bộ dữ liệu và kém hơn thuật toán SHC trên 5% bộ dữ liệu.. - Thuật toán HCST cho chất lượng lời giải tốt hơn thuật toán PBLS trên 40% bộ dữ liệu và bằng thuật toán PBLS trên 60% bộ dữ liệu.. - Các thuật toán SHC, PBLS, HCS cho chất lượng lời giải trung bình nhìn chung là kém hơn thuật toán WONG. - Thuật toán WONG có chất lượng lời giải tốt hơn thuật toán CAMPOS.. - Tiếp theo chúng tôi sẽ so sánh chất lượng lời giải của thuật toán HCST và các thuật toán đã khảo sát trên qua một số hình vẽ. - Các thuật toán SHC, PBLS, HCST cho chất lượng lời giải như nhau trên các đồ thị steinc.. - Hình 1: Chất lượng lời giải của các thuật toán qua các bộ dữ liệu steinc. - Các thuật toán PBLS, HCST cho chất lượng lời giải bằng nhau trên các bộ dữ liệu steind và cùng cho chất lượng tốt hơn thuật toán SHC trên một bộ dữ liệu.. - Hình 2: Chất lượng lời giải của các thuật toán qua các bộ dữ liệu steind. - Các thuật toán SHC, HCST cho chất lượng lời giải bằng nhau trên các bộ dữ liệu steine11..steine15 và cùng cho chất lượng tốt hơn thuật toán PBLS trên ba bộ dữ liệu.. - Hình 3: Chất lượng lời giải của các thuật toán qua các bộ dữ liệu steine11..steine15 Thuật toán HCST cho chất lượng lời giải tốt hơn thuật toán SHC trên bốn bộ dữ liệu thuộc steine16..steine20 và kém hơn trên một bộ dữ liệu còn lại. - thuật toán HCST luôn luôn cho lời giải có chất lượng tốt hơn thuật toán PBLS trên các bộ dữ liệu steine16..steine20.. - Hình 4: Chất lượng lời giải của các thuật toán qua các bộ dữ liệu steine16..steine20 3.4.2 Thời gian tính. - Thuật toán HCST có thời gian tính không quá 7.6% thời gian tính của thuật toán SHC đối với các đồ thị 500 đỉnh, không quá 18.6% đối với các đồ thị 1000 đỉnh, không quá 43.0% đối với các đồ thị 2500 đỉnh steine16..steine20 và không quá 61.7%. - đối với các đồ thị 2500 đỉnh steine11..steine15.. - Thuật toán HCST có thời gian tính không quá 15.2% thời gian tính của thuật toán PBLS đối với các đồ thị 500 đỉnh, không quá 36.7% đối với các đồ thị 1000 đỉnh, không quá 84.7% đối với các đồ thị 2500 đỉnh steine16..steine20, và có thời gian tính tương đương đối với các đồ thị 2500 đỉnh steine11..steine15.. - Tiếp theo chúng tôi sẽ so sánh thời gian tính của thuật toán HCST với các thuật toán đã khảo sát trên qua một số hình vẽ.. - Hình 5: Thời gian tính của các thuật toán qua các bộ dữ liệu steinc. - Hình 6: Thời gian tính của các thuật toán qua các bộ dữ liệu steind. - Hình 7: Thời gian tính của các thuật toán qua các bộ dữ liệu steine11.. - Hình 8: Thời gian tính của các thuật toán qua các bộ dữ liệu steine16..steine20. - Bài báo đã khảo sát các thuật toán tốt nhất hiện biết giải bài toán MRCST trong trường hợp đồ thị thưa và qua đó đề xuất một thuật toán mới hiệu quả để giải bài toán MRCST trong trường hợp đồ thị thưa. - Bài báo này cũng là công trình đầu tiên công bố kết quả thực nghiệm giải bài toán MRCST trên các đồ thị thưa có kích thước lớn.. - Thuật toán bầy ong giải bài toán cây khung với chi phí định tuyến nhỏ nhất. - Thuật toán tìm kiếm Tabu giải bài toán cây khung với chi phí định tuyến nhỏ nhất