logo标签列表

如何在Karmarkar-Karp启发式多向分区算法中重构分区？

algorithmpartition-problem
3
我正在尝试实现Karmarkar-Karp启发式数字分割算法的k-分割版本。但我在第二阶段中遇到了困难，即从差集重建数字分割。
我能找到的唯一详细描述第二阶段伪代码的来源是论文的第58页：多标准图分区的多物理模拟负载平衡。
给定多重集合S = [1,7,5,10,9,3]，将其划分为三个（k=3）子集，算法经历了两个阶段。
第一阶段：
首先按降序对S进行排序：
S = [10,9,7,5,3,1]
然后，将S中的每个数字转换为大小为k的元组，第一个条目是数字本身，其他条目都是零：
M = [[10,0,0],[9,0,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
这创建了矩阵M。
在每一步中，从M中删除(a, b, c)和(x, y, z)，并在原地形成一个新的元组：E := (a + x, b + y, c + z)。该元组通过其最小值进行归一化，并按降序排序，然后按顺序插入回M中。在每个步骤中，算法通过将它们放入两个堆栈中来记忆旧值数组([a, x], [b, y], [c, z])和用于归一化的数字。
M = [[10,0,0],[9,0,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
Old values: []
Norm. numbers: []


M = [[10,9,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
Old values: [([10,0],[0,0],[0,9])]
Norm. numbers: [0]


M = [[5,0,0],[3,0,0],[3,2,0],[1,0,0]]
Old values: [([10,0],[9,0],[0,7]), ([10,0],[0,0],[0,9])]
Norm. numbers: [7,0]


M = [[5,3,0],[3,2,0],[1,0,0]]
Old values: [([5,0],[0,0],[0,3]), ([10,0],[9,0],[0,7]), ([10,0],[0,0],[0,9])]
Norm. numbers: [0,7,0]


M = [[2,2,0],[1,0,0]]
Old values: [([5,0],[3,2],[0,3]), ([5,0],[0,0],[0,3]), ([10,0],[9,0],[0,7]), ([10,0],[0,0],[0,9])]
Norm. numbers: [3,0,7,0]


M = [[1,1,0]]
Old values: [([2,0],[2,0],[0,1]), ([5,0],[3,2],[0,3]), ([5,0],[0,0],[0,3]), ([10,0],[9,0],[0,7]), ([10,0],[0,0],[0,9])]
Norm. numbers: [1,3,0,7,0]

第二阶段：

第二阶段从差集、记忆的旧值和归一化数字中构建分区。

在每个步骤中，它会弹出记忆的旧值数组和归一化数字：

M = [[1],[1],[0]]
Old values: [[2,0],[2,0],[0,1]] 
Norm. number: 1

针对旧值数组中的每个元组，它会计算一个在 M 中搜索的值。
[2,0]: 2 + 0 - 1 = 1

然后在 M 中搜索包含该值的分区，并用该元组替换该值：
[[2,0],[1],[0]]


[2,0]: 2 + 0 - 1 = 1
=> [[2,0],[2,0],[0]]

在每次迭代中，它不会将两个元组放入同一个分区。因此，[0,1] 进入最后一个分区：
[0,1]: 0 + 1 - 1 = 0
=> [[2,0],[2,0],[0,1]]

等等：

M = [[2,0],[2,0],[0,1]]
Old values: [[5,0],[3,2],[0,3]] 
Norm. number: 3

M = [[0,0,5],[0,3,2],[1,0,3]]
Old values: [[5,0],[0,0],[0,3]] 
Norm. number: 0

问题来了：

M = [[0,0,0,5],[3,2,0,0],[1,0,0,3]]
Old values: [[10,0],[9,0],[0,7]] 
Norm. number: 7

[10,0]: 10 + 0 - 7 = 3
=> [[0,0,0,5],[10,0,2,0,0],[1,0,0,3]]

[9,0]: 9 + 0 - 7 = 2
=> ???

我已经在这个迭代中将[10,0]元组放入了[3,2,0,0]分区，所以我不能再将另一个元组放入其中。但是，M没有包含值2的其它分区。

如果允许在出现这种情况时将多个元组放入同一个分区，那么得到的分区将远非最优：

[[0,0,0,0,5,7],[0,0,0,0,0,0,10,9],[1,0,0,3]]

我认为我可以使用最大二分匹配来解决这个问题，但这感觉像是一个肮脏的技巧。

我是否漏掉了一些重要的步骤或者有更好的方法来重构分区？

结论：

David Eisenstat提供了一个优雅且快速的C++面向对象实现算法。

但是，由于我的工作需要，我需要将其改写为PHP语言。直接翻译实现代码会导致内存效率低下和速度慢。内存效率低下是因为每个数字都被包装成一个子集对象。而且，使用PHP对对象数组进行排序比对数字数组进行排序要慢一个数量级。例如，在使用这种方法将500000个数字分成100个子集时，需要138秒，而我的贪心算法实现只需要9秒。

经过两天的性能分析，我使用数组重新编写了PHP实现。它看起来很丑陋，但在k值较低时，它的性能优于我的贪心算法实现，并且在k值较高时速度不会太慢：

K: 2
Greedy: 330 (seconds)
Karmarkar–Karp: 6

K: 4
Greedy: 177
Karmarkar–Karp: 6

K: 8
Greedy: 85
Karmarkar–Karp: 6

K: 16
Greedy: 43
Karmarkar–Karp: 8

K: 32
Greedy: 21
Karmarkar–Karp: 11

K: 64
Greedy: 11
Karmarkar–Karp: 20

K: 128
Greedy: 8
Karmarkar–Karp: 33

K: 256
Greedy: 3
Karmarkar–Karp: 61

我希望David Eisenstat的答案和我的解决方案都能对您有所帮助。

<?php

function greedy(array $array, int $k) : array
{
    $result = new \Ds\PriorityQueue();

    for ($i = 0; $i < $k; $i++)
    {
        $result->push([], 0);
    }

    sort($array, SORT_NUMERIC);

    while (!empty($array))
    {
        $number = array_pop($array);
        $smallestSumArray = $result->pop();

        $smallestSumArray [] = $number;
        $sum = array_sum($smallestSumArray);
        $result->push($smallestSumArray, -$sum);
    }

    return $result->toArray();
}

function karmarkarKarp(array $array, int $k) : array
{
    $id = PHP_INT_MIN;

    $heap = new \Ds\PriorityQueue();
    $idToNumbers = new \Ds\Map();
    $idToSum = new \Ds\Map();

    /**
     * Convert every number into an ID that is connected with a numbers array using $idToNumbers map
     * and with a sum using $idToSum map
     */
    foreach ($array as $number)
    {
        $idToNumbers[$id] = new \Ds\Stack([$number]);
        $idToSum[$id] = $number;
        $heap->push([$id], $number);
        ++$id;
    }
 
    //Partitioning:

    $sumToId = [];

    while ($heap->count() > 1)
    {
        /** @var array $a */
        $a = $heap->pop();
        /** @var array $b */
        $b = $heap->pop();

        for ($i = 0; $i < $k; $i++)
        {
            $reverseI = $k - 1 - $i;

            if (!isset($a[$i]) && !isset($b[$reverseI])) // Instead of filling k-tuple with zeroes just check that a position is set
            {
                continue;
            }

            if (!isset($a[$i]) || !isset($b[$reverseI]))
            {
                $Ai = $a[$i] ?? $b[$reverseI];
                unset($a[$i], $b[$reverseI]);
                $sum = $idToSum[$Ai];

                isset($sumToId[$sum]) ? $sumToId[$sum] []= $Ai : $sumToId[$sum] = [$Ai];

                continue;
            }

            /** @var int $Ai */
            $Ai = $a[$i];

            /** @var int $Bk */
            $Bk = $b[$reverseI];

            unset($a[$i], $b[$reverseI]);

            $aNumbers = $idToNumbers[$Ai];
            $bNumbers = $idToNumbers[$Bk];

            while (!$bNumbers->isEmpty())
            {
                $aNumbers->push($bNumbers->pop());
            }

            $sum = $idToSum[$Ai] + $idToSum[$Bk];

            $idToSum[$Ai] = $sum;

            isset($sumToId[$sum]) ? $sumToId[$sum] []= $Ai : $sumToId[$sum] = [$Ai];

            $idToNumbers->remove($Bk);
            $idToSum->remove($Bk);
        }

        krsort($sumToId); // It's faster than using usort() to sort $a by sums in $idToSum map

        $a = array_merge(...$sumToId);

        $sumToId = [];

        $difference = $idToSum[$a[0]] - (isset($a[$k -1]) ? $idToSum[$a[$k -1]] : 0);

        $heap->push($a, $difference);
    }

    //Preparing the resulting array:

    /** @var array $last */
    $last = $heap->pop();

    array_walk($last, function (&$item) use ($idToNumbers) {
        /** @var \Ds\Stack $numbersStack */
        $numbersStack = $idToNumbers[$item];

        $item = [];

        while (!$numbersStack->isEmpty())
        {
            $item []= $numbersStack->pop();
        }
    });

    return $last;
}

$randomArray = [];

for ($i = 0; $i < 500000; $i++)
{
    $randomArray []= random_int(1, 6000);
}

for ($k = 2; $k <= 256; $k *= 2)
{
    echo PHP_EOL . 'K: ' . $k;

    $time = time();
    $result = greedy($randomArray, $k);
    echo PHP_EOL . 'Greedy: ' . (time() - $time);

    gc_mem_caches();

    $time = time();
    $result = karmarkarKarp($randomArray, $k);
    echo PHP_EOL . 'Karmarkar–Karp: ' . (time() - $time) . PHP_EOL;

    gc_mem_caches();
}
1个回答
2

我会使用一阶段实现这个算法，添加数据结构来跟踪与每个总和相关的子集。以下是C++代码：

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <list>
#include <memory>
#include <vector>

namespace {

using Number = std::uint64_t;

class Subset {
 public:
  Subset() : numbers_{}, sum_{} {}
  explicit Subset(const Number number) : numbers_{number}, sum_{number} {}

  Subset(Subset&&) = default;
  Subset& operator=(Subset&&) = default;

  const std::list<Number>& numbers() const { return numbers_; }

  Number sum() const { return sum_; }

  void Merge(Subset other) {
    numbers_.splice(numbers_.end(), other.numbers_);
    sum_ += other.sum_;
  }

 private:
  Subset(const Subset&) = delete;
  Subset& operator=(const Subset&) = delete;

  std::list<Number> numbers_;
  Number sum_;
};

std::ostream& operator<<(std::ostream& stream, const Subset& subset) {
  stream << '[';
  if (!subset.numbers().empty()) {
    auto it{subset.numbers().begin()};
    stream << *it;
    for (++it; it != subset.numbers().end(); ++it) {
      stream << ',' << *it;
    }
  }
  stream << ']';
  return stream;
}

struct SubsetSumGreater {
  bool operator()(const Subset& a, const Subset& b) const {
    return a.sum() > b.sum();
  }
};

class Partition {
 public:
  Partition(const Number number, const std::size_t k) : subsets_(k) {
    assert(k > 0);
    subsets_.front().Merge(Subset{number});
  }

  Partition(Partition&&) = default;
  Partition& operator=(Partition&&) = default;

  const std::vector<Subset>& subsets() const { return subsets_; }

  Number difference() const {
    return subsets_.front().sum() - subsets_.back().sum();
  }

  void Merge(Partition other) {
    assert(subsets_.size() == other.subsets_.size());
    auto it{subsets_.begin()};
    auto other_it{other.subsets_.rbegin()};
    while (it != subsets_.end() && other_it != other.subsets_.rend()) {
      it->Merge(std::move(*other_it));
      ++it;
      ++other_it;
    }
    std::sort(subsets_.begin(), subsets_.end(), SubsetSumGreater{});
  }

 private:
  Partition(const Partition&) = delete;
  Partition& operator=(const Partition&) = delete;

  std::vector<Subset> subsets_;
};

std::ostream& operator<<(std::ostream& stream, const Partition& partition) {
  stream << '[';
  if (!partition.subsets().empty()) {
    auto it{partition.subsets().begin()};
    stream << *it;
    for (++it; it != partition.subsets().end(); ++it) {
      stream << ',' << *it;
    }
  }
  stream << ']';
  return stream;
}

struct DifferenceLess {
  bool operator()(const Partition& a, const Partition& b) const {
    return a.difference() < b.difference();
  }
};

Partition KarmarkarKarp(const std::vector<Number>& numbers,
                        const std::size_t k) {
  assert(!numbers.empty());
  assert(k > 0);
  std::vector<Partition> heap;
  heap.reserve(numbers.size());
  for (const Number number : numbers) {
    heap.emplace_back(number, k);
  }
  std::make_heap(heap.begin(), heap.end(), DifferenceLess{});
  while (heap.size() > 1) {
    std::pop_heap(heap.begin(), heap.end(), DifferenceLess{});
    Partition partition{std::move(heap.back())};
    heap.pop_back();
    std::pop_heap(heap.begin(), heap.end(), DifferenceLess{});
    heap.back().Merge(std::move(partition));
    std::push_heap(heap.begin(), heap.end(), DifferenceLess{});
  }
  return std::move(heap.front());
}

}  // namespace

int main() { std::cout << KarmarkarKarp({1, 7, 5, 10, 9, 3}, 3) << '\n'; }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接