Tôi đã đưa ra vấn đề sau đây mà tôi không biết các giải pháp cũng như không thể tìm thấy cụm từ 'tra cứu' để điều tra thêm.Giảm thiểu tổng khoảng cách bằng cách sử dụng liên kết k giữa các nút
Giả sử chúng tôi có N nút được đặt hàng (n_1, n_2 .... n_N) với một khoảng cách cố định là 1 giữa chúng. So dist (n_1, n_N) = N-1. Bây giờ chúng ta được phép kết nối hai nút bất kỳ, do đó có hiệu quả làm giảm khoảng cách của chúng đến 1. Giả sử chúng ta có thể có các kết nối như vậy.
Vấn đề là: làm cách nào để chúng tôi chọn nút nào để kết nối để giảm thiểu tổng khoảng cách giữa hai nút bất kỳ?
Vấn đề này có phải là biến thể đã biết của một số vấn đề được nghiên cứu kỹ lưỡng không? Có một giải pháp hiệu quả tồn tại cho điều này (hoặc một biến thể mà chúng tôi chỉ muốn giảm thiểu khoảng cách tối đa giữa bất kỳ hai nút)
Cảm ơn
Sự khác nhau giữa việc giảm thiểu "tổng khoảng cách giữa hai nút bất kỳ" và giảm thiểu "khoảng cách tối đa giữa hai nút bất kỳ" là gì? –
tổng khoảng cách có nghĩa là tổng khoảng cách giữa tất cả các cặp nút. khoảng cách tối đa là khoảng cách lớn nhất từ tập hợp tất cả khoảng cách giữa các cặp nút. Tôi không chắc chắn nhưng họ không có vẻ tương đương. – Jagadeesh