algorithm - 有什么算法可以平衡地将N条线段分割成M条线(N <= M)？

Question

也许是一个微不足道的问题，但我正在寻找一种算法，可以以平衡的方式将 N 线段分割成 M 段(M >= N)(例如，R^2 r 平方最大化)。有人有好的引用吗？

编辑(根据评论者的要求添加示例):

例如，让 N = 5长度段:{1, 10, 7, 15, 1}我们想把它分成 M = 7零件。

• 一个好的解决方案是:{1, 1, 5, 5, 7, 7, 8} (分为 15 和 10)
• 一个糟糕的解决方案是:{1, 1, 5, 5, 5, 7, 10} (将 15 分成 3)

我猜，是一个贪婪算法 distance from avg作为一种启发式方法可以做得很好，但不确定是否存在一些极端情况。

谢谢

Answer 1

这个问题实际上不是 NP-hard，因为不可能重新组合各个部分。这是一个 O(m log n) 时间算法，用于解决确定切割以最小化所得碎片长度平方和的问题。将每个段的分割计数初始化为 1，并将它们放入优先级队列中(我将很快指定优先级)。重复以下操作 m - n 次:拉出最上面的段(最高优先级)，增加其拆分计数，然后将其放回队列中。

每个段的优先级是其当前划分的平方和减去其假设划分为另一段的平方和。例如，如果 15 当前被分割为两部分，7 和 8，我们可以将其分割为三部分，即 5、5 和 5，则优先级为 7^2 + 8^2 - 5^2 - 5^2 - 5^2 = 38。为了运行您的示例，初始优先级队列是

15 (1 cut), priority 15^2 - 7^2 - 8^2 = 112
10 (1 cut), priority 10^2 - 5^2 - 5^2 =  50
 7 (1 cut), priority  7^2 - 3^2 - 4^2 =  24
 1 (1 cut), priority  1^2 - 0^2 - 1^2 =   0
 1 (1 cut), priority  1^2 - 0^2 - 1^2 =   0.

我们又分了15次。

10 (1 cut ), priority 10^2       - 5^2 - 5^2       = 50
15 (2 cuts), priority  7^2 + 8^2 - 5^2 - 5^2 - 5^2 = 38
 7 (1 cut ), priority  7^2       - 3^2 - 4^2       = 24
 1 (1 cut ), priority  1^2       - 0^2 - 1^2       =  0
 1 (1 cut ), priority  1^2       - 0^2 - 1^2       =  0.

我们又分了10次。

15 (2 cuts), priority 7^2 + 8^2 - 5^2 - 5^2 - 5^2 = 38
10 (2 cuts), priority 5^2 + 5^2 - 3^2 - 3^2 - 4^2 = 16
 7 (1 cut ), priority 7^2       - 3^2 - 4^2       = 24
 1 (1 cut ), priority 1^2       - 0^2 - 1^2       =  0
 1 (1 cut ), priority 1^2       - 0^2 - 1^2       =  0.

我们就到此为止；接下来是 15，即 1, 1, 5, 5, 5, 5, 5, 7。

这种“贪婪”算法是最优的，因为将一个片段分割成更多片段的返回是独立的，并且在精确的技术意义上是递减的(超模块化)。