tailieunhanh - Giải thuật kiến song song giải bài toán cây khung nhỏ nhất có bậc bị chặn
Bài viết đề xuất giải thuật tối ưu hóa đàn kiến song song tìm cây khung nhỏ nhất có bậc bị chặn trên đồ thị có số đỉnh tương đối lớn. | Giải thuật kiến song song giải bài toán cây khung nhỏ nhất có bậc bị chặn JOURNAL OF SCIENCE OF HNUE DOI: Educational Sci., 2015, Vol. 60, No. 7A, pp. 53-60 This paper is available online at GIẢI THUẬT KIẾN SONG SONG GIẢI BÀI TOÁN CÂY KHUNG NHỎ NHẤT CÓ BẬC BỊ CHẶN Bùi Thị Thủy, Phạm Thị Lan Khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội Tóm tắt. Cho một đồ thị G = (V, E) liên thông, có trọng số và một số nguyên dương d. Cây khung có bậc bị chặn của G là một cây khung trong đó các đỉnh của nó đều có bậc nhỏ hơn d. Bài toán tìm cây khung nhỏ nhất có bậc bị chặn của một đồ thị cho trước đã được chứng minh là bài toán NP - khó. Trong bài báo này, chúng tôi đề xuất giải thuật tối ưu hóa đàn kiến song song tìm cây khung nhỏ nhất có bậc bị chặn trên đồ thị có số đỉnh tương đối lớn. Từ khóa: Giải thuật kiến, cây khung tối ưu có bậc bị chặn, chiến lược song song, bài toán Np - khó, thuật toán song song. 1. Mở đầu Bài toán cây khung nhỏ nhất có bậc bị chặn (Degree – Constrained Minimum Spanning Tree (DCMST)) được nghiên cứu lần đầu tiên bởi 2 tác giả Deo và Hakimi [2]. Bài toán được phát biểu như sau: Input: Cho trước một đồ thị G = (V, E) với |V | = n, các cạnh được gán trọng số và một số nguyên dương d. Question: Có tồn tại hay không một cây khung nhỏ nhất T của G thỏa mãn điều kiện mọi đỉnh của T đều có bậc không vượt quá d. Có thể phát biểu lại bài toán dưới dạng tối ưu như sau: Cho đồ thị G = (V, E) có n đỉnh, m cạnh và cij > 0 là trọng số của mỗi cạnh eij . Giả sử ( cij , eij ∈ E Xij = () 0, eij 6∈ E Với một số d nguyên dương, hãy xác định giá trị nhỏ nhất của biểu thức sau: X WT = cij Xij () i,j∈V,i6=j Ngày nhận bài: 20/7/2015. Ngày nhận đăng: 20/11/2015. Liên hệ: Bùi Thị Thủy, e-mail: btthuy@ 53 Bùi Thị Thủy, Phạm Thị Lan Trong đó X Xij ≤ d với i ∈ V () j∈V,i6=j X Xij ≥ 1 với i ∈ V () j∈V,i6=j
đang nạp các trang xem trước
