5

以下で説明する問題を処理できるアルゴリズムを探しています。私はすでにアルゴリズムを作成しており（投稿するには専門的すぎると思います）、考えられる限り最適化されていますが、より大きな数のセットではまだ遅すぎます（コストが指数関数的に上昇するため）。このソリューションは、適切なコンピューターで 5 秒もかからないはずです。

一連の数字が与えられます。たとえば、次のようになります。

M = { 1, 1, 1, 2, 2, 2, 5, 5, 5, 10, 10, 10, 10, 20, 50, 50, 50, ... , 10000, 10000, 20000, 20000 }

特別な構造を持つ必要はありません (ただし、ここにはあります)。

「ターゲット ポイント」のセットと数値が与えられます。たとえば、次のようになります。

P = { 670、2010、5600、10510、15000}

目標は、 M から最小量の数値を取得することです。ここで、それらを決定された順序で追加すると、P 内のすべてのポイントにできるだけ近い中間結果が得られます。M 内の各数値のみを使用できます。一度。

この例では、考えられる解決策は次のようになります (ただし、それが最適かどうかはわかりません)。

Y = (500, 100, 50 ; 1000, 200, 200; 2000, 1000, 500; 5000; 2000, 2000)

ご覧のとおり、2 つの基準は、ある種のトレードオフに対して最小であり、近いです。それが、私の現在のアルゴリズムがスコアリングを使用して「最適な」ソリューションを見つける理由です。

現在の仕組みは次のとおりです。

  1. M を並べ替え、P を並べ替え、昇順
  2. スコアを適切に変更するには小さすぎる数値、または単純に大きすぎる数値を削除します
  3. 再帰的に:
  4. P の次のポイントを現在の「ターゲット」として取り、プラス マイナス 10% など
  5. M から次の番号を追加し、M の場合は削除します
  6. 目的地に近い場合は4へ。終点にある場合は、現在の分布のスコアを計算し、場合によってはそれを覚えておいてください
  7. そうでなければ5に行く
  8. 番号の試行から戻ってきたら、次に高い番号を取る

2 つの同じ番号を試行することはなく、昇順のみを試行します。たとえば、次のようになります。

  • 100、100、100、50、50、20、10
  • 100、100、100、50、50、20、20
  • 100、100、100、50、50、50、10
  • 100、100、100、50、50、50、20
  • 100、100、100、50、50、50、50
  • 100、100、100、100
  • 100、100、100、100、10
  • 100、100、100、100、20
  • ...

各数値が約 5 で、小さい数値の多くが削除されるため、アルゴリズムは非常に高速で、適切な解を見つけます。しかし、より多くの数値を追加したり、特に小さい数値を含めたりすると、実行時間は 100 ミリ秒から無限に上昇します。

この問題に対処する方法を教えてください。問題またはその一部を処理できる文献に同様のアルゴリズムはありますか?

4

3 に答える 3

0

コイン交換の問題に似ています：http：//www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro.htm

唯一の違いは、「コイン」の供給が限られていること（配列内のアイテムを「使用済み」としてマークすることで簡単に解決できる）と、正確な数に到達する必要がないことです-プラス/マイナス10％はあなたにとって良い（目標値の10％未満のMの要素を捨てることができるように）

于 2009-08-15T13:13:35.150 に答える
0

試してみてください。最高ではないかもしれませんが、うまく機能するはずです。私はここでPHPを使用しています -

1) M の値とそのカウントを分類します。これを C と呼びましょう。

$C = array_count_values( $M );

This gives us:
Array
(
    [1] => 3
    [2] => 3
     ...
    [20] => 1
     ...
)

2) P から最初の数を取り出し、M に二分探索を適用して、P1 に最も近い数 N1 (N1 < P1) を取得します。Cからそれぞれのカウントを引きます

    So say you get 500 which is nearest to 670. Now subtract $C[500] - 1.
You can validate if count is not 0 and if zero get the next lower number from M.

3) P1-N1 を取得し、この数値の二分探索を再度行い、最も近い値を返します。これを N1 に追加し、最も近い合計が得られるまでループを続けます。

4) P のすべてのメンバーについて、ポイント 2 とポイント 3 を繰り返します。

二分探索はここで重要な部分であり、十分に効率的であるはずです。

于 2009-08-15T08:04:47.990 に答える