我在 x 轴上随机放置了引脚，并且知道所有这些引脚的位置。假设有 n 个。我必须在两个限制 [A,B] 之间移动 x 轴上的所有这些引脚，以便新位置形成差的算术级数 k。我应该这样做，使 SUM(|oldpos(i) - newpos(i)|) for each pin i 最小。为方便起见，目前我正在考虑仅将所有引脚移出/移至整数位置。
我不知道这是否可以在某个最佳时间复杂度内完成。我可以肯定的一件事是，在最佳排列之后，新位置的引脚将像在旧位置一样排序。
一个 O(k.n) 方法是选择从 A 开始的级数(即，将第一个引脚放置在 A，然后将每个后续引脚放置在 A+k、A+2k 等等).为此计算SUM。现在对 A+1、A+1+k、A+2+2k 等处的每个引脚执行相同操作。最低限度就是答案。
最佳答案
你是对的，你可以构建一个保持秩序的解决方案。但这不一定是唯一的解决方案。考虑以下示例，目标 T1 和 T2 以及源点 S1 和 S2(您要移动到目标):
T1 T2
S1 S2
如您所见，有两种解决方案:
- 将
S1移动到T1并将S2移动到T2 - 将
S1移动到T2并将S2保持在T1
两种解决方案的总成本完全相同，因为您使用绝对值作为成本标准。如果您使用平方范数或其他范数，这看起来会有所不同。
既然您知道输入点和目标点之间的对应关系(现在假设从 A 开始的进程)，您只需要优化偏移量:
minimize_offset SUM_i (|T_i + offset - oldpos(i)|)
没有正式证明，解决方案是offset = median(oldpos(i) - T_i)。直觉是两个序列的中值必须位于相同的位置。您可以通过可视化更改偏移量时发生的情况来验证这一点。对于某些源点，成本会增加，而对于某些源点，成本会降低，具体取决于这些点到其相应目标点的方向以及您更改偏移量的方向。关键是，如果两个点都没有改变相对于其相应目标点的一侧(因为您使用了绝对值范数)，则这些变化的绝对值将全部相同。因此，如果左侧对应的点与右侧对应的点一样多，则无法进一步降低成本，因为一旦降低其中一组的成本，就会增加其中一组的成本其他设置相同数量。
无论如何，可以使用天真的方法在 O(n log n) 中计算中位数，或者使用中位数的中位数计算 O(n)。如果您得到的解决方案的目标点超出了有效区间，则必须相应地截断偏移量。事实上，目标点的初始假设(从 A 开始)不需要进行。您可以假设任何开始，例如0。
顺便说一句，这听起来与 a former project of mine 非常相似.您可能想看一看。
例子
这是您给定输入的示例
S = (4, 7, 9, 13, 16)
k=3.
第 1 步:使用 k=3 构建任意目标序列:
T = (0, 3, 6, 9, 12)
第 2 步:计算序列 S - T
S - T = (4, 4, 3, 4, 4)
第 3 步:计算 S - T 的中位数:
median(S - T) = 4
将此偏移量添加到 T，您就得到了最终序列:
F = (4, 7, 10, 13, 16)
S = (4, 7, 9, 13, 16)
关于algorithm - 将引脚最佳地放置在轴上作为算术级数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44223199/