アフィンコストによるデカルトリクエストの最適化

StackOverflow https://stackoverflow.com/questions/1403933

質問

文献があればどうなるかわからないコスト最適化のリクエストがあります。説明するのは少し難しいので、質問の長さについて事前に謝罪します。

この方法で動作する、私がアクセスしているサーバーがあります：

  • レコード（r1、... rn）およびフィールド（f1、... fp）で要求が行われます
  • デカルト積（r1、...、rp）x（f1、... fp）のみ要求できます
  • そのようなリクエストに関連付けられたコスト（時間とお金）は、リクエストのサイズに関係します：

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

一般性を失うことなく（正規化するだけで）、b=1であるため、コストは次のようになります。

T((r1, ...,rn)x(f1,...fp)) = a + n * p

  • ユーザーからのリクエストであるペア(r1, f(r1)), ... (rk, f(rk))のサブセットのみをリクエストする必要があります。私のプログラムは、ユーザーとサーバー（外部）の間の仲介者として機能します。このようなリクエストがたくさんあります（1日に数万件）。

グラフィカルに、n x pのスパースマトリックスと考えることができます。このため、ゼロ以外の値を長方形のサブマトリックスでカバーします。

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

所有：

  • 一定のコストのために合理的に保たれている部分行列の数
  • すべての「x」は部分行列内になければなりません
  • 線形コストのために、カバーされる総面積が大きすぎてはなりません

私の問題のスパース係数に名前を付けます（可能なペアの合計に対する必要なペアの数、g = k / (n * p)。係数aを知っています。

いくつかの明らかな観察があります：

  • aが小さい場合、最善の解決策は各（レコード、フィールド）ペアを個別に要求することであり、合計コストは次のとおりです。k * (a + 1) = g * n * p * (a + 1)
  • aが大きい場合、最良の解決策はデカルト積全体を要求することであり、合計コストは次のとおりです。a + n * p
  • 2番目の解決策は、g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
    • となるとすぐに改善されます
  • もちろん、デカルト積の順序は重要ではないため、マトリックスの行と列を転置して、より簡単にカバーできるようにします。例：
   f1 f2 f3
r1  x    x
r2     x 
r3  x    x

次のように並べ替えることができます

   f1 f3 f2
r1  x  x
r3  x  x
r2       x

そして、(f1,f3) x (r1,r3) + (f2) x (r2)

をリクエストするのが最適な解決策です
  • すべてのソリューションを試して低コストを探すことは選択肢ではありません。組み合わせ論が爆発するからです
for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

だから、おおよその解決策を探しています。マトリックスを与えられたカバーを見つけるある種の貪欲なアルゴリズムをすでに持っています（ユニタリセルで始まり、マージ内の空のセルの割合がしきい値を下回る場合にそれらをマージします）。

いくつかの数値を念頭に置くと、nは1から1000の間、pは1から200の間です。カバレッジパターンは、「ブロック」です。 。残念ながら、レコードのクラスにアクセスできません...

質問1 ：誰かがアイデア、賢明な単純化、または役に立つ可能性のある論文への参照を持っていますか？私はたくさんのリクエストがあるので、平均して うまくいくアルゴリズムが探しています（しかし、例えば、全体をリクエストするなど、極端な場合に非常に貧弱に働く余裕はありませんnとpが大きく、要求が実際に非常にスパースである場合の行列）。

質問2 ：実際には、問題はさらに複雑です。実際には、コストは次の形式に似ています。a + n * (p^b) + c * n' * p'、ここでbは定数<！> lt; 1（レコードがフィールドを要求されると、他のフィールドを要求するのにそれほど費用はかかりません）およびn' * p' = n * p * (1 - g)は、要求したくないセルの数です（無効であり、追加コストがあるため）無効なものをリクエストする場合）。私はこの問題の迅速な解決策を夢見ることさえできませんが、それでも...アイデアは誰ですか？

役に立ちましたか？

解決

要求された値をカバーするサブマトリックスの選択は、カバー問題の設定の形式です。したがって、NPは完了します。あなたの問題は、セットのコストが異なるというこのすでに難しい問題に追加されます。

行と列の並べ替えを許可することはそれほど大きな問題ではありません。切断された部分行列だけを考慮することができるからです。行1、列4〜7、行5、列4 2、7は有効なセットです。行2と行5を交換して、接続されたサブマトリックス行1、列4〜行2、列7を取得できるからです。もちろん、これはいくつかの制約を追加します-すべての順列ですべてのセットが有効であるとは限りませんが、これが最大の問題だとは思いません。

Wikipediaの記事では、因子0.5 * log2(n)を使用した場合よりも多項式時間で問題を解決できないという近似不可能な結果が得られます。ここでnはセットの数です。あなたの場合、2^(n * p)は、（非常に悲観的な）セット数と利回りの上限であり、多項式時間で0.5 * n * pの因子までの解しか見つけることができません（N = NPを除き、変動コストを無視します） 。

行と列の順列を無視するセットの数の楽観的な下限は、0.5 * n^2 * p^2であり、log2(n) + log2(p) - 0.5のはるかに優れた係数を生成します。結果として、あなたは最悪の場合にのみn = 1000およびp = 200の楽観的な場合で約17の要因まで、そして悲観的な場合で約100.000の要因まで解決策を見つけることを期待できます（さまざまなコストをまだ無視しています）。

したがって、できる最善の方法は、ヒューリスティックアルゴリズムを使用することです（Wikipediaの記事には、ほぼ最適な貪欲アルゴリズムが記載されています）。アルゴリズムのパフォーマンスが（非常に）悪い場合があることを受け入れます。または、他の方法で最適化アルゴリズムを使用し、より多くの時間を使用する適切なソリューションを見つけようとします。この場合、 A *検索を使用することをお勧めします。

他のヒント

このための本当に良いアルゴリズムはどこかにあると確信していますが、ここに私自身の直感的なアイデアがあります：

  1. Toss-some-rectanglesアプローチ：

    • <！> quot;ほぼ最適な<！> quotを決定します。 a に基づく長方形サイズ。
    • すべてのポイントがカバーされるまで、これらの長方形を（おそらくランダムに）必要なポイントの上に置きます。
    • ここで、各長方形を<！> quot; losing <！> quot;なしで可能な限り縮小します。任意のデータポイント。
    • 互いに近い長方形を見つけ、それらを結合するほうが、別々に保つよりも安価になるかどうかを決定します。

  2. 成長

    • 1x1の長方形内の各ポイントから始めます。
    • n行/列（nは a に基づく場合があります）内のすべての長方形を探します。コストをかけずに（または負のコスト：D）1つの長方形に結合できるかどうかを確認します。
    • 繰り返します。

  3. 縮小

    • すべてのポイントをカバーする1つの大きな長方形から始めます。
    • 大きな辺と一対の辺を共有するが、非常に少ない点を含むサブ長方形を探します。
    • 大きな長方形から切り取り、2つの小さな長方形を作成します。
    • 繰り返します。

  4. クワッド

    • 平面を4つの長方形に分割します。これらのそれぞれについて、さらに再帰するか、長方形全体を含めることで、より良いコストが得られるかどうかを確認してください。
    • 今、長方形を取り、それらのいずれかをほとんど/無料でマージできるかどうかを確認します。\

また：心に留めておく場合によっては、それらのスーパーセットである1つの大きな長方形よりも、2つの重複する長方形の方が良いこともあります。例えば。 2つの長方形が1つの角で重なっている場合。

OK、質問に対する私の理解が変わりました。新しいアイデア：

  • 各行を長いビット文字列として保存します。ビットストリングのペアをANDし、1ビットの数を最大にするペアを見つけようとします。これらのペアをより大きなグループに成長させます（並べ替えて、本当に大きなペアを互いに一致させます）。次に、最大のグループにヒットするリクエストを作成し、それらのすべてのビットを忘れます。すべてが完了するまで繰り返します。行から列に切り替えることもあります。

  • ゼロまたは少数のポイントが含まれるすべての行/列を探します。 <！> quot; Delete <！> quot;一時的に。今、あなたはそれらを除外するリクエストでカバーされるものを見ています。ここで、おそらく他の手法のいずれかを適用し、無視された行/列を後で処理します。これについてのもう1つの考え方は、最初に密度の高いポイントを処理し、次に密度の低いポイントに移動することです。

値がまばらなので、多くのユーザーが同様の値を求めている可能性がありますか？アプリケーション内のキャッシュはオプションですか？リクエストは、（x、y）位置の関数であるハッシュによってインデックス付けできるため、グリッドの正しい領域内にあるキャッシュされたセットを簡単に識別できます。たとえば、キャッシュされたセットをツリーに保存すると、要求範囲をカバーする最小限のキャッシュされたサブセットをすばやく見つけることができます。その後、サブセットに対して線形ルックアップを実行できます。これは小さいです。

ユーザーリクエストセットで言及されているnレコード（行）とpフィールド（cols）を、p次元空間（{0,1} ^ p）のn点と見なします。 Xがあり、クラスターの階層を識別します。ルートの最も粗いクラスターにはすべてが含まれますX。クラスタリング階層内の各ノードについて、必要なすべての列（これはrows（any subnode）x cols（any subnode））をカバーする製品を検討します。次に、子カバーをマージする（カバー全体を支払う）か、個別の要求として保持するかをボトムアップで決定します。 （カバーは連続した列ではありませんが、必要なものだけです;つまり、ビットベクトルを考えてください）

重複する製品リクエストの方が安くなる可能性があることにArteliusに同意します。私の階層的なアプローチはそれを組み込むために改善が必要でしょう。

少し作業しましたが、Pythonのような擬似コードでの、O（n ^ 3）貪欲な、対称性を破る明らかなアルゴリズム（レコードとフィールドは別々に処理されます）があります。

アイデアは簡単です。まず、レコードごとに1つのリクエストを試行し、マージする価値のあるものがなくなるまで、最も価値のあるマージを行います。このアルゴリズムには、リクエストの重複を許可しないという明らかな欠点がありますが、実際のケース（a + n * (p^b) + c * n * p * (1 - g)コスト関数を使用）で非常にうまく機能すると期待しています：

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

これはO（n3 * p）です：

  • 初期化後、nリクエストで開始
  • whileループは、反復ごとにプールから1つの要求を削除します。

  • 内側のforループは、リクエストの（ni^2 - ni）/ 2個の個別のペアで繰り返されます。最悪の場合（すべてを1つの大きなリクエストにマージする場合）、nはnから1になります。

    1. アルゴリズムの非常に悪いケースを指摘してくれる人がいますか。これを使用するのは理にかなっているように聞こえますか？
    2. これはO（n ^ 3）であり、大きな入力にはコストがかかりすぎます。最適化するアイデアはありますか？

事前に感謝します！

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top