algorithm - シーケンス内の数値間の差を最大化する

Question

次の問題を解決するためのアルゴリズムの一般的なアイデアを見つけるのに助けが必要です。問題は課題で私に与えられました。貪欲な方法で解決できるはずですが、簡単な解決策がわかりません。問題の説明は次のとおりです。

となるN個の数列が与えられa_1 ... a_nます0 = a_1 < a_2 < ... < a_n。任意の 2 つの連続する数値間の最小差が最大になるように、 最大​​で M個のこれらの数値を削除する必要があります。a_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つのサブ問題の間に「フェンス」が形成されます。
2. すべての最適なソリューションは、削除されていない番号で始まり、いくつかの連続した削除された番号、削除されていない番号、2番目の削除されていない番号で始まる問題の残りの部分に対する最適なソリューションが続く必要があります。適切に縮小されたMを使用します。

以下では、x [i]はリスト内のi番目の番号を意味し、インデックスは0から始まります。

再帰

f（i、j）を、位置0 <= i <Nで始まる番号リストの接尾辞から取得できる最適な（最大の最小）間隔サイズとします。これは、この（つまりi番目の）番号を保持し、後の（i番目の）番号を正確に削除することによって行われます。必ずしも連続していない）番号。次の再帰は、これを計算する方法を示しています。

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回実行されることを保証します（個別のパラメーターの組み合わせごとに1回） 。関数が実行されるたびに、全体としてO（NM ^ 2）時間の間、ますます長くなる削除ブロックをスキャンするO（M）作業が実行されます。

より少ない削除を使用してより大きなギャップを作成することはできないため、M + 1の結果f（0、M）、f（0、M-1）、...、fを調べることで、全体として最大の最小間隔サイズを見つけることができます。前の番号よりも小さい最初の番号の場合は（0、0）：その前の番号が答えであり、f（）の2番目の引数は必要な削除の最小数です。最適な解決策（つまり、削除された特定の数値のリスト）を見つけるために、別の先行配列で行われた決定を記録して、p [i、j]がdの値（以前の値に変換できる）を与えることができます。 f（i、j）の最適解につながるiとj）。（おそらく「前任者」はここで混乱しています：それは前に解決されたサブ問題を指します現在のサブ問題。ただし、これらのサブ問題は、現在のサブ問題を表すサフィックスの「後」（右側）に表示されます。）これらのリンクをたどると、行われた削除/削除禁止の決定を回復できます。

動作するC++コード

http://ideone.com/PKfhDv

補遺：初期の失敗

このようなトリッキーな問題では、間違ったアプローチを見て、どこが間違っていたかを正確に確認することが役立つ場合があります...：-/問題は解決したと思いましたが、解決策を返す必要があることに気づいていませんでしたそれは可能な限り少ない削除を使用し、これを修正するための私の最初の試みはうまくいきませんでした。

最初に、f（i、j）を、位置0 <= i <Nで始まる番号リストのサフィックスから取得できる最適な（最大の最小）間隔サイズとして定義しようとしました。 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）によって返されるペアの2番目の要素の動作を示していませんが、両方の選択肢で1つの削除が必要なため、明らかに1になります。

Answer 2

動的計画法を使用します。

手がかり X(i,j) には、最初の i 要素とその中で j が選択された (つまり、削除されていない) 最小距離が含まれます。

これにより、正確な解決策が得られます。複雑さ = O(MN^2)。各 i 値には j の有効な値が M 個しかないため、関数の呼び出しごとに O(M) の作業を行う必要があります。

要素を A1、A2、...、An とする

更新の式は次のとおりです。

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

[コメントから情報を追加するために j_random_hacker が編集]

Answer 3

私は解決策を得たと思います。少なくとも 2 つのサンプル セットでは機能します。必ずしも答えと同じセットを返すとは限りませんが、返されるセットの最小値は同じです。それは反復的で貪欲でもあり、それは素晴らしいことであり、最適化する方法はたくさんあります。MLog(N)のようです。

重要なことは、数値は重要ではなく、それらの違いだけが重要であることを理解することです。「数字を削除」すると、実際には隣接する 2 つの違いを組み合わせているだけです。私のアルゴリズムはその違いに焦点を当てます。これらの違いの原因となった項目に戻って、削除するのは簡単なことです。

アルゴリズム

1. 各数値の違いの順序付きリスト/配列を作成します。
2. 最小差xを見つけます。xのカウント> 残りの M の場合、停止します。あなたはすでに最高の状態にいます。
3. 左端から始まるxの各値について、その差を隣接する値の小さい方と組み合わせます (そしてそのxを削除します)。隣人の値が等しい場合、決定は任意です。xの値を持つ近傍が 1 つだけの場合は、他の近傍と結合します。([1, 1, ...] のように選択肢がない場合は、対応するXと組み合わせますが、可能であれば避けてください。)
4. Mがなくなるまでステップ 2 に戻ります。

アルゴリズムに関する注意事項

ステップ 3 には、任意の決定とラベル付けした点があります。おそらくそうあるべきではありませんが、どれだけ複雑にするかが問題になるほどエッジの効いたケースに陥っています。この恣意性が、複数の異なる正解が存在することを可能にします。同じ値を持つ隣人が 2 つある場合は、この時点で任意に 1 つを選択します。理想的には、おそらく 2 離れている隣人のペアをチェックし、次に 3 など、低い方を優先する必要があります。展開中にエッジに当たってしまったらどうしよう。最終的に、この部分を完全に実行するには、この関数を再帰的に呼び出して、どちらがより適切に評価されるかを確認する必要がある場合があります。

サンプル データのウォークスルー

2番目の最初：

0 3 7 10 15 26 38 44 53 61 76 80 88 93 100 から最大 8 個を削除します。

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

3 を削除します。エッジの削除は、一方向にのみ追加できます。

[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 であることに注意してください。

最初の 1 つ最後

0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100 から最大 7 個を削除します。

[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」は、2 つのメソッドの結果の違いを探します。

*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.

Haskell コード:

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