You need to enable JavaScript to run this app. Karmarkar-Karp启发式多路划分算法如何进行分区重构?
优惠活动
大模型
产品
解决方案
定价
更多

Karmarkar-Karp启发式多路划分算法如何进行分区重构?

Karmarkar-Karp k分区算法实现问题与PHP优化方案

我正在实现Karmarkar-Karp启发式数字划分算法的k分区版本,卡在第二阶段从生成的差集重构数字分区的步骤。目前能找到的唯一完整描述该第二阶段伪代码的资料是《Load balancing of multiphysics simulations by multi-criteria graph partitioning》论文的第58页。
以多重集S = [1,7,5,10,9,3]划分为3个(k=3)子集为例,算法分为两个阶段:

阶段1

首先将S降序排序:
S = [10,9,7,5,3,1]
之后将S中的每个数字转换为长度为k的元组,第一个元素为数字本身,其余为0,生成矩阵M:
M = [[10,0,0],[9,0,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
每一步从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]

阶段2

第二阶段基于生成的差集、存储的旧值和归一化数值构建分区,每一步弹出存储的旧值数组和归一化数值,执行过程如下:

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++ OOP实现,但我工作中需要将其改写为PHP版本。直接转译的实现内存效率低、运行速度慢:内存效率低是因为每个数字都被封装为Subset对象,运行慢是因为PHP中对象数组的排序速度比数字数组慢一个数量级。例如使用该方案将50万个数字划分为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();
}

内容的提问来源于stack exchange,提问作者Egor Nelyubov

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.11 15:18:04