我想要做的是不断向一个集合中添加更多的值，并尽量让它们彼此之间距离尽可能远。我相信肯定有几种算法可以解决这个问题，但我可能只是没有用正确的术语进行搜索。如果有人能指向一个解决方案（不需要特别高效），那就太棒了。
实际上，给定一个范围在Min-Max之间的值S集合，我需要计算出一个新值V，也在该范围内，使得V与S中所有值之间的距离之和最大化。
实际上，给定一个范围在Min-Max之间的值S集合，我需要计算出一个新值V，也在该范围内，使得V与S中所有值之间的距离之和最大化。
3个回答
2
很容易证明，V的可能候选值要么是S已存在的值，要么是最小/最大值。证明：设S_1，S_2，...，S_n为包括最小和最大值在内的排序后的S序列。如果选择S_i < V < S_{i+1}，则距离之和可以通过选择V = S_i或V = S_{i+1}来实现，具体取决于左侧和右侧的点数。
这种观察可以得到一个O（n ^ 2）算法，只需检查S中的每个潜在候选项即可。通过预先计算前缀和以在O（1）每个元素中计算距离总和，可以将其改进为O（n）。
一般来说，由于每个元素对可能值域产生两个线性成本函数的贡献，因此可以使用O（log n）解决此问题。您只需要一个可以维护线性函数段列表并返回具有最大总和的点的数据结构。平衡二叉搜索树具有一些巧妙的增强和延迟更新，可以解决此问题。当然，是否需要这样做取决于元素数量和您希望执行的查询数量。
这种观察可以得到一个O（n ^ 2）算法，只需检查S中的每个潜在候选项即可。通过预先计算前缀和以在O（1）每个元素中计算距离总和，可以将其改进为O（n）。
一般来说，由于每个元素对可能值域产生两个线性成本函数的贡献，因此可以使用O（log n）解决此问题。您只需要一个可以维护线性函数段列表并返回具有最大总和的点的数据结构。平衡二叉搜索树具有一些巧妙的增强和延迟更新，可以解决此问题。当然，是否需要这样做取决于元素数量和您希望执行的查询数量。
- Niklas B.
9
忍者回答！找到操作复杂度的工作做得很好。 - tophyr
考虑一组5个值：
{1, 10, 10, 10, 10}。通过将 V 插入到接近1而不是在1和10之间的中间位置（即5）来最大化距离的总和。我有什么遗漏吗？ - Tim Biegeleisen@tophyr 注意，我的建议与你的不同。我提出了一种方法，无需首先遍历S。 - Niklas B.
дҪ зҡ„иҜ„и®әеҗҜеҸ‘дәҶжҲ‘дҝ®ж”№дёӢйқўзҡ„зӯ”жЎҲпјҢдҪҶиҝҷ并дёҚж”№еҸҳжҖ»е’ҢгҖӮиҜ·иҖғиҷ‘д»ҘдёӢжғ…еҶөпјҡ
`[1, 10, 10, 10, 10]` -> `[9, 0, 0, 0]` == `9`,
`[1, 1.5, 10, 10, 10, 10]` -> `[.5, 8.5, 0, 0, 0]` == `9`,
`[1, 1.00001, 10, 10, 10, 10]` -> `[.00001, 8.9999, 0, 0, 0]` == `9`,
`[1, 5, 10, 10, 10, 10]` -> `[4, 5, 0, 0, 0]` == `9` - tophyr哎呀，这格式太丑了...太糟糕了，注释中的换行符显然没有被保留。 - tophyr
显示剩余4条评论
1
我不认为有一种万能解决方案来解决你的问题，但这是我通常解决问题的方法。首先，你需要定义一个函数
接下来，你可以迭代
这个算法可以重复用于每个要添加的新值。请注意，因为这本质上是一个一维优化问题，所以运行时间应该不会太糟糕，因此你的第一次尝试可能已经足够了。
sumDistance()，它接受一个新值V和当前集合中的所有值，并输出V与集合中每个值之间距离的总和。接下来，你可以迭代
sumDistance()的定义域d，其中Min <= d <= Max，并跟踪域中每个值V的总和。当你遇到一个新的最大总和时，记录它。给你最大总和的V值是你保留并添加到你的集合中的值。这个算法可以重复用于每个要添加的新值。请注意，因为这本质上是一个一维优化问题，所以运行时间应该不会太糟糕，因此你的第一次尝试可能已经足够了。
- Tim Biegeleisen
5
这听起来就是我在找的，很有道理。如果我没弄错的话，我可以通过快速搜索来迭代整个范围，将每个值的搜索时间减少到log(N)，其中N为范围值。我打算试一试这个方法。 - Zepee
很遗憾，我看不到任何方法可以保证你拥有最好的“V”值而不需要每次迭代范围。但是对于一维问题，O（N）并不算太糟糕。 - Tim Biegeleisen
@Zepee 你在实现解决方案方面有没有取得任何成功？ - Tim Biegeleisen
是的，它确实起作用了。在我的情况下，我能够使用快速搜索来加速对新元素的范围搜索，并不断扩展集合。 :) 我不确定在任意集合上进行完整范围搜索是否可以保证成功。在我的情况下，总是有多个具有相同距离值的局部最大值，但我不确定我们是否能证明永远不会出现小于绝对最大值的局部最大值。 - Zepee
是的，我认为在所有情况下都没有一种通用的方法可以避免扫描整个域。但是当你试图寻找优化时，你是正确的。 - Tim Biegeleisen
0
假设距离 d(a,b) = |a-b|，那么min和max中的一个总是会产生最大值。
证明：
假设您有一个不在端点的V。那么你有n1个低值和n2个高值。最小值处的总距离至少会比最大值处的总距离大(n1 - n2) * (max - V)，而最大值处的总距离至少会比最小值处的总距离大(n2 - n1) * (V - min)。
由于n1 - n2和n2 - n1中至少有一个非负，因此最大值总是可以在端点之一找到。
- Klas Lindbäck
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接