0

レポートと場所の間には1対多の関係があります。私の目標は、レポートのリストを、表示されているすべての場所を含むレポートをできるだけ少なくすることです。

番号のリストに単純化すると、次のようになります。キーはレポートで、配列は場所のリストです。

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

理想的な解決策は、レポート1 or 3とを選択すること4です。どちらか1または3が選択される可能性があります。これは、両方に場所が含まれ、レポートで2場所が重複しているためです。レポートはLocationを持つ唯一のレポートであるため、選択する必要があります。1444

効率は大きな問題ではありません。PHPを使用してリストを絞り込むための最良の方法はどのようになっていますか？

4

2 に答える 2

3

NP完全性が再び発生します。

あなたが解決しようとしている問題は集合被覆と呼ばれ、確かにNP完全です。

これは、そのための「効率的な」（読み取り、多項式時間）アルゴリズムが存在する可能性が低いことを意味します。

良いニュースは、まともな近似を提供する単純な近似アルゴリズムがあることです。

「明らかな」欲張りアルゴリズム（各ポイントで、カバーされていない場所の数が最も多いレポートを選択する）がどのように概算を与えるかについては、これを参照してください。ここで、はレポートの数です（実際にはそれよりも優れています）。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 に答える