gpt4 book ai didi

algorithm - 如何找到连接两组点的最小成本

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:46:53 25 4
gpt4 key购买 nike

我有两组点 S 和 V,它们的大小都是 n。我想链接这两个集合,以便 S 中的每个点都链接到 V 中的一个且仅一个点。链接两点的成本定义为两点之间的欧几里德距离。应该有n!可能的链接方式。那么如何找到成本最低的方法呢? (以一种有效的方式)

最佳答案

这是一个赋值问题。您可以使用 Hungarian Method 解决它. python 中有此实现.您还可以使用任何线性规划求解器解决问题。 LP 公式将始终为您提供整数解。

关于algorithm - 如何找到连接两组点的最小成本,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10174779/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com