9

文献があるかどうかわからないコスト最適化のリクエストがあります。説明するのが少し難しいので、質問が長くなってしまうことをあらかじめお詫びします。

このように機能する私がアクセスしているサーバーがあります：

  • リクエストはレコード (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 日に数万件)。

グラフィカルに、これを nxp スパース行列と考えることができます。そのために、非ゼロの値を四角形の部分行列でカバーしたいと考えています。

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

持つ：

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

私の問題のスパース係数を g と名付けます (可能なペアの総数に対する必要なペアの数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
r1xx
r2×
r3xx

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

   f1 f3 f2
r1xx
r3xx
r2×

そして、求める最適解がある(f1,f3) x (r1,r3) + (f2) x (r2)

  • 組み合わせ論が爆発するため、すべてのソリューションを試して低コストを探すことは選択肢ではありません。
行の順列ごとに: (n!)
   列の順列ごとに: (p!)
       nxp 行列の可能なカバーごとに: (時間は不明ですが、大きい...)
           カバーのコストを計算する

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

いくつかの数字を覚えておくと、私の n は 1 から 1000 の間のどこかで、私の p は 1 から 200 の間のどこかです。レコードは、要求されたフィールドが類似しているクラスにあるため、実際には「ブロック状」です。残念ながら、レコードのクラスにアクセスできません...

質問 1 : アイデア、巧妙な単純化、または有用な論文の参考文献を誰かが持っていますか? 多くのリクエストがあるので、平均してうまく機能するアルゴリズムを探しています (ただし、n と p が大きい場合に行列全体をリクエストするなど、極端なケースではうまく動作しない余裕はありません)。 、そしてリクエストは実際には非常にまばらです）。

質問 2 : 実際、問題はさらに複雑です: コストは実際には次のような形式です: a + n * (p^b) + c * n' * p'、ここで、b は定数 < 1 です (レコードがフィールドを要求されると、他のフィールドを要求するのはそれほどコストがかかりません。フィールド) でn' * p' = n * p * (1 - g)あり、要求したくないセルの数です (それらは無効であり、無効なものを要求するには追加コストがかかるため)。この問題を迅速に解決できるとは夢にも思いませんが、それでも...誰かアイデアはありますか?

4

6 に答える 6

5

要求された値をカバーする部分行列を選択することは、集合カバー問題の形式であり、したがって NP 完全です。あなたの問題は、セットのコストが異なるというこのすでに困難な問題に追加されます。

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

ウィキペディアの記事では、問題を多項式時間で解くことはできないという非近似性の結果が得られます。係数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。結果として、楽観的なケースでは最大で約 1 倍、悲観的なケースn = 1000ではp = 200約 1 倍の最悪のケースでしか解決策を見つけることが期待できません(さまざまなコストは無視します)。17100.000

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

于 2009-09-10T15:57:34.913 に答える
1

わかりました、質問の私の理解は変わりました。新しいアイデア：

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

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

于 2009-09-10T10:55:10.643 に答える
1

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

  1. トスいくつかの長方形のアプローチ:

    • に基づいて「ほぼ最適な」長方形サイズを決定します。
    • すべてのポイントがカバーされるまで、必要なポイントにこれらの長方形を (おそらくランダムに) 配置します。
    • 次に、各長方形を取得し、データ ポイントを「失う」ことなく可能な限り縮小します。
    • 互いに近い四角形を見つけて、それらを別々にしておくよりも組み合わせたほうがコストがかからないかどうかを判断します。

  2. 育つ

    • 独自の 1x1 の長方形内の各ポイントから始めます。
    • n 行/列 (n は a に基づいている場合があります) 内のすべての四角形を見つけます。それらを無料で (または負のコスト:D) 1 つの長方形に結合できるかどうかを確認してください。
    • 繰り返す。

  3. 縮む

    • すべてのポイントをカバーする 1 つの大きな長方形から始めます。
    • 大きな長方形と一対の辺を共有しているが、ポイントがほとんど含まれていないサブ長方形を探します。
    • 大きなものから切り取って、2 つの小さな長方形を作ります。
    • 繰り返す。

  4. クワッド

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

また、場合によっては、それらのスーパーセットである 1 つの大きな四角形よりも、 2つの重なり合う四角形を使用する方がよい場合があることに注意してください。たとえば、2 つの長方形が 1 つの角で重なっている場合などです。

于 2009-09-10T08:36:54.717 に答える
0

ユーザー要求で言及されている n 個のレコード (行) と p 個のフィールド (列) は、p 次元空間 ({0,1}^p) の n 個の点として設定され、i 番目の座標が X の場合は 1 であると見なします、およびすべての X を含むルートで最も粗いクラスターを持つクラスターの階層を識別します。クラスタリング階層の各ノードについて、必要なすべての列をカバーする積を検討します (これは行 (任意のサブノード) x cols(任意のサブノード) )))。次に、子カバーをマージするか (カバー全体に対して支払う)、個別の要求として保持するかをボトムアップで決定します。(カバーは連続した列ではなく、正確に必要なものです。つまり、ビットベクトルを考えてください)

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

于 2009-09-10T08:37:57.860 に答える
0

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

于 2009-09-10T08:42:04.020 に答える
0

私はそれに少し取り組んできました.Pythonのような疑似コードで明らかなO(n^3)貪欲な対称性破りアルゴリズム(レコードとフィールドは別々に扱われます)です。

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

#与えられた
# 関数コスト要求 -> 正の実数
# セットの 2 つのペア (f1, r1) と (f2, r2) を取るマージ関数
# そして ((f1 U f2), (r1 U r2)) を返します

# レコードごとのリクエストで初期化

requests = [({record},{field if (record, field) is needed}) for all needed records]
cost = [リクエスト内のリクエストのコスト(リクエスト)]

終了 = 偽

while not finished: # 何か得るものがあるかもしれません
    maximum_gain = 0
    終了 = 真
    this_step_merge = 空

    # リクエストのすべてのペアにループ
    request1 != request2 のように (requests x request) 内のすべての (request1, request2) に対して:
        merged_request = マージ (リクエスト 1、リクエスト 2)
        ゲイン = コスト (リクエスト 1) + コスト (リクエスト 2) - コスト (merged_request)

        ゲイン > maximum_gain の場合:
            maximum_gain = ゲイン
            this_step_merge = (request1, request2, merged_request)

    # マージするものが少なくとも見つかった場合は、続行する必要があります
    maximum_gain > 0 の場合:
        # リクエストのリストを更新します...
        request1、request2、merged_request = this_step_merge
        リクエストから request1 を削除
        リクエストから request2 を削除
        # ...そしてまだ終わっていません
        merged_request をリクエストに挿入する
        終了 = 偽

出力要求

これは O(n3 * p) です。理由は次のとおりです。

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

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

    1. 誰かがアルゴリズムの非常に悪いケースを指摘するのを手伝ってくれますか? これを使用するのは理にかなっていますか？
    2. これは O(n^3) であり、大きな入力にはコストがかかりすぎます。それを最適化するアイデアはありますか？

前もって感謝します ！

于 2009-09-20T10:23:51.413 に答える