5
Mój problem jest następujący:Minimalizacja dystans parowania wskazuje
Given a number of 2n points, I can calculate the distance between all points
and get a symmetrical matrix.
Can you create n pairs of points, so that the sum of the distance of all pairs is
minimal?
EDIT: Every point has to be in one of the pairs. Which means that
every point is only allowed to be in one pair.
ja naiwnie próbował użyć algorytmu węgierskiego i nadzieję, że może dać mi zadanie, dzięki czemu zadania są symetryczne. Ale to oczywiście nie zadziałało, ponieważ nie mam dwuczłonowego wykresu.
Po przeszukaniu znalazłem Stable roommates problem, który wydaje się być podobny do mojego problemu, ale różnica polega na tym, że po prostu próbuje znaleźć dopasowanie, ale nie próbuje zminimalizować odległości.
Czy ktoś wie podobny problem, a nawet rozwiązanie? Przegapiłem coś? Problem nie wydaje się taki trudny, ale nie mogłem wymyślić optymalnego rozwiązania.
Więc jeśli dobrze to rozumiem, macie symetryczną matrycę zawierającą odległość między każdym punktem? Może przekształcić tę macierz w zbiór posortowany według odległości [punkt początkowy, punkt końcowy, odległość] i wybrać pierwsze n par? – Yay295
Każdy punkt może znajdować się w jednej parze. Nie jest to gwarantowane, jeśli sortuję według odległości. Powinienem dodać to do opisu problemu. – the
Hmm, to utrudnia to. Czy jesteś jednak pewien, że węgierski algorytm nie zadziała? Zamiast wyświetlać go jako kompletny, nieukierunkowany wykres, podziel każdy punkt na dwa punkty (źródło i miejsce docelowe) i wyświetl go jako pełnego, dwukierunkowego grafu. – Yay295