Tutorial — Thiết lập đường truyền

Khi thực hiện thao tác giữa hai trạm, mức nhiễu của trạm nhỏ hơn sẽ giảm về $0$. Đáng chú ý là khi hai trạm đều có mức nhiễu bằng $0$, chi phí để tạo kênh truyền thông giữa chúng bằng đúng $0$ đơn vị năng lượng.

Để kết nối các thành phần với chi phí bằng $0$, mỗi thành phần chỉ cần sở hữu ít nhất một trạm có mức nhiễu bằng $0$. Bằng cách ghép cặp trạm lớn hơn với trạm nhỏ hơn liền kề từ các giá trị lớn nhất giảm dần, ta vừa tối thiểu hóa chi phí năng lượng tiêu hao vừa tạo ra đủ các trạm có mức nhiễu bằng $0$.

Sắp xếp dãy mức nhiễu ban đầu theo thứ tự tăng dần $g_1 \le g_2 \le \dots \le g_n$ bằng thuật toán sắp xếp. Kết quả tối ưu chính là tổng các phần tử tại các vị trí lẻ tính từ cuối mảng về đầu, tương ứng với các giá trị $g_{n - 2k}$ với mọi số nguyên không âm $k$ thỏa mãn $n - 2k \ge 1$.