9

次の合計を行うための効率的な手法はありますか?

n 個の整数A={X1,X2,…,Xn}を含む有限集合Aが与えられた場合、Xiは整数です。ここで、 A1、A2、... 、 An で示されるA のn 個のサブセットがあります。各サブセットの合計を計算します。効率的なテクニックはありますか？

(通常、 nはAのすべてのサブセットの平均サイズよりも大きいことに注意してください。)

たとえば、A={1,2,3,4,5,6,7,9}、A1={1,3,4,5}、A2={2,3,4}、A3= .. . . A1とA2の合計を計算する単純な方法では、加算に5 フロップが必要です。

合計(A1)=1+3+4+5=13

合計(A2)=2+3+4=9

...

ここで、最初に 3+4 を計算し、その結果 7 を記録する場合、加算に必要なフロップは 3 つだけです。

合計(A1)=1+7+5=13

合計(A2)=2+7=9

...

一般化されたケースはどうですか？計算を高速化する効率的な方法はありますか? ありがとう！

4

5 に答える 5

2

サブセットのいくつかの選択については、いくつかの（潜在的に高価な）事前計算を行うことを気にしないのであれば、計算を高速化する方法がありますが、すべてではありません。たとえば、サブセットが{1,2}、{2,3}、{3,4}、{4,5}、...、{n-1、n}、{n、1}であるとします。その場合、単純なアプローチではサブセットごとに1つの算術演算が使用され、明らかにそれ以上のことはできません。一方、サブセットが{1}、{1,2}、{1,2,3}、{1,2,3,4}、...、{1,2、...、 n}の場合、n-1の算術演算でうまくいくことができますが、単純なアプローチははるかに悪いです。

事前計算を行う1つの方法があります。常に最適な結果が得られるとは限りません。サブセットの各ペアについて、遷移コストを最小（対称差のサイズ、Y-1のサイズ）と定義します。（XとYの対称差は、XまたはYにあるもののセットですが、両方にはありません。）したがって、遷移コストは、Yの要素の合計を計算するために必要な算術演算の数です。 Xの。空のセットをサブセットのリストに追加し、Edmondsのアルゴリズム（http://en.wikipedia.org/wiki/Edmonds%27_algorithm）またはより高速でより複雑なバリエーションの1つを使用して、最小コストの有向スパニングツリーを計算します。そのテーマ。ここで、スパニングツリーのエッジがX-> Yの場合、Yの前にXを計算するようにしてください（これは「トポロジカルソート」であり、効率的に実行できます。

これにより、たとえば{1,2}、{3,4}、{1,2,3,4}、{5,6}、{7,8}、{5,6の場合、明らかに次善の結果が得られます。 、7,8}。上記の手順を使用して操作の順序を決定した後、最適化パスを実行して、すでに計算された合計を前提として各セットの合計を評価する安価な方法を見つけることができます。これにより、実際にはかなり適切な結果が得られる可能性があります。

サブセットの特定のセットに対して最適な手順を見つけることは、NP困難またはそれよりも悪いことだと思いますが、証明しようとはしていません。（確かに計算可能です。実行できる計算のセットは有限です。しかし、一見すると、非常にコストがかかる可能性があります。潜在的に、約2 ^ nの部分和を追跡し、いずれか1つを追加する可能性があります。 （2 ^ 2n）^（n ^ 2）= 2 ^（2n ^ 3）の操作であらゆる可能性を試すという非常に単純なコストで、各ステップでそれらを他のステップに追加し、最大で約n^2ステップにします。 ）。

于 2012-04-30T12:42:00.057 に答える
2

「加算」が単なるADD演算ではなく、2 つの整数オペランドを含む非常に集中的な関数であると仮定すると、明らかなアプローチは結果をキャッシュすることです。

これは、適切なデータ構造を介して実現できます。たとえば、2 つのオペランドによって形成されたキーと値としての回答を含むキー値ディクショナリです。

しかしC、質問で指定したように、最も簡単なアプローチは整数の配列によるもので、 の解nがに格納されます。nx + yarray[x][y]

その後、サブセットを繰り返し反復し、オペランドの各ペアについて、配列内の適切な位置を確認できます。値が存在しない場合は、計算して配列に配置する必要があります。次に、値がサブセット内の 2 つのオペランドを置き換え、反復します。

演算が可換の場合、配列を検索する前にオペランドをソートする必要があります (つまり、最初のインデックスが常に 2 つのオペランドの最小になるように)。これにより、「キャッシュ」ヒットが最大化されます。

于 2012-04-30T12:35:53.877 に答える
1

一般的な最適化手法は、中間結果を事前に計算することです。あなたの場合、2 つの被加数を使用してすべての合計を事前に計算しA、それらをルックアップ テーブルに格納することができます。これにより、|A|*|A+1|/2テーブル エントリが作成されます。ここで、|A|は のカーディナリティですA。

Ai の要素の合計を計算するには、次のようにします。

  • Ai の最初の 2 つの要素の合計を調べて、tmp に保存します。
  • Ai に要素 x が残っている間:
  • tmp と x の合計を調べる

例からの要素の合計を計算するにA1 = {1,3,4,5}は、次のようにします。

  • ルックアップ (1,3) = 4
  • ルックアップ (4,4) = 8
  • ルックアップ (8,5) = 13

ルックアップ テーブルの事前計算中にすべての作業が既に実行されているため、特定の Ai の合計を計算するのに合計は必要ないことに注意してください。

ルックアップ テーブルをハッシュ テーブルに格納するlookup()と、O(1) になります。


このアプローチの可能な最適化:

  • 合計結果を計算しながらルックアップ テーブルを作成します。したがって、実際に必要な合計のみを計算します。ルックアップ テーブルがキャッシュになりました。
  • 加算演算が可換である場合、小さい方の被加数が最初に来る合計のみを格納することで、キャッシュ サイズの半分を節約できます。次に、 = iflookup()のように変更します。lookup(a,b)lookup(b,a)a > b
于 2012-04-30T12:36:19.090 に答える
0

合計が時間のかかるアクションであると仮定すると、サブセットのすべてのペアのLCSを見つけることができます(コメントで述べたようにソートされていると仮定するか、ソートされていない場合はソートします)。その後、最大長の LCS の合計を計算します (すべての LCS にわたって)次に、関連する配列の値を関連する番号に置き換え、それらの LCS を更新し、複数の番号を持つ LCS がなくなるまでこの方法を続けます。確かにこれは最適ではありませんが、単純なアルゴリズム (合計数が少ない) よりは優れています。ただし、バックトラックを実行して最適なソリューションを見つけることができます。

たとえば、サンプル入力の場合:

A1={1,3,4,5} , A2={2,3,4}

LCS (A_1,A_2) = {3,4} ==>7 ==>replace it:

A1={1,5,7}, A2={2,7} ==> LCS = {7}, maximum LCS length is `1`, so calculate sums.

それでも、2 つの乱数の合計を計算してから、もう一度 LCS を取ることで改善できます。

于 2012-04-30T12:30:41.773 に答える
0

番号。効率的なテクニックはありません。

NP完全問題なので。そして、そのような問題に対する効率的な解決策はありません

なぜNP完全なのですか？
この問題のアルゴリズムを使用して、セット カバー問題を解決できます。セットに余分なセットを入れて、すべての要素を連結するだけです。

例: 要素の集合
A1={1,2}、A2={2,3}、A3 = {3,4} 集合被覆問題を解きたいとします。

このセットに、すべての要素を含む数値のセット A4 = {1,2,3,4} を追加します

ジョン・スミスが求めているアルゴリズムを使用し、ソリューション A4 が表現されていることを確認します。NP完全問題を解きました。

于 2012-04-30T13:32:44.817 に答える