graph-algorithm - 最佳最大点对

  显示原文与译文双语对照的内容
0 0

我在 2 D 有一个偶数点。 我需要一个能使对点对成对的算法,这样对对的总距离是最大的。

动态编程,贪婪的方法将无法工作,我认为。 我可以使用线性规划还是匈牙利算法? 或者其他任何?

时间:原作者:4个回答

0 0

你当然可以使用整数线性规划。 下面是一个示例公式:

为每个无序的distrinct点 ij 引入一个二进制变量 x[ij] ( 例如 ) 。 例如 i<j ),其中 x[ij]=1 iff ij 组合在一起。

计算 d[ij] ( 用于 i<j )的所有距离。

目标是最大化 sum_[i<j] d[ij]*x[ij],受到每个点正好成一对的约束,换句话说, forall j, sum_[i<j] x[ij] = 1

注意,这里工作也适用于 3d 点: 你只需要两对点之间的距离。

原作者:
...