3

n並べ替えられていない整数の大きなセット(たとえば、 ) があり、それぞれの要素 (は小さい、たとえば) の2^20サブセットを合計の昇順で生成したい場合、最も効率的な方法は何ですか?kk5

この方法でこれらのサブセットを生成する必要があるのは、特定の条件を満たす最小の合計を持つ k 要素サブセットを見つけたいためです。したがって、生成された k 要素サブセットのそれぞれに条件を適用します。

また、アルゴリズムの複雑さはどうなりますか?

同様の質問がここにあります:リスト全体 (すなわちジェネレーター) を構築およびソートせずに、製品の順序でリストの可能なすべてのサブセットを取得するアルゴリズムですが、製品の順序でサブセットを生成することについて、私の目的には適合しません。セットのサイズが非常に大きいため、n

このアルゴリズムは Mathematica で実装するつもりですが、C++ や Python でも実装できます。

4

5 に答える 5

1

20の整数、または2 ^ 20を意味しますか？それが本当に2^20である場合、条件を満たすサブセットを見つける前に、かなりの量（2 ^ 20は5つを選択）のサブセットを調べる必要があるかもしれません。最新の100kMIPSCPUでは、1つの命令だけでセットを計算してその条件を評価できると仮定すると、そのセット全体を通過するのに3兆年かかります。ですから、そのほんの一部を経験する必要があるとしても、それはあなたの生涯で終わることはありません。

整数の数が少なくても、これはこの問題を解決するためのかなり力ずくの方法のようです。混合整数計画法では、条件を制約として表現できる可能性があると思います。その場合、以下を解くことは、ブルートフォース列挙よりもはるかに高速に解を得ることができます。整数がw_i、i 1からNであると仮定すると、次のようになります。

min sum(i) w_i*x_i
    x_i binary
    sum over x_i = k
subject to (some constraints on w_i*x_i)

MIPの線形計画緩和がタイトであることが判明した場合は、運が良ければ、2 ^ 20の整数であっても、問題を解決するための非常に効率的な方法があります（例：最大フロー/最小カット問題）。 ）また、同時に解くことができない値が非常に多い場合があるため、列生成のアプローチを使用して解を見つけることができます。

関心のある制約についてもう少し投稿すると、私または他の誰かが、ブルートフォースの列挙を伴わない、より具体的な解決策を提案できる可能性があります。

于 2013-02-28T03:07:35.020 に答える
1

小さなサブセット ( と呼びますP) の目的のプロパティがかなり一般的である場合、確率論的アプローチがうまく機能する可能性があります。

  1. 整数をソートしn(数百万の整数、つまり 10 から 100 MB の RAM の場合、これは問題になりません)、k-1最小のものを合計します。これを合計と呼びoffsetます。
  2. ランダムな - サブセットを生成し(たとえば、乱数 modkをサンプリングして)、 - 性をチェックします。knP
  3. 試合では、サブセットの合計に注意してください。これから減算して、同等の合計のサブセットのoffset最大要素の上限を見つけます。k
  4. n整数のセットを、この境界以下のものに制限してください。
  5. 一定回数の反復内で一致が見つからなくなるまで (goto 2) を繰り返します。

最初の並べ替えはO(n log n)です。手順 4 で暗に示される二分探索はO(log n)です。

明らかに、Pランダムなポット ショットが一致する可能性が低いほどまれな場合、これは役に立ちません。

于 2013-02-28T03:40:19.923 に答える
1

k サイズのセットの 1000 分の 1 だけが条件を満たしている場合でも、テストするには組み合わせが多すぎます。ランタイムは nCk (n choose k) でスケーリングすると思います。ここで、n はソートされていないリストのサイズです。Andrew Mao による回答には、この値へのリンクがあります。10^28/1000 は 10^25 のままです。毎秒 1000 回のテストでも、それでも 10^22 秒です。=10^14 年。

許可されている場合は、大きなセットから重複した数字を削除する必要があると思います. 重複を削除するたびに、実行する必要がある評価の数が大幅に削減されます。リストを並べ替えてから、だまされた人を殺します。

また、ここで唯一の最良の回答をお探しですか? 答えを検証するのは誰で、どれくらいの時間がかかりますか? 遺伝的アルゴリズムを実装し、一晩中 (時間がある限り) 多数のインスタンスを実行することをお勧めします。これにより、宇宙の持続時間よりもはるかに短い時間で、非常に優れた答えが得られます。

于 2013-02-28T03:37:05.667 に答える
0

これがあなたが言っていることを行うためのおおよその方法です。

まず、リストを並べ替えます。v次に、ソートされたリスト内の位置に対応する長さ 5 のインデックス ベクトル を考えます。ここで、最大インデックスは numbermであり、その他のインデックス ベクトルv'には最大インデックスがありますm' > m。そのようなすべてのv'ベクトルの最小合計は、すべてのベクトルの最小合計より常に大きくなりvます。

したがって、合計がほぼ増加する要素をループする方法は次のとおりです。

sort arr

for i = 1 to N
   for v = 5-element subsets of (1, ..., i)
     set = arr{v}
     if condition(set) is satisfied
       break_loop = true
       compute sum(set), keep set if it is the best so far
   break if break_loop

(1, ..., n+1)基本的に、これは、満足のいく代入が で見つかった場合に の 5 要素の組み合わせをチェックする必要がなくなったことを意味します。これは、(1, ..., n)最大インデックスn+1を持つ満足のいく代入はより大きな合計を持ち、そのセットの後で停止できるためです。ただし、合計が常に増加することを保証する while の 5 つの組み合わせをループする簡単な方法はありません(1, ..., n)が、少なくとも some で満足のいくセットを見つけたら、チェックを停止できますn。

于 2013-02-28T03:43:35.177 に答える
0

これは map-reduce ( http://en.wikipedia.org/wiki/MapReduce )の完璧な候補のようです。合格候補が各ノードに均等に存在するようにスマートに分割する方法を知っていれば、おそらく優れたスループットを得ることができます。

完全な並べ替えは、マップ ステージで処理できるため、実際には必要ない場合があります。その後、各ノードは k-タプルに対して条件を検証し、結果をファイルに出力して、後で集計/縮小することができます。

発生確率が分かっていて、すべての結果が必要ない場合は、確率アルゴリズムを調べて答えに収束してみてください。

于 2013-02-28T03:58:59.877 に答える