Cómo encontrar el costo mínimo de vincular dos conjuntos de puntos

Question

Tengo dos conjuntos de puntos S y V, ambos tienen el tamaño n. Quiero vincular los dos conjuntos para que cada punto en S se vincule con uno y solo un punto en V. El costo de unir dos puntos se define como la distancia euclidiana entre los dos puntos. Debería haber n! posibles formas de vincular. Entonces, ¿cómo encontrar el camino del costo mínimo? (de manera eficiente)

Answer 1

Este es un problema de asignación. Puedes resolverlo con el Hungarian Method. Hay implementaciones de esto en python. También puede resolver el problema con cualquier solucionador de programación lineal. La formulación LP siempre le dará una solución entera.