MÔ HÌNH CÂY CỰC TIỂU

MÔ HÌNH CÂY CỰC TIỂU

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

a. Bài toán cây cực tiểu

Mô hình cây cực tiểu nhằm giải bài toán liên kết toàn bộ các nút của một mạng sao cho tổng chiều dài của các cung liên kết là cực tiểu. Bài toán cây cực tiểu trong thực tế có thể liệt kê như sau:

Xây dựng hệ thống giao thông nối nhiều thành phố
Xây dựng hệ thống cáp tín hiệu nối nhiều điểm thu phát,…

Một bài toán cây cực tiểu như sau: Một công ty cung cấp dịch vụ truyền hình cáp cho năm khu vực dân cư với mạng cáp có thể lắp đặt và khoảng cách giữa trung tâm và các khu vực như ở sơ đồ mạng sau. Công ty muốn xác định mạng cáp với mục tiêu cực tiểu tổng chiều dài của mạng cáp.

b. Giải thuật cây cực tiểu

Gọi:

N={1, 2, …, n}: tập các nút mạng
C_k tập các nút nối mạng ở bước lặp k của giải thuật
N_k tập các nút chưa nối mạng ở bước lặp k của giải thuật

Giải thuật cây cực tiểu gồm các bước sau:

Bước 0: Đặt C₀= Æ, N₀= N.

Bước 1:

Bắt đầu bằng nút bất kỳ i, đặt C₁= {i}, N₁= N – {i}
Đặt k = 2

Bước k:

Chọn nút j* Î N_k-1, có cung ngắn nhất liên kết với một nút của C_k-1.
Nối kết j* với nút của C_k-1có liên kết ngắn nhất với j*, nút j* chuyển từ N_k-1vào C_k-1.
Nếu N_k= Æ. Dừng
Nếu N_k¹ Æ. Đặt k = k + 1, quay lại bước k.