algorithm - 最大化序列中数字之间的差异

Question

我需要一些帮助来找到解决以下问题的算法的总体思路。这个问题是在作业中交给我的。看起来应该可以通过贪心的方法解决，但我想不出一个简单的解决方案。以下是问题描述：

给你一个由N个数字组成的序列，a_1 ... a_n使得0 = a_1 < a_2 < ... < a_n. 您必须最多 消除这些数字中的 Ma_i+1 - a_i个，以使任意两个连续数字之间的最小差异最大化。

您可能无法消除第一个和最后一个元素，a_0并且a_n. 此外，您必须消除尽可能少的数字：如果消除M - 1您得到最短距离D并且消除M您仍然具有相同的最小差，则您不能消除最后一个数字。

我不是要求这个问题的完整解决方案。关于算法的外观只有一些指导方针。

编辑：一些测试样本。请记住，可能有多个有效的解决方案。

Remove at most 7 from:
0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100

Solution:
0 7 15 26 31 38 44 53 60 73 80 88 93 100

Remove at most 8 from:
0 3 7 10 15 26 38 44 53 61 76 80 88 93 100

Solution:
0 15 38 53 76 88 100

Answer 1

[编辑：我最初声称ElKamina 的答案是错误的，但我现在确信它不仅是正确的，而且与我（后来的）答案几乎相同 :-P 虽然我的口味仍然有点简洁！]

这是一个精确的O(NM^2) 时间、O(NM) 空间 动态规划算法，可以在毫秒内获得所有 OP 示例的正确答案。基本思想是：

1. 每当我们施加不应该删除特定数字的约束时，它就会在两个子问题之间形成一道“栅栏”，从而以最优方式解决每个子问题，从而保证在该约束到位的情况下对整个问题的最优解，并且
2. 每个最优解必须以一个未删除的数字开始，然后是一些连续删除的数字，然后是一个未删除的数字，然后是从第二个未删除的数字开始的问题剩余部分的最优解，并且使用适当减小的 M。

下面，x[i] 表示列表中的第 i 个数字，索引从 0 开始。

递归

令 f(i, j) 是可从位置 0 <= i < N 开始的数字列表的后缀获得的最佳（最大最小）间隔大小，方法是保留这个（即第 i 个）数字并精确删除后面的 j (不一定是连续的）数字。以下递归显示了如何计算它：

f(i, j) = max(g(i, j, d)) over all 0 <= d <= min(j, N-i-2)
g(i, j, d) = min(x[i+d+1] - x[i], f(i+d+1, j-d))

存在而min(j, N-i-2)不是简单的 j 以防止删除“结束”。我们需要的唯一基本情况是：

f(N-1, 0) = infinity (this has the effect of making min(f(N-1), 0), z) = z)
f(N-1, j > 0) = 0 (this case only arises if M > N - 2)

这个怎么运作

更详细地说，为了计算 f(i, j)，我们要做的是遍历从位置 i+1 开始的所有可能的连续删除数（包括零），在每种情况下计算 (a) 由下式形成的区间的最小值该删除块和（b）从该块右侧的第一个未删除数字开始的子问题的最佳解决方案。 重要的是要指定块中的第一个数字 (x[i]) 不会被删除，这样前一个（父）子问题的间隔总是“上限”。 这是一个棘手的部分，我花了一段时间才弄清楚。

让它快速

如果你编写上面的普通递归，它会起作用，但它会花费 M 和 N 的指数时间。通过记忆f()，我们保证它的主体将最多运行 N * M 次（每个不同的参数组合一次） . 每次函数运行时，它都会对越来越长的删除块执行 O(M) 工作扫描，总共需要 O(NM^2) 时间。

您不能通过使用更少的删除来创建更大的间隙，因此可以通过查看 M+1 个结果 f(0, M), f(0, M-1), ..., f 找到总体最大的最小间隔大小(0, 0) 表示小于前一个数字的第一个数字：前一个数字是答案，f() 的第二个参数是所需的最小删除次数。要找到最佳解决方案（即删除的特定数字的列表），您可以将做出的决定记录在单独的前驱数组中，以便 p[i, j] 给出 d 的值（可以转换为i 和 j) 导致 f(i, j) 的最优解。（也许这里的“前辈”是混淆的：它指的是之前解决的子问题当前子问题，尽管这些子问题出现在表示当前子问题的后缀“之后”（右侧）。）然后可以遵循这些链接来恢复做出的删除/不删除决定。

工作 C++ 代码

http://ideone.com/PKfhDv

附录：早期失误

对于像这样一个棘手的问题，查看错误的方法并准确了解它们出错的地方会很有帮助...... :-/ 我以为我已经解决了这个问题，但我没有注意到返回解决方案的要求使用尽可能少的删除，我最初尝试解决这个问题并没有奏效。

起初，我尝试将 f(i, j) 定义为可从从位置 0 <= i < N 开始的数字列表的后缀获得的最佳（最大最小）间隔大小，方法是保留这个（即第 i 个）数字并删除任何地方从 0 到 j后面的（不一定是连续的）数字。但这引起了一个微妙的问题：您不一定可以从最佳解决方案到子问题的最佳解决方案中组装出最佳解决方案。我最初认为这可以通过更改函数以返回一个（间隔大小，实现该间隔大小所需的最小删除数）对而不只是一个间隔大小来解决，并让它打破共享最大最小间隔的动作之间的联系通过始终选择最小化删除次数的操作来确定大小。但一般情况下并非如此，因为子问题的最优解（即数字列表的某些后缀）将花费删除使该区域中的最小间隔大小尽可能大，即使这些删除被证明是浪费的，因为完整解决方案的前缀无论如何都会迫使整体最小值降低。这是一个使用 f() 的反例，它返回（间隔大小，达到该大小所需的最小删除数）对：

Problem: M = 1, X = [10 15 50 55].

f(2, 0) = (5, 0) (leaving [50 55])
f(1, 1) = (40, 1) (delete 50 to leave [15 55]); *locally* this appears better
          than not deleting anything, which would leave [15 50 55] and yield
          a min-gap of 5, even though the latter would be a better choice for
          the overall problem)
f(0, 1) = max(min(5, f(1, 1)), min(40, f(2, 0))
        = max(min(5, 40), min(40, 5))
        = (5, 1) (leaving either [10 15 55] or [10 50 55])

我没有展示 f(0, 1) 返回的对的第二个元素的工作，因为它很难简洁地表达，但显然它会是 1，因为两种选择都需要删除 1 次。

Answer 2

使用动态规划。

线索 X(i,j) 包含与前 i 个元素的最小距离，其中 j 被选中（即未删除）。

这将为您提供准确的解决方案。复杂度 = O(MN^2)，因为对于每个 i 值，只有 M 个 j 的有效值，并且每次调用函数都需要做 O(M) 的工作。

设元素为 A1,A2,...,An

更新公式为：

X(i+1,j+1) = Max( Min(A(i+1)-Ak, Xkj) for k<=i)

[由 j_random_hacker 编辑以添加评论中的信息]

Answer 3

我想我得到了解决方案。它至少适用于两个样本集。它不一定返回与答案相同的集合，但它返回的集合具有相同的最小值。它也是迭代和贪婪的，这很好，并且有很多方法可以优化它。看起来它是 MLog(N)。

重要的是要意识到数字并不重要——只有它们之间的差异才重要。当你“删除一个数字”时，你实际上只是结合了两个相邻的差异。我的算法将专注于差异。回到导致这些差异的项目并在你去的时候删除是一件简单的事情。

算法

1. 创建每个数字之间差异的有序列表/数组。
2. 找到最小的差异x。如果x的计数> 剩余的 M，则停止。你已经处于最佳状态。
3. 对于从最左边开始的每个x值，将该差异与较低的邻居组合（并删除该x）。如果邻居的值相等，则您的决定是任意的。如果只有一个邻居的值为x，则与另一个邻居合并。（如果您别无选择，例如 [1, 1, ...]，则与匹配的X组合，但如果可以，请避免使用。）
4. 返回第 2 步，直到用完M。

算法说明

第 3 步有一个点，我将其标记为任意决定。可能不应该是这样，但是您遇到了足够多的情况，这是您要添加多少复杂性的问题。这种任意性允许存在多个不同的正确答案。如果您看到两个具有相同值的邻居，此时，我说任意选择一个。理想情况下，您可能应该检查距离为 2 的邻居，然后是 3，以此类推，并支持较低的邻居。如果您在扩展时遇到边缘，我不确定该怎么办。最终，要完美地完成这部分，您可能需要递归调用此函数并查看哪个评估更好。

遍历样本数据

先第二个：

最多删除 8 个： 0 3 7 10 15 26 38 44 53 61 76 80 88 93 100

[3, 4, 3, 5, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 8

删除 3's。边缘上的移除只能在一个方向上添加：

[7, 3, 5, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 7

[7, 8, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 6

接下来，去掉 4：[7, 8, 11, 12, 6, 9, 8, 15, 12, 5, 7] M = 5

接下来，去掉 5：[7, 8, 11, 12, 6, 9, 8, 15, 12, 12] M = 4

接下来，去掉 6：[7, 8, 11, 12, 15, 8, 15, 12, 12] M = 3

接下来，去掉 7: [15, 11, 12, 15, 8, 15, 12, 12] M = 2

接下来去掉8: [15, 11, 12, 15, 23, 12, 12] M = 1 // 注意，任意决定添加方向

最后，去掉 11: [15, 23, 15, 23, 12, 12]

请注意，在答案中，最低差值为 12。

第一个最后一个

最多删除 7 个： 0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100

[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 7, 1, 12, 3, 4, 1, 7, 5, 7] M = 7

删除 1：

[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 4, 1, 7, 5, 7] M = 6

[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 5

剩下 4 个 3，所以我们可以删除它们：

[7, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 4

[7, 8, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 3

[7, 8, 11, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 2 // 注意右边任意加

[7, 8, 11, 5, 7, 6, 9, 8, 12, 8, 5, 7, 5, 7] M = 1

接下来我们将删除 5，但只允许删除 1，并且有 3，所以我们在这里停止。我们的最低差是 5，匹配解决方案。

注意：对于 SauceMaster 提出的 1、29、30、31、59 案例，从组合相同X值到避免这样做的想法进行了编辑。

Answer 4

我希望不要使用所有组合的方法，但经过多次尝试，这似乎是将我的结果与 j_random_hacker 匹配的唯一方法。（下面的一些评论与此答案的早期版本有关。）我对 j_random_hacker/ElKamina 的算法在 Haskell（'jrhMaxDiff'）中的简洁表达印象深刻。他的函数“compareAllCombos”查找我们两种方法结果的差异：

*Main> compareAllCombos 7 4 4
Nothing

算法：

1. Group the differences: [0, 6, 11, 13, 22] => [[6],[5],[2],[9]]

2. While enough removals remain to increase the minimum difference, extend the 
   minimum difference to join adjacent groups in all possible ways:

   [[6],[5],[2],[9]] => [[6],[5,2],[9]] and [[6],[5],[2,9]]...etc.

   Choose the highest minimum difference and lowest number of removals.

哈斯克尔代码：

import Data.List (minimumBy, maximumBy, groupBy, find)
import Data.Maybe (fromJust)

extendr ind xs = 
  let splitxs = splitAt ind xs
      (y:ys) = snd splitxs
      left = snd y
      right = snd (head ys)
  in fst splitxs ++ [(sum (left ++ right), left ++ right)] ++ tail ys

extendl ind xs = 
  let splitxs = splitAt ind xs
      (y:ys) = snd splitxs
      right = snd y
      left = snd (last $ fst splitxs)
  in init (fst splitxs) ++ [(sum (left ++ right), left ++ right)] ++ tail (snd splitxs)

extend' m xs =
  let results = map (\x -> (fst . minimumBy (\a b -> compare (fst a) (fst b)) $ x, x)) (solve xs)
      maxMinDiff = fst . maximumBy (\a b -> compare (fst a) (fst b)) $ results
      resultsFiltered = filter ((==maxMinDiff) . fst) results
  in minimumBy (\a b -> compare (sum (map (\x -> length (snd x) - 1) (snd a))) (sum (map (\x -> length (snd x) - 1) (snd b)))) resultsFiltered
   where 
     solve ys = 
       let removalCount = sum (map (\x -> length (snd x) - 1) ys)
           lowestElem = minimumBy (\a b -> compare (fst a) (fst b)) ys
           lowestSum = fst lowestElem
           lowestSumGrouped = 
             map (\x -> if (fst . head $ x) == 0 
                           then length x 
                           else if null (drop 1 x) 
                                   then 1 
                                   else if odd (length x)
                                           then div (length x + 1) 2
                                           else div (length x) 2)
             $ filter ((==lowestSum) . fst . head) (groupBy (\a b -> (fst a) == (fst b)) ys)
           nextIndices = map snd . filter ((==lowestSum) . fst . fst) $ zip ys [0..]
           lastInd = length ys - 1
       in if sum lowestSumGrouped > m - removalCount || null (drop 1 ys)
             then [ys]
             else do
               nextInd <- nextIndices          
               if nextInd == 0
                  then solve (extendl (nextInd + 1) ys)
                  else if nextInd == lastInd
                          then solve (extendr (nextInd - 1) ys)
                          else do 
                            a <- [extendl nextInd ys, extendr nextInd ys]
                            solve a

pureMaxDiff m xs = 
  let differences = map (:[]) $ tail $ zipWith (-) xs ([0] ++ init xs)
      differencesSummed = zip (map sum differences) differences
      result = extend' m differencesSummed
      lowestSum = fst result
      removalCount = sum (map (\x -> length (snd x) - 1) (snd result))
  in if null (filter ((/=0) . fst) differencesSummed)
        then (0,0)
        else (removalCount, lowestSum)

-- __j_random_hacker's stuff begins here

-- My algorithm from http://stackoverflow.com/a/15478409/47984.
-- Oddly it seems to be much faster when I *don't* try to use memoisation!
-- (I don't really understand how memoisation in Haskell works yet...)
jrhMaxDiff m xs = fst $ fromJust $ find (\(x, y) -> snd x > snd y) resultPairsDesc
  where
    inf = 1000000
    n = length xs
    f i j =
      if i == n - 1
         then if j == 0
                 then inf
                 else 0
         else maximum [g i j d | d <- [0 .. min j (n - i - 2)]]
    g i j d = min ((xs !! (i + d + 1)) - (xs !! i)) (f (i + d + 1) (j - d))
    resultsDesc = map (\i -> (i, f 0 i)) $ reverse [0 .. m]
    resultPairsDesc = zip resultsDesc (concat [(tail resultsDesc), [(-1, -1)]])

-- All following code is for looking for different results between my and groovy's algorithms.
-- Generate a list of all length-n lists containing numbers in the range 0 - d.
upto 0 _ = [[]]
upto n d = concat $ map (\x -> (map (\y -> (x : y)) (upto (n - 1) d))) [0 .. d]

-- Generate a list of all length-maxN or shorter lists containing numbers in the range 0 - maxD.
generateAllDiffCombos 1 maxD = [[x] | x <- [0 .. maxD]]
generateAllDiffCombos maxN maxD =
  (generateAllDiffCombos (maxN - 1) maxD) ++ (upto maxN maxD)

diffsToNums xs = scanl (+) 0 xs

generateAllCombos maxN maxD = map diffsToNums $ generateAllDiffCombos maxN maxD

-- generateAllCombos causes pureMaxDiff to produce an error with (1, [0, 0]) and (1, [0, 0, 0]) among others,
-- so filter these out to look for more "interesting" differences.
--generateMostCombos maxN maxD = filter (\x -> length x /= 2) $ generateAllCombos maxN maxD
generateMostCombos maxN maxD = filter (\x -> length x > 4) $ generateAllCombos maxN maxD

-- Try running both algorithms on every list of length up to maxN having gaps of
-- size up to maxD, allowing up to maxDel deletions (this is the M parameter).
compareAllCombos maxN maxD maxDel =
  find (\(x, maxDel, jrh, grv) -> jrh /= grv) $ map (\x -> (x, maxDel, jrhMaxDiff maxDel x, pureMaxDiff maxDel x)) $ generateMostCombos maxN maxD
--  show $ map (\x -> (x, jrhMaxDiff maxDel x, pureMaxDiff maxDel x)) $ generateMostCombos maxN maxD