0

我在报告和位置之间有一对多的关系。我的目标是将我的报告列表缩小到尽可能少的包含所有代表位置的报告。

如果我将其简化为数字列表，它将如下所示，其中键是报告，数组是位置列表：

{
  1:[1,2],
  2:[1],
  3:[2,3],
  4:[1,3,4]
}

理想的解决方案是选择报告1 or 3和4. 要么 要么1可以3选择，因为它们都包括 Location和带有 Report的2重复 Location 。需要选择报告，因为它是唯一带有 Location 的报告。1444

效率不是主要问题。使用 PHP 缩小列表的最佳方法是什么？

4

2 回答 2

3

NP完全性再次出现。

您要解决的问题称为Set Cover，而且，果然是NP-Complete。

这意味着不太可能存在针对它的“高效”（读取，多项式时间）算法。

好消息是，有一些简单的近似算法可以给你一个不错的近似值。

请参阅此，了解“明显”的贪心算法（在每一点，选择具有最多未发现位置的报告）如何为您提供一个log (R)近似值，即R报告的数量在哪里（实际上，它甚至比这更好）。

于 2013-03-22T18:36:40.970 回答
1

如果效率不是您所说的问题，我可以向您推荐 O(2^n * k)算法，其中n是列表的数量，k是它们的长度之和。只需使用位掩码获取所有可能的组合，并为每个组合计算它是否涵盖所有内容。

PS这是一个实现（http://ideone.com/bAGpbL）：

$arr = array(
  0 => array(1,2),
  1 => array(1),
  2 => array(2,3),
  3 => array(1,3,4),
);
// It is assumed that all indexes are sequential starting from 0
$total_cover = array();
foreach($arr as $sub_arr) {
    foreach($sub_arr as $value) {
        $total_cover[$value] = true;
    }
}
$n = count($arr);
$best_cover = array_keys($arr);
for($i = 0; $i < (1 << $n); $i++) {
    $cover = array();
    $selected_list = array();
    for($j = 0; $j < $n; $j++) {
        if(($i >> $j) & 1) {
            $selected_list[] = $j;
            foreach($arr[$j] as $value) {
                $cover[$value] = true;
            }
        }
    }
    $good_cover = true;
    foreach($total_cover as $key => $value) {
        if(!isset($cover[$key])) {
            $good_cover = false;
            break;
        }
    }
    if($good_cover && count($selected_list) < count($best_cover)) {
        $best_cover = $selected_list;
    }
}
var_dump($best_cover);
于 2013-03-22T19:24:31.337 回答