16

サブセット和問題を解く次の方法を検討してください。

def subset_summing_to_zero (activities):
  subsets = {0: []}
  for (activity, cost) in activities.iteritems():
      old_subsets = subsets
      subsets = {}
      for (prev_sum, subset) in old_subsets.iteritems():
          subsets[prev_sum] = subset
          new_sum = prev_sum + cost
          new_subset = subset + [activity]
          if 0 == new_sum:
              new_subset.sort()
              return new_subset
          else:
              subsets[new_sum] = new_subset
  return []

私はここからそれを持っています：

http://news.ycombinator.com/item?id=2267392

それを「より効率的に」することが可能であるというコメントもあります。

どのように？

また、少なくとも上記の問題と同じくらい速い問題を解決する他の方法はありますか？

編集

スピードアップにつながるアイデアに興味があります。私が見つけた：

https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2

これは線形時間アルゴリズムに言及しています。しかし、私は紙を持っていません、おそらくあなた、親愛なる人々、それがどのように機能するか知っていますか？おそらく実装？おそらく完全に異なるアプローチ？

編集2

現在、フォローアップがあります：
Pisingerによるサブセット和アルゴリズムの高速ソリューション

4

6 に答える 6

16

私はあなたがこの問題を解決しようとしている敏捷性を尊重します！残念ながら、NP完全問題を解決しようとしています。つまり、多項式の時間障壁を破るさらなる改善により、P=NPであることが証明されます。

Hacker Newsから取得した実装は、疑似ポリタイム動的計画法ソリューションと一致しているようです。追加の改善は、定義上、この問題とそのすべてのアルゴリズムアイソフォームに関する現在の研究の状態を進める必要があります。言い換えれば、一定のスピードアップは可能ですが、このスレッドのコンテキストで問題に対するこのソリューションのアルゴリズムの改善が見られる可能性はほとんどありません。

ただし、許容可能な程度の誤差を伴うポリタイムソリューションが必要な場合は、近似アルゴリズムを使用できます。ウィキペディアから露骨に盗まれた擬似コードでは、これは次のようになります。

initialize a list S to contain one element 0.
 for each i from 1 to N do
   let T be a list consisting of xi + y, for all y in S
   let U be the union of T and S
   sort U
   make S empty 
   let y be the smallest element of U 
   add y to S 
   for each element z of U in increasing order do
      //trim the list by eliminating numbers close to one another
      //and throw out elements greater than s
     if y + cs/N < z ≤ s, set y = z and add z to S 
 if S contains a number between (1 − c)s and s, output yes, otherwise no

Pythonの実装、元の用語を可能な限り忠実に保持します。

from bisect import bisect

def ssum(X,c,s):
    """ Simple impl. of the polytime approximate subset sum algorithm 
    Returns True if the subset exists within our given error; False otherwise 
    """
    S = [0]
    N = len(X)
    for xi in X:
        T = [xi + y for y in S]
        U = set().union(T,S)
        U = sorted(U) # Coercion to list
        S = []
        y = U[0]
        S.append(y)
        for z in U: 
            if y + (c*s)/N < z and z <= s:
                y = z
                S.append(z)
    if not c: # For zero error, check equivalence
        return S[bisect(S,s)-1] == s
    return bisect(S,(1-c)*s) != bisect(S,s)

...ここで、Xは用語のバッグ、cは精度（0から1の間）、sはターゲットの合計です。

詳細については、ウィキペディアの記事を参照してください。

（追加のリファレンス、CSTheory.SEの詳細を読む）

于 2012-03-29T18:28:06.343 に答える
7

私はPythonをあまり知りませんが、途中でミートと呼ばれるアプローチがあります。擬似コード：

Divide activities into two subarrays, A1 and A2
for both A1 and A2, calculate subsets hashes, H1 and H2, the way You do it in Your question.
for each (cost, a1) in H1
     if(H2.contains(-cost))
         return a1 + H2[-cost];

これにより、妥当な時間で処理できるアクティビティの要素の数を2倍にすることができます。

于 2012-03-26T12:04:48.547 に答える
6

私の以前の回答では、この問題に対するポリタイム近似アルゴリズムについて説明しましたが、 xのすべてのx iが正の場合、Pisingerのポリタイム動的計画法ソリューションの実装が特に要求されました。

from bisect import bisect

def balsub(X,c):
    """ Simple impl. of Pisinger's generalization of KP for subset sum problems
    satisfying xi >= 0, for all xi in X. Returns the state array "st", which may
    be used to determine if an optimal solution exists to this subproblem of SSP.
    """
    if not X:
        return False
    X = sorted(X)
    n = len(X)
    b = bisect(X,c)
    r = X[-1]
    w_sum = sum(X[:b])
    stm1 = {}
    st = {}
    for u in range(c-r+1,c+1):
        stm1[u] = 0
    for u in range(c+1,c+r+1):
        stm1[u] = 1
    stm1[w_sum] = b
    for t in range(b,n+1):
        for u in range(c-r+1,c+r+1):
            st[u] = stm1[u]
        for u in range(c-r+1,c+1):
            u_tick = u + X[t-1]
            st[u_tick] = max(st[u_tick],stm1[u])
        for u in reversed(range(c+1,c+X[t-1]+1)):
            for j in reversed(range(stm1[u],st[u])):
                u_tick = u - X[j-1]
                st[u_tick] = max(st[u_tick],j)
    return st

うわー、それは頭痛を誘発しました。これは校正が必要です。これは、を実装している間balsub、SSPのこのサブ問題に対する最適なソリューションが存在するかどうかを判断するための適切なコンパレータを定義できないためです。

于 2012-03-31T03:24:33.880 に答える
3

問題について「議論」したことをお詫びしますが、x値が制限されている「サブセット和」問題は、問題のNPバージョンではありません。動的計画法の解は、制限されたx値の問題で知られています。これは、x値を単位長の合計として表すことによって行われます。動的計画法ソリューションには、xの全長に比例するいくつかの基本的な反復があります。ただし、数値の精度がNに等しい場合、サブセット和はNPになります。つまり、xを表すために必要な数値または基数2の位の値は=Nです。N=40の場合、xは数十億単位である必要があります。NP問題では、xの単位長はNとともに指数関数的に増加します。そのため、動的計画法の解はNPサブセット和問題の多項式時間解ではありません。そういうわけで、

于 2012-04-01T18:44:38.187 に答える
2

コードをより効率的にするための3つの方法は次のとおりです。

  1. コードは、各部分和のアクティビティのリストを格納します。合計を計算するために必要な最新のアクティビティを保存し、解決策が見つかったらバックトラックして残りを計算する方が、メモリと時間の両方の点でより効率的です。

  2. アクティビティごとに、ディクショナリに古いコンテンツが再入力されます（subsets [prev_sum] =サブセット）。単一の辞書を単純に拡張する方が高速です

  3. 値を2つに分割し、中間のアプローチでミートを適用します。

最初の2つの最適化を適用すると、次のコードが5倍以上高速になります。

def subset_summing_to_zero2 (activities):
  subsets = {0:-1}
  for (activity, cost) in activities.iteritems():
      for prev_sum in subsets.keys():
          new_sum = prev_sum + cost
          if 0 == new_sum:
              new_subset = [activity]
              while prev_sum:
                  activity = subsets[prev_sum]
                  new_subset.append(activity)
                  prev_sum -= activities[activity]
              return sorted(new_subset)
          if new_sum in subsets: continue
          subsets[new_sum] = activity
  return []

また、3番目の最適化を適用すると、次のようになります。

def subset_summing_to_zero3 (activities):
  A=activities.items()
  mid=len(A)//2
  def make_subsets(A):
      subsets = {0:-1}
      for (activity, cost) in A:
          for prev_sum in subsets.keys():
              new_sum = prev_sum + cost
              if new_sum and new_sum in subsets: continue
              subsets[new_sum] = activity
      return subsets
  subsets = make_subsets(A[:mid])
  subsets2 = make_subsets(A[mid:])

  def follow_trail(new_subset,subsets,s):
      while s:
         activity = subsets[s]
         new_subset.append(activity)
         s -= activities[activity]

  new_subset=[]
  for s in subsets:
      if -s in subsets2:
          follow_trail(new_subset,subsets,s)
          follow_trail(new_subset,subsets2,-s)
          if len(new_subset):
              break
  return sorted(new_subset)

要素の最大絶対値になるようにバインドを定義します。ミドルアプローチでのミートのアルゴリズム上の利点は、限界に大きく依存します。

下限（たとえば、bound=1000およびn=300）の場合、真ん中の出会いは、最初に改善された方法を除いて、約2倍の改善しか得られません。これは、サブセットと呼ばれる辞書が密集しているためです。

ただし、上限（たとえば、bound=100,000およびn=30）の場合、最初の改善された方法の2.5秒（および元のコードの場合は18秒）と比較して、中間の会議には0.03秒かかります。

上限の場合、中央のミートは、通常の方法の操作数の平方根になります。

途中で会うのが下限の2倍しかないのは意外に思われるかもしれません。その理由は、各反復での操作の数が辞書内のキーの数に依存するためです。k個のアクティビティを追加した後、2 ** k個のキーがあると予想される場合がありますが、バインドが小さい場合、これらのキーの多くが衝突するため、代わりにO（bound.k）キーのみが使用されます。

于 2012-03-29T21:58:48.990 に答える
0

ウィキペディアで説明されている疑似ポリタイムアルゴリズムのScalaソリューションを共有したいと思いました。これはわずかに変更されたバージョンです。一意のサブセットがいくつあるかを把握します。これは、 https： //www.hackerrank.com/challenges/functional-programming-the-sums-of-powersで説明されているHackerRankの問題に非常に関連しています。コーディングスタイルは良くないかもしれません、私はまだScalaを学んでいます:)多分これはまだ誰かのために役立ちます。

object Solution extends App {
    var input = "1000\n2"

    System.setIn(new ByteArrayInputStream(input.getBytes()))        

    println(calculateNumberOfWays(readInt, readInt))

    def calculateNumberOfWays(X: Int, N: Int) = {
            val maxValue = Math.pow(X, 1.0/N).toInt

            val listOfValues = (1 until maxValue + 1).toList

            val listOfPowers = listOfValues.map(value => Math.pow(value, N).toInt)

            val lists = (0 until maxValue).toList.foldLeft(List(List(0)): List[List[Int]]) ((newList, i) => 
                    newList :+ (newList.last union (newList.last.map(y => y + listOfPowers.apply(i)).filter(z => z <= X)))
            )

            lists.last.count(_ == X)        

    }
}
于 2014-04-07T17:51:21.720 に答える