5

私は集合I={P1、P2、...、Pm}を持ち、次のようにR1、R2、...、Rnで表されるIのn個の有限部分集合を持っています。

R1 = {P1、P2}

R2 = {P2、P4}

R3 = {P2、P3、P4}

R4 = {P1、P2、P4}

...。

ここで、円周率は整数を示します。

Riごとに、そのすべての要素の積を計算したいと思います。私の目的は、Ri（i = 1,2、...、n）間でいくつかの共通部分を共有することにより、乗算と除算をできるだけ少なくすることです。

たとえば、最初にP2 * P4を計算できる場合、この結果はR3とR4のすべての要素の積を計算する際に使用できます。

除算も許可されていることに注意してください。たとえば、最初にA = P1 * P2 * P3 * P4を計算し、次にA / P1を使用してR3のすべての要素の積を計算し、R4にA/P3を使用できます。

最小の乗算と除算を使用して、Iのすべてのサブセットのすべての積を計算したい場合、それは集合被覆問題ですか？NP完全？ところで、ここのようにそれを記述するために整数線形計画法の定式化を与えることができますか？

どんな提案でも大歓迎です！

コミュニティ編集：追加の仮定：

  • 乗算と同じコストで、除算が許可されます
  • 特定のセットに繰り返される要素はありません。例：R5 = {P1, P1, P1, P2}許可されていません
4

3 に答える 3

1

除算がなければ、これはGary & Johnsonで説明されている問題 ENSEMBLE COMPUTATION と同じように見えるため、NP 完全です。

[PO9] アンサンブル計算

インスタンス: 有限集合 A、正の整数 J のサブセットのコレクション C。

質問: j <= J ユニオン演算のシーケンス S = (z_1 <- x_1 U y_1, z_2 <- x_2 U y_2, ..., z_j <- x_j U y_j) はありますか? x_i と y_i が互いに素であり、1 <= i <= j であり、C のすべてのサブセット c に対して、いくつかの z_i、1 <= i < が存在する= j、これは C と同じです。

セット I は A に対応し、各 R_i は C の要素に対応し、乗算はセット ユニオンに対応します。

于 2012-05-31T00:04:04.583 に答える
1

まず、分割は必要ありません

ここでは除算は必要ありません。常に余分な計算になります。

割る必要があるということは、既に掛け算を行ったことを意味します。

たとえば、Pi*Pj*Pk*Pn を Pn で割って Pi*Pj*Pk を計算する場合、以前に Pi*Pj*Pk*Pn を計算したため、以前に Pi*Pj*Pk を計算したことを意味します。

(あなたの数はすべて素数だと仮定しています)

私の解決策

分割の可能性を考慮していない考えがあります。

Ri を使用してサフィックス ツリーの構築を開始できます。

次に、乗算の数はツリー内のエッジの数になります。

例 ：

あなたの例を使用すると、サフィックスツリーは次のようになります。

       P2
      / \
     P4 P1
    / \ 
   P3 P1

4 つの乗算を取得します。

M1=P1*P2

M2=P2*P4

M3=M2*P1

M4=M2*P3

乗算の最小数を見つけることは、最小数のエッジでサフィックス ツリーを構築することと同じです。

これが役立つことを願っています。

于 2012-05-30T17:26:46.963 に答える
1

エッジのない要素 R iのグラフを考えてみましょう。次のようにエッジを追加できるようになりました。

  • R a →R bの間に有向辺を追加し、商 R b /R aで注釈を付けます。

たとえば、エッジ R 1 →R 3を描くことができます。この場合、R 1 /R 3 = P3*P4/P1を掛けるコストがかかります。

これをすべてのノードに対して行うと、|R| が得られます。2 つのエッジ。

中間結果のみを使用した場合は、最小スパニング ツリー アルゴリズムを使用してこれを解決できます。MST アルゴリズムは、エッジの数が線形に非常に近いと思います (逆アッカーマンの係数で、 よりも遅くなりますlog(log(log(...log(n)...))))。http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/07/Karger95.pdfしたがって、この基本的なアルゴリズムは |R| 2回。

ただし、中間結果のみを使用すると、真に最適な答えを得ることができなくなります。なぜなら、より良いパフォーマンスを実現するために、何もないところから引き出す「即興」表現を使用できるからです。たとえば、次のシナリオを検討できます。

R1 = {P2, P3, P4, P5}
R2 = {P1, P3, P4, P5}
R3 = {P1, P2, P4, P5}
R4 = {P1, P2, P3, P5}
R5 = {P1, P2, P3, P4}

最適な解決策は、 を計算してからP1*P2*P3*P4*P5P iで割り、9 回の操作を行うことです。上記の方法では、R1=P2*P3*P4*P5 のようなことしか実行できず、毎回乗算と除算を実行して、R1→R2、R2→R3、R3→R4、R4→R5、11 回の演算が行われます。(除算がなければ、9 つの演算もある: b=P1*P2 c=b*P3 r5=c*P4 r4=c*P5, d=P4*P5, r3=b*d, e= P3*d, r1=e*P2, r2=e*P1. 分割が必要な状況を作ることは可能だと思いますが、それを見つけることができないようです. 見つけられない場合は、これは実際には単純な多項式時間の問題です。)

この方法を「即席表現」法と呼びます。即席式を計算することを選択した場合 (最初に単一の沈没コスト)、これを使用することを選択した場合、エッジをトラバースするための将来のすべての計算のコストが削減されます(なぜなら、いくつの即席式を使用するかを選択できる可能性があるためです)。使用する）。

これにより、非常にマイナーな補足事項が得られます。

Theorem:
  You should have at least one intermediate expression of each 
  length up to the maximum size of any R.
Proof (induction):
  To build up a product of size N, you will need to do 
  have a product of size N-1.

この定理に注目すると、上記は少し間違っていることがわかります。最適な解決策は、 を覚えてP1*P2*P3計算P1*P2*P3*P4することP1*P2*P3*P4*P5でした。R5次に、無料で取得できます(R4別の手段を使用して乗算を 1 回行うだけで、残念ながら以前と同じコストになります)、合計コストが 9 から 8 に削減されます。これにより、http://en.wikipedia. org/wiki/Floyd%E2%80%93Warshall_algorithmと任意のエッジを使用すると、非常に長い時間の後に最適なソリューションが得られる可能性があります。

とにかく、そのようなシステムをどのようにソリューションに組み込むのでしょうか? MST アルゴリズムが台無しになるため、ノードを追加することはできません。即席式 E による乗算または除算によって一部の P が累乗 p よりも大きくならないエッジごとに (たとえば、p=2 の場合、 のような積を作成する中間の即席式は許可されますP1 * P4^2 / P3が、のようなものは許可されませんP2^3)、その乗算と除算を実行します。 2 つの新しいエッジを作成します。(これを複数回行うか、将来的に行う可能性があります。) また、エッジのすべてのサブセットに対してこれを行い、上記のようにメモ化します。MST アルゴリズムを使用する場合、この方法のコストは、エッジの数が大幅に増加することです。そのため、おそらく (|R| + #newedges) 2 = (|R|^|P|) 2最悪の場合、最適な答えを見つけるのにかかる時間が大幅に長くなる可能性があります。

したがって、推測として、より一般的な問題は NP 困難であるように思われます。そうでない場合は、誰かチャイムを鳴らしてください。ただし、使用する便利な即興表現を推測するためにヒューリスティックを使用することもできます。たとえば、R の「大規模な」サブセットに「高密度の共通 P が含まれている」場合は、すべての共通 P の積であるトリックノードを生成できます。R のサブセットに見られるすべての「一般的な P の大規模/密な塊」に対してこれを行うと、MST を実行すると、より一般的な検索を行わなくても、わずかに良い答えが得られる可能性があります。階層クラスタリング アルゴリズムなどのアルゴリズムを実行して、このような塊を検出することもできます。

(補足: ラティスに関する数学をこの問題に適用することもできます。これは、各セットをビット ベクトルと見なすことができ、これらが一緒になってラティスの基礎を形成するためです。)

于 2012-05-30T17:34:08.373 に答える