部分解决方案的优化:最小化对之间的距离之和
JBS*_*rro 11 algorithm optimization sum distance
我有一个我喜欢的问题,我喜欢考虑解决方案,但不幸的是我被困住了.我希望你也喜欢它.问题是:
我有两个2D点列表(比如A和B),并且需要将A点和B点的点配对,条件是所有对中的距离总和最小.一对包含A中的一个点和B中的一个点,一个点只能使用一次,并且应该创建尽可能多的对(即min(length(A), length(B))).
我做了一个简单的例子,其中颜色表示该点来自哪个列表,黑色连接是解决方案.
虽然这是一个很好的问题,我怀疑是NP难,但它会变得更好.我可以建立现有的解决方案.假设我有两个列表和相应的解决方案(即成对的集合),那么我需要解决的问题是当在一个列表中添加或删除一个点时重新优化该解决方案.
遗憾的是,我无法提出任何产生最佳解决方案的非暴力算法.我希望你可以.任何(伪)语言都可以理解任何算法,最好是C#.