Tôi có một tập hợp các điểm và một hàm khoảng cách áp dụng cho mỗi cặp điểm. Tôi muốn kết nối TẤT CẢ các điểm với nhau, với tổng khoảng cách tối thiểu. Bạn có biết về một thuật toán hiện tại tôi có thể sử dụng cho điều đó không?Thuật toán để kết nối tất cả các dấu chấm với tổng khoảng cách tối thiểu
Mỗi điểm có thể được liên kết với một số điểm, vì vậy đây không phải là bình thường "nhân viên bán hàng hành trình" Vấn đề :)
Cảm ơn!
Điều bạn muốn là .
Hai thuật toán phổ biến nhất để tạo ra một là:
Thuật toán bạn đang tìm kiếm được gọi là cây bao trùm tối thiểu. Việc tìm chi phí tối thiểu cho điện nước, điện thoại hoặc lưới điện là rất hữu ích. Có thuật toán của Prim hoặc thuật toán Kruskal. Thuật toán của IMO Prim dễ hiểu hơn một chút.
đây http://en.wikipedia.org/wiki/Minimum_spanning_tree bạn có thể tìm thêm thông tin về cây bao trùm nhỏ nhất, vì vậy bạn có thể điều chỉnh nó để giải quyết vấn đề của bạn.
Hãy nhìn vào thuật toán của Dijkstra:
thuật toán Dijkstra, hình thành bởi nhà khoa học máy tính người Hà Lan Edsger Dijkstra năm 1956 và xuất bản năm 1959, là một thuật toán tìm kiếm đồ thị mà giải quyết đơn nguồn bài toán đường đi ngắn nhất cho một đồ thị với chi phí đường dẫn cạnh không âm, tạo ra một cây con đường ngắn nhất. Thuật toán này thường được sử dụng trong định tuyến và dưới dạng chương trình con trong các thuật toán đồ thị khác.
http://en.wikipedia.org/wiki/Dijkstra 's_algorithm
Như những người khác đã nói, các minimum spanning tree (MST) sẽ cho phép bạn để tạo thành một khoảng cách tối thiểu phụ đồ thị kết nối tất cả các điểm của bạn.
Trước tiên, bạn sẽ cần tạo biểu đồ cho tập dữ liệu của mình. Để tạo hiệu quả biểu đồ không được chiếu, bạn có thể tính toán số Delaunay triangulation của tập hợp điểm của mình. Việc chuyển đổi từ triangulation sang đồ thị sau đó là khá bằng chữ - bất kỳ cạnh nào trong tam giác cũng là một cạnh trong biểu đồ, được cân bằng độ dài của cạnh tam giác.
Có các thuật toán hiệu quả cho cả hai giai đoạn MST (Prim's/Kruskal O(E*log(V))) và Delaunay triangulation (Divide and Conquer O(V*log(V))), vì vậy có thể đạt được các phương pháp tổng thể hiệu quả.
Hy vọng điều này sẽ hữu ích.
Điều này có thể được hiểu là vấn đề cây kéo dài trọng lượng tối thiểu. Tôi không chắc đó là cách tốt nhất để tiếp cận nó nhưng đó là một cách. – biziclop
Nếu chỉ số khoảng cách theo D (x, z) <= D (x, y) + D (y, z) cho mỗi ba điểm x, y & z thì về cơ bản kết nối mọi điểm ghép sẽ cho tổng khoảng cách tối thiểu. Tôi nghĩ rằng bạn cần phải tinh chỉnh câu hỏi của bạn một chút. – ElKamina
Chỉ số khoảng cách có thể là tổng của tất cả độ dài của kết nối. –