Wie finden Sie die Mindestkosten für die Verknüpfung von zwei Punkte

Question

Ich habe zwei Sätze von Punkten S und V, beide haben die Größe n. Ich möchte die beiden Sätze so verknüpfen, dass jeder Punkt in S mit einem und nur einem Punkt in V verknüpft ist. Die Kosten für die Verknüpfung zweier Punkte sind als euklidischer Abstand zwischen den beiden Punkten definiert. Es sollte n sein! mögliche Wege zu verknüpfen. So, wie man den Weg der minimalen Kosten findet? (auf effiziente Weise)

Answer 1

Dies ist ein Zuordnungsproblem. Sie können es mit dem Hungarian Method lösen. Es gibt Implementierungen davon in python. Sie können das Problem auch mit jedem linearen Programmierlöser lösen. Die LP-Formulierung liefert Ihnen immer eine ganzzahlige Lösung.