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 当前被拆分为两 block ，7 和 8，我们可以将其拆分为三 block ，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.

我们又 split 了 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.

我们又 split 了 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。

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