Doc_Co
29-04-2004, 07:42
Cho trước N điểm trong mặt phẳng, hãy tìm tập các đoạn thẳng nối tất cả các diểm với nhau sao cho tổng dộ dài của chúng ngắn nhất.
Có một cách giả đơn giản nhất là xây dựng một đồ thị đầy đủ cos n đỉnh vaf
n*(n-1)/2 cạnh có trọng số là khoảng cách giữa hai đỉnh . Sau đó dùng Kruskal để tìm.
Xin hỏi:
1. có tài liệu nào hướng dẩn không. Lợi dụng yếu tố hình học ta sẽ loại bỏ một số cạnh trong đô thị đầy đủ trước khi tìm cây bao trùm tối thiểu.
Có một cách giả đơn giản nhất là xây dựng một đồ thị đầy đủ cos n đỉnh vaf
n*(n-1)/2 cạnh có trọng số là khoảng cách giữa hai đỉnh . Sau đó dùng Kruskal để tìm.
Xin hỏi:
1. có tài liệu nào hướng dẩn không. Lợi dụng yếu tố hình học ta sẽ loại bỏ một số cạnh trong đô thị đầy đủ trước khi tìm cây bao trùm tối thiểu.