パーティション化問題を解決するための再帰バックトラッキングアルゴリズム

Question

ねえ、私は各部品が（ほぼ）同じ合計を持つように、肯定的な数値の配列をK部品に分割するアルゴリズムを見つけるための助けを探しています...私たちが持っているとしましょう

1,2,3,4,5,6,7,8,8,9 en k = 3 thnアルゴリズムは、このように分割する必要があります1,2,3,4,5 | 6,7 | 8,9要素を変更することはできません...貪欲なアルゴリズムを見つけるのは簡単ですが、常に最適なソリューションを返すバックトラッキングバージョンを探しています...

アニヨーンはヒントがありますか？

Answer 1

リストなどの動的なデータ構造を使用しないソリューションは次のとおりです。それらはまったく不要であり、実際にはアルゴリズムを必要以上に遅くするでしょう。

ここではKをパーティションの数とし、nを配列内の要素の数とします。

int start[K];

void register() {
   /* calculate the error between minimum and maximum value partitions */
   /* partition boundaries are start[0], start[1], start[2], ... */
   /* if lower error than previously stored, remember the best solution */
}

void rec(int s, int k) {
  if (k == K) register();
  for (int i = s; i < N; i++) {
    start[k] = i;
    rec(i + 1, k + 1);
  }
}

/* entry */
start[0] = 0;
rec(1, 1);
/* then output the best solution found at register() */

注：これはO（n^k）アルゴリズム。これがそうであるため、それはサブエクスポン的です いいえ 一般的なNPコンプリートパーティションの問題に相当します。ここには、特定の合計セットの任意のサブセットの代わりに、線形配列の連続したセグメントを探しています。

Answer 2

最適なソリューションとはどういう意味ですか？私はあなたが最適なパーティションまでの各パーティション距離の合計を最小化するものを意味すると思います。最適なパーティションは、要素合計がパーティションの数を割った合計と等しいというパーティションです。

効率を気にしないなら、この大まかなアプローチはあなたにとって十分であるかもしれません。アルゴリズムをテストして正確さを確認していないので、注意してください。

void FindPartitions(int[] numbers, int i, IList<int>[] partitions, int currentPartition, IList<int>[] bestSolution, ref int minDistance)
{
    if (i == numbers.Length)
    {
        int sum = numbers.Sum();
        int avg = sum / partitions.Length;
        int currentDistance = 0;
        foreach (var partition in partitions)
            currentDistance += Math.Abs(partition.Sum() - avg);
        if (currentDistance < minDistance)
        {
            minDistance = currentDistance;
            for (int j = 0; j < partitions.Length; j++)
                bestSolution[j] = new List<int>(partitions[j]);
        }
    }
    else
    {
        partitions[currentPartition].Add(numbers[i]);
        FindPartitions(numbers, i + 1, partitions, currentPartition, bestSolution, ref minDistance);
        partitions[currentPartition].RemoveAt(partitions[currentPartition].Count - 1);
        if (currentPartition < partitions.Length - 1)
            FindPartitions(numbers, i, partitions, currentPartition + 1, bestSolution, ref minDistance);
    }
}

Answer 3

JavaScriptの再帰アルゴリズムです。この関数は、各ワーカーが割り当てられる合計を返します。入力配列のブックロードが、できるだけ公平に分割したい肯定的な数字の配列であるとしましょう（Kワーカーの間では）

これが機能するフィドルです：https://jsfiddle.net/missyalyssi/jhtk8vnc/3/

function fairWork(bookLoads, numWorkers = 0) {
    // recursive version

    // utilities
    var bestDifference = Infinity;
    var bestPartition = {};
    var initLoads = {};
    var workers = Array.from({length: numWorkers}, (val, idx) => {
      initLoads[idx] = 0;
      return idx;
    });
    var bookTotal = bookLoads.reduce((acc, curr) => {return acc + curr}, 0); 
    var average = bookTotal / bookLoads.length;

    // recursive function
    function partition(books = bookLoads, workers, loads={}) {

      // if only one worker give them all the books
      if (workers.length == 1 && books.length > 0) {
        var onlyWorker = workers[0];
        loads[onlyWorker] += books.reduce((acum, curr, idx, arr) => {
                               return acum + curr;
                             },0);
        books = [];
      }

      // base case
      if (books.length == 0) {
        var keys = Object.keys(loads);
        var total = 0;
        for (let key = 0; key < keys.length; key++) {
          // square so that difference shows 
          total += Math.pow(Math.abs(average - loads[keys[key]]), 2);
        }
        if (total < bestDifference) {
          bestDifference = total;
          bestPartition= loads;
        }
        return bestPartition;
      }

      var currBookLoad = books[0];

      // add book to curr worker 1
      var newWorker1Loads = Object.assign({}, loads);
      var worker1 = workers[0]; 
      newWorker1Loads[worker1] = newWorker1Loads[worker1] + currBookLoad || currBookLoad;
      partition(books.slice(1), workers, newWorker1Loads)

      // give to next worker
      var newNextWorkerLoads = Object.assign({}, loads);
      var worker2 = workers[1]; 
      newNextWorkerLoads[worker2] = newNextWorkerLoads[worker2] + currBookLoad || currBookLoad;
      partition(books.slice(1), workers.slice(1), newNextWorkerLoads)

      return bestPartition;
    }
    // function call
    return partition(bookLoads, workers, initLoads)
}
fairWork([3,1,2,3], 3)
//Result will be: Object {0: 3, 1: 3, 2: 3}
fairWork([1,2,3,4,5,6,7,8,9], 3)
//Result will be: Object {0: 15, 1: 13, 2: 17}