4

それぞれが 0 ～ 10 の値のプロパティを含むアイテムの辞書を取得し、さまざまな要素を追加して、どのアイテムの組み合わせが目的の合計を達成するかを選択するスクリプトを作成しようとしています。同じ「スロット」を共有するアイテムのみを使用して、これを行うスクリプトも必要です。

例えば：

item_list = {
 'item_1': {'slot': 'top', 'prop_a': 2, 'prop_b': 0, 'prop_c': 2, 'prop_d': 1 },
 'item_2': {'slot': 'top', 'prop_a': 5, 'prop_b': 0, 'prop_c': 1, 'prop_d':-1 },
 'item_3': {'slot': 'top', 'prop_a': 2, 'prop_b': 5, 'prop_c': 2, 'prop_d':-2 },
 'item_4': {'slot': 'mid', 'prop_a': 5, 'prop_b': 5, 'prop_c':-5, 'prop_d': 0 },
 'item_5': {'slot': 'mid', 'prop_a':10, 'prop_b': 0, 'prop_c':-5, 'prop_d': 0 },
 'item_6': {'slot': 'mid', 'prop_a':-5, 'prop_b': 2, 'prop_c': 3, 'prop_d': 5 },
 'item_7': {'slot': 'bot', 'prop_a': 1, 'prop_b': 3, 'prop_c':-4, 'prop_d': 4 },
 'item_8': {'slot': 'bot', 'prop_a': 2, 'prop_b': 2, 'prop_c': 0, 'prop_d': 0 },
 'item_9': {'slot': 'bot', 'prop_a': 3, 'prop_b': 1, 'prop_c': 4, 'prop_d':-4 },
}

次に、スクリプトは、「item_list」ディクテーションから、「スロット」ごとに 1 つのアイテムを使用して、追加したときに目的の結果が得られる組み合わせを選択する必要があります。

たとえば、必要な結果が 'prop_a': 3、'prop_b': 3、'prop_c': 8、'prop_d': 0 の場合、スクリプトは 'item_2'、'item_6'、および 'item_9' を選択します。機能した他の組み合わせと一緒に。

'item_2': {'slot': 'top', 'prop_a': 5, 'prop_b': 0, 'prop_c': 1, 'prop_d':-1 }
'item_6': {'slot': 'mid', 'prop_a':-5, 'prop_b': 2, 'prop_c': 3, 'prop_d': 5 }
'item_9': {'slot': 'bot', 'prop_a': 3, 'prop_b': 1, 'prop_c': 4, 'prop_d':-4 }
 'total':                 'prop_a': 3, 'prop_b': 3, 'prop_c': 8, 'prop_d': 0

これを達成する方法はありますか？Python や完全なスクリプトである必要はありませんが、理論的にこれを行う方法についての説明だけで十分です。すべての組み合わせをループしてみましたが、すぐに手に負えなくなり、手に負えなくなったようです。実際のスクリプトでは、それぞれ 8 つのプロパティを持つ 20 の異なる「スロット」を使用して、約 1,000 のアイテムに対してこれを行う必要があります。

助けてくれてありがとう！

4

4 に答える 4

7

プロパティは正の値と負の値の両方を持つことができ、すべての満足のいく組み合わせが必要なので、「本質的な」最適化は不可能だと思います。つまり、多項式時間の解はありません (P != NP...;-) . すべての解決策は、スロットごとに 1 つの組み合わせをすべて列挙し、最終結果を確認することに帰着します。非常に小さな調整を行うことで、あちこちで数パーセントの労力を節約できる可能性がありますが、それほど大きなことはありません。

50**2020 の可能なスロットに 1000 のアイテムがあり、スロットごとに約 50 のアイテムが均等に分散されているとし9536743164062500000000000000000000ます10**34。一般に、「すべての解の検索」からサブツリーを「刈り込む」ことはできません。最初のスロットの仮説上の選択がある場合、小道具の値に関係なく、満たすことができる残りのスロットの選択20-pがまだある可能性pがあるためです。制約 (または複数)。

この NP 完全問題の正確な多項式時間解を見つけることができれば、基本的に現代の数学とコンピューター サイエンスに革命をもたらしたことになります。これはあまりありそうにありません。

実行可能な問題に到達するには、いくつかの方法で要件を緩和する必要があります (ソリューションのサブセットのみを見つける可能性を受け入れる、決定論的アプローチではなく確率論的アプローチを受け入れる、おおよその解決策を受け入れるなど)。

これを行うと、いくつかの小さな最適化が理にかなっている場合があります。たとえば、すべてのプロパティ値とターゲットに対して定数 (各プロパティの最小の負の値よりも 1 大きい値) を合計することから始めて、すべてのプロップ値が > 0 になるようにします。 - これで、(たとえば) いくつかのプロパティの値、またはすべてのプロパティの合計でスロットをソートし、部分的な仮想ソリューションにスロットをもう 1 つ追加すると、各累積プロップ値が少なくとも増加するという知識に基づいて、いくつかの剪定を行うことができます。 X と少なくとも Y の合計 (したがって、いずれかの条件によって実行中の合計が目標を超える場合は、そのブランチをプルーニングできます)。一般に、この種のヒューリスティックな近似は、big-O の動作を改善する必要はありませんが、問題を計算上実行可能に近づけるのに十分なだけ、期待される乗数の値を減らすことができます。

しかし、要件の緩和が不可能な場合は、そのような巧妙な小さなトリックを探す価値さえありません。その場合、問題は計算的に実行不可能なままになるため、巧妙な小さな最適化を探すことは、実際には生産的ではありません。

于 2010-04-25T17:34:18.757 に答える
4

この問題は基本的に、部分和問題(これは NP 完全です) を多次元に一般化したものです。問題を言い換えると (同じ問題を解決していることを確認するため)、1000 個のアイテムが 20 個のクラス (スロットと呼ばれます) に分割されています。各項目には、8 つのプロパティのそれぞれについて [-10,10] の整数値があります。したがって、各項目は 8 次元ベクトルの値を持つと見なすことができます。各スロットから 1 つのアイテムを選択して、合計値 (これらの 8 次元ベクトルを追加) が特定のベクトルになるようにします。

あなたが与えた例では、4つの次元があり、3つのクラスの9つのアイテムには値(2,0,2,1)、(5,0,1,-1)、...などがあり、選択したい合計（3,3,8,0）を作るために各クラスから1つのアイテム。右？

強引な

まず、すべての可能性を列挙する力ずくの検索があります。1000 個のアイテムが 20 個のクラスに均等に分割されていると仮定すると (それぞれに 50 個あります)、クラスごとに 50 個の選択肢があります。 8 つの座標のそれぞれに沿って 20 の要素を合計してチェックすると、実行時間は ∝ 50 20 ·20 ·8 になります): これは実現不可能です。

動的計画法、単発

次に、動的プログラミングのソリューションがありますが、これは異なります。実際には、ブルートフォースが実行不可能な場合に機能することがよくありますが、この場合も残念ながら実行不可能に見えます。(「プロパティ値」のより良い境界が得られれば、指数関数的に改善されます。) ここでのアイデアは、可能な合計に到達する 1 つの方法を追跡することです。[-10,10] からの 20 個の数の合計は [-200,200] にあるため、400 8しかありません。=655360000000000000000 8 次元ベクトルの可能な合計。(これは他の検索空間のほんの一部ですが、慰めにはなりません。各「プロパティ」について、[各クラスの最大アイテム] と [各クラスの最小アイテム] の合計の差を取ることもできます。 ] を使用して 400 をより小さな数に置き換えます。) 動的計画法アルゴリズムの考え方は次のとおりです。

  • last[(a,b,c,d,e,f,g,h)][k] は、k 番目のクラスから (最初の k-1 クラスからそれぞれ 1 つのアイテムと共に) 取得できる 1 つのアイテムを示します。正確な合計 (a,b,c,d,e,f,g,h)。次に、擬似コード：

    for k=1 to 20:
    for each item i in class k:
        for each vector v for which last[v][k-1] is not null:
            last[v + value(i)][k] = i

次に、目的の最終合計が s の場合、k 番目のクラスからアイテム last[s][k] を選択し、(k-1) 番目のクラスからアイテム last[s-value(i)][k-1] を選択します。等々。これには、最悪の場合 ∝ 20·50·400 8 ·8 の時間がかかります(厳密な分析ではなく、緩い上限のみ)。

動的計画法、個別

「完璧な」ソリューションについてはこれで終わりです。ただし、ヒューリスティックなソリューションと「実際に機能する可能性が最も高い」ソリューションを許可する場合は、(問題を正確に解決する場合でも) より適切に行うことができます。たとえば、8 つの次元ごとに問題を個別に解くことができます。これはさらに簡単に実装でき、最悪の場合でも ∝ 20・50・400・8=3200000 の時間しかかからず、非常に簡単に実行できます。last[][] を単一の要素ではなくリストとして保持すると、最後に（効果的に）そのために指定された合計を達成するサブセットのリストがあります座標（「製品形態」）。実際には、必要な合計に正確に一致するサブセットは多くない可能性があるため、サブセットの数が最も少ない座標から始めて、残りの 7 つの座標についてそれらの各サブセットを試すことができます。このステップの複雑さは、問題のデータによって異なりますが、(1) 合計が等しいセットがほとんどない可能性があると私は考えています (または期待できます)。チェックするか、または (2) 与えられた合計のセットが多数あります。この場合、かなり早い段階で 1 つを見つけることができます。

いずれにせよ、最初に各座標に対して動的プログラミングを個別に行うと、第 2 段階ではるかに小さな空間を検索できるようになります。

近似アルゴリズム

合計が正確に等しくなる必要がなく、必要な合計の特定の係数内にある合計を受け入れる場合は、サブセットの FPTAS (完全多項式時間近似スキーム) を取得するために使用されるよく知られたアイデアがあります。時間多項式 (アイテムの数など) と 1/ε で実行される合計問題。これを説明するのに時間がかかりましたが、調べてみてください。基本的には、400 8スペースをより小さなスペースに置き換えるだけです。たとえば、数値を最も近い 5 の倍数に丸めるなどです。

于 2010-04-25T20:11:39.040 に答える
3

これは、一般に動的計画法で解決されるナップザック問題の変形のように思えます。

しかし、おそらく再帰を使用して、かなり単純な (ただし遅い) ソリューションを作成できます。

def GetItemsForSlot(item_list, slot):
  return [ (k,v) for (k,v) in item_list.items() if v['slot'] == slot]

def SubtractWeights(current_weights, item_weights):
  remaining_weights = {}
  for (k,v) in current_weights.items():
      remaining_weights[k] = current_weights[k] - item_weights[k]
  return remaining_weights

def AllWeightsAreZero(remaining_weights):
  return not [v for v in remaining_weights.values() if v != 0]

def choose_items(item_list, remaining_weights, available_slots,
                 accumulated_items=[ ]):
    print "choose_items: ", remaining_weights, available_slots, \
      accumulated_items
    # Base case: we have no more available slots.
    if not available_slots:
      if AllWeightsAreZero(remaining_weights):
          # This is a solution.
          print "SOLUTION FOUND: ", accumulated_items
          return
      else:
          # This had remaining weight, not a solution.
          return

    # Pick the next available_slot
    slot = available_slots[0]
    # Iterate over each item for this slot, checking to see if they're in a
    # solution.
    for name, properties in GetItemsForSlot(item_list, slot):
        choose_items(item_list, # pass the items recursively
                     SubtractWeights(remaining_weights, properties),
                     available_slots[1:], # pass remaining slots
                     accumulated_items + [name]) # Add this item




if __name__ == "__main__":
    total_weights = {
       'prop_a': 3,
       'prop_b': 3,
       'prop_c': 8,
       'prop_d': 0
    }

    choose_items(item_list, total_weights, ["top", "mid", "bot"])

これはテスト済みで、動作しているように見えました。ただし、約束はありません:)

slot と prop_a を同じオブジェクトのプロパティとして保持すると、操作が少し難しくなります。コードを理解しやすくするために、辞書の代わりにクラスを使用することをお勧めします。

于 2010-04-25T16:47:16.953 に答える
1

すべての組み合わせをループしてみましたが、すぐに手に負えなくなり、手に負えなくなったようです。実際のスクリプトでは、それぞれ 8 つのプロパティを持つ 20 の異なる「スロット」を使用して、約 1,000 のアイテムに対してこれを行う必要があります。

最初に適切なオブジェクト階層に構造をロードしてから、それを区分的に解決することは、あなたの考え方を助けるかもしれません。

例：

class Items(dict):
    def find(self, **clauses):
        # TODO!

class Slots(dict):
    # TODO!

items = Items()
for item, slots in item_list.items():
    items[item] = Slots(slots)
    # consider abstracting out slot based on location (top, mid, bot) too

print items.find(prop_a=3, prop_b=3, prop_c=8, prop_d=0)
于 2010-04-25T17:01:14.640 に答える