8

テーブルに約 2M のレコードが格納されています。各レコードには、数と約 5K のブール属性があります。

ということで、表はこんな感じ。

3, T, F, T, F, T, T, ...
29, F, F, T, F, T, T, ...
...
-87, T, F, T, F, T, T, ...
98, F, F, T, F, F, T, ...

そしてSUM(A, B)、Ath 属性と Bth 属性が真である数の合計として定義しました。たとえば、上記のサンプル データから: SUM(1, 3) = 3 + ... + (-87)1 番目と 3 番目の属性が 3 と -87 の T であるため

3, (T), F, (T), F, T, T, ...
29, (F), F, (T), F, T, T, ...
...
-87, (T), F, (T), F, T, T, ...
98, (F), F, (T), F, F, T, ...

AndSUM()は任意の数のパラメータを取ることができます: SUM(1)andSUM(5, 7, ..., 3455)はすべて可能です。

L最大の結果がSUM(L)得られる属性のリストを見つけるためのスマートなアルゴリズムはありますか? 明らかに、この大規模なデータ セットに対してブルート フォースは実行できません。

最大数だけでなく、上位 N 個のリストを見つける方法があれば素晴らしいと思います。

EDIT ブルートフォースなしでは答えを見つけることはできないようです。「良い見積もり」を見つけるために質問を変更した場合、それを行う良い方法はありますか? または、L のカーディナリティが 10 などに固定されていると言ったら、L を計算する方法はありますか? どれでも嬉しいです。

4

4 に答える 4

11

残念ながら、この問題はNP 完全です。あなたのオプションは、近似アルゴリズムを使用して適切ではあるが最大ではないソリューションを見つけるか、分岐限定を使用して指数関数的なランタイムに達しないことを期待することに制限されています。

NP完全性の証明

問題が NP 完全であることを証明するために、セット カバー問題を問題に還元します。要素のセットとUのサブセットのセットがあり、 のすべてのセットの結合が であるとします。セット カバー問題は、 のすべての要素が の要素に含まれるような の最小の部分集合を求めます。問題を解決するための多項式時間アルゴリズムがあれば、次のようにセット カバーの問題を解決できます。NSMUSUTSUT

まず、M+N行とM属性を含むテーブルを作成します。最初のN行は「要素」行で、それぞれが の要素に対応しUます。これらには「十分に否定的な」値があります。-M-1十分なはずです。要素 rowの場合、対応する要素がのth セットにないi場合、jth 属性は true です。jS

最後のM行は「セット」行で、それぞれが のセットに対応しSます。これらには価値があります1。set rowN+iの場合、ith 属性はfalseで、その他はすべて true です。

要素行の値は十分に小さいため、すべての要素行を除外する属性の選択は、要素行を含む属性の選択よりも優れています。のすべてのセットの結合は であるため、SすべてUの属性を選択するとすべての要素行が除外されるため、要素行を含まずに最も多くのセット行を含む属性を選択するのが最適です。テーブルの構成により、対応するセットの結合が である場合、属性の選択はすべての要素行を除外し、Uそうである場合、含まれる属性が少ないほどスコアが高くなります。したがって、属性の最適な選択は、 の最小カバー率に直接対応しますS。

最大合計を生成する属性の選択を選択する優れたアルゴリズムがあれば、それをこのテーブルに適用して、任意の最小カバーを生成できますS。したがって、問題は NP 完全集合カバー問題と同じくらい難しく、属性の完全な選択を生成するための効率的なアルゴリズムを考え出すために時間を無駄にすべきではありません。

于 2013-07-07T10:55:23.017 に答える
1

特定の (多数の) ランダムな属性の組み合わせから始めて、最悪の x% を死に至らしめ、属性を追加/削除することで残りの人口の特定の割合を変異させる、遺伝的アルゴリズムのアプローチを試すことができます。

最適な答えが見つかる保証はありませんが、妥当な時間内に適切な答えを見つけるチャンスです。

于 2013-07-07T09:44:17.613 に答える
0

この問題を解決するための多項式アルゴリズムは思い浮かびません。貪欲なヒューリスティックを提案することしかできません。

  1. 各属性について、その を計算しますexpected_score。つまり、単独で選択した場合に SUM にもたらされる加数を計算します。あなたの例では、1 のスコアは 3 - 87 = -84 です。

  2. expected_score増加しない順に属性を並べ替えます。

  3. その順序で、貪欲にL属性を追加します。actual_score属性が実際に合計にもたらすスコアを呼び出します ( に既にある属性に応じて、aよりも良い場合も悪い場合もあります)。が厳密に正でない場合は、 を破棄します。expected_scoreLactual_score(a)a

これは最適な を提供しませんがL、「かなり良い」ものだと思います。

于 2013-07-07T09:34:09.133 に答える
0

注: このアプローチが最良の結果をもたらさない理由については、以下を参照してください。

私の最初のアプローチは、特別なケース L={} (すべての整数の合計を与える必要があります) から始めて、それを解のリストに追加することです。そこから、可能な属性を制限として追加します。最初の反復では、各属性を順番に試して、より良い結果が得られたものを覚えておいてください。その繰り返しの後、覚えているものを解決策のリストに入れます。

2 回目の反復では、記憶された各属性に別の属性を追加してみてください。結果を改善したすべてのものを覚えておいてください。記憶された属性の組み合わせから重複を削除し、これらをソリューションのリストに追加します。{m,n} は {n,m} と同じなので、セットを爆破しないように冗長な組み合わせをスキップしてください。

最終的な合計を改善するために追加できる可能性のある属性がなくなるまで、2 回目の反復を繰り返します。次に、解のリストを合計で並べ替えると、要求された解が得られます。

5k から 3 つの属性を選択する方法は最大 20G あることに注意してください。これらを含むデータ構造を構築することはできませんが、必要に応じてそれらを生成する必要があります。それでも、大量の一時的なソリューションが生成される可能性があるため、それらを効率的に、場合によってはディスクに保存する必要があります。前の反復ではなく、次の反復には前の反復のソリューションのみが必要であるという事実を利用できます。

ここでのもう 1 つの制限は、L={} より下のすべての解が考慮されないため、最終的に N 個未満の最適解になる可能性があることです。その場合、N 個の解が得られるまで、考えられるすべての解を受け入れます。N 個の解が得られたら、最悪の解よりも改善されない解を破棄します。

Python コード:

solutions = [{}]
remembered = [{}]
while remembered:
    tmp = remembered
    remembered = []
    for s in remembered:
        for xs in extensions(s):
            if score(xs) > score(s)
                remembered.append(xs)
    solutions.extend(remembered)

これが機能しない理由:

3 つのレコードからなる一時的な解決策を検討してください

-2, T, F
-2, F, T
+3, F, F

これらの合計は -1 です。ここで最初の属性を選択すると、2 番目と 3 番目のレコードが破棄され、合計が -2 になります。2 番目の属性を選択するとき、1 番目と 3 番目の属性を破棄し、同じ合計 -2 を与えます。1 番目と 2 番目の属性の両方を選択すると、3 つのレコードすべてが破棄され、合計がゼロになり、改善されます。

于 2013-07-07T09:48:48.853 に答える