6

ここには本当にアルゴリズムのマスターが必要です！たとえば、次のような配列を取得しました。

[
    [870, 23]
    [970, 78]
    [110, 50]
]

そして私はそれを分割したいので、それは次のようになります：

// first array
[
    [970, 78]
]
// second array
[
    [870, 23]
    [110, 50]
]

だから今、なぜ私もそれをこのように見せたいのですか？

サブ値の合計をできるだけ等しくしたいからです。ですから、970についてです。したがって、この場合、それらを分割して最初のサブ値のみを見ると、それはすでに正しいので、非常に簡単ですが、両方をチェックして、可能な限り等しく保ちたいので、 100個のサブ配列を取得した配列！だから、誰かが私がこれをプログラムできるアルゴリズムを教えてくれるなら、それは本当に素晴らしいでしょう！870 + 1107823 + 50

スケール：

  • 配列内の最大1000個の要素（サブリスト）
  • 要素は10^9までの整数です

私は「十分に近い解決策」を探しています-それは正確に最適な解決策である必要はありません。

4

4 に答える 4

2

元の投稿での議論から私が集めたものから、あなたは単一の分割点を探しているのではなく、2つのセットのそれぞれの合計がほぼ等しくなるようにすべてのペアを2つのセットに分散させたいと考えています。

十分に近い解決策が受け入れられるので、シミュレーテッドアニーリングに基づくアプローチを試すことができますか？（http://en.wikipedia.org/wiki/Simulated_annealingを参照）

つまり、各ペアを左または右のセットにランダムに割り当てることから始めるという考え方です。次に、次のいずれかによって新しい状態を生成します

  • a）ランダムに選択したペアを左から右のセットに移動します。
  • b）ランダムに選択したペアを右から左のセットに移動する。
  • c）両方を行う。

次に、この新しい状態が現在の状態よりも良いか悪いかを判断します。それが良い場合は、それを使用してください。悪い場合は、受け入れ確率関数によって受け入れられた場合にのみそれを取ります。これは、最初は悪い状態を使用できるようにする関数ですが、時間が経つにつれて（または「温度が下がる」）、徐々に悪い状態を優先します。 SA用語）。多数の反復（たとえば100.000）の後、かなり良い結果が得られるはずです。

必要に応じて、このアルゴリズムを複数回再実行します。これは、ローカル最適点でスタックする可能性があるためです（ただし、受け入れ確率関数はこれに対抗しようとします）。

このアプローチの利点は、実装が簡単であり、より良いソリューションを探し続ける期間を自分で決めることができることです。

于 2012-10-28T20:00:27.183 に答える
2

まず、すでに確立されているように、問題はNP-Hardであり、分割問題から縮小されます。

リダクション: パーティションの問題
のインスタンスが与えられた場合、それぞれサイズ 1 のリストを作成します。結果はまさにこの問題になります。

上記の結論:
この問題は NP 困難であり、既知の多項式解はありません。

第二に、問題の規模のために、指数関数的および疑似多項式の解は機能するのに時間がかかりすぎます。

第三に、ヒューリスティックと近似アルゴリズムが残ります。

次のアプローチをお勧めします。

  1. サブリストのスケールを正規化して、すべての要素が同じスケールになるようにします (たとえば、すべてが範囲[-1,1]に正規化されるか、すべてが標準正規分布に正規化されます)。
  2. 新しいリストを作成します。各要素は、正規化されたリスト内の一致するサブリストの合計になります。
  3. サブセット合計/分割問題用に開発された近似またはヒューリスティック ソリューションを使用します。

結果は最適ではありませんが、ここでは最適は実際には達成できません。

于 2012-10-28T19:42:01.683 に答える
1

配列の真ん中で、配列を最初と 2 番目の部分に分割する場所を探しているだけだと思います。

線形アルゴリズムがこれを行うことができるようです。JavaScript でこのようなもの。

arrayLength = 2;
tolerance = 10;

// Initialize the two sums.
firstSum = [];
secondSum = [];
for (j = 0; j < arrayLength; j++)
{
   firstSum[j] = 0;
   secondSum[j] = 0;
   for (i = 0; i < arrays.length; i++)
   {
      secondSum += arrays[i][j];
   }
}

// Try splitting at every place in "arrays".
// Try to get the sums as close as possible.
for (i = 0; i < arrays.length; i++)
{
   goodEnough = true;
   for (j = 0; j < arrayLength; j++)
   {
      if (Math.abs(firstSum[j] - secondSum[j]) > tolerance)
         goodEnough = false;
   }

   if (goodEnough)
   {
      alert("split before index " + i);
      break;
   }

   // Update the sums for the new position.
   for (j = 0; j < arrayLength; j++)
   {
      firstSum[j] += arrays[i][j];
      secondSum[j] -= arrays[i][j];
   }
}
于 2012-10-28T19:39:17.010 に答える
0

すべての回答に感謝します。ブルートフォース攻撃は良いアイデアであり、NP-Hard もこれに関連していますが、これは複数のナップサックの問題であり、この pdf ドキュメントを使用して解決できることがわかりました。

于 2012-11-02T06:39:13.697 に答える