2

私は小さなソフトウェアを作成していますが、概念的な問題に遭遇しました。私は小さな例で状況を説明しようとします:

  • 複数の点を含む座標系があります。
  • 各ポイントは、x軸とy軸上の位置(これまでのところ通常)で表され、青または赤のいずれかになります。
  • 次に、イベントを作成します。
  • 各イベントには1つの青と1つの赤のポイントが含まれており、それらを選択する方法にはいくつかの条件があります。
    • 例:blue(x)とred(x)の合計(=青と赤の点のx値)は偶数でなければなりません。
    • 同時に、y値のチェックサムが素数であってはならないという条件があるかもしれません。
  • 各ポイントは、複数のイベントの一部にすることができます。
  • 私の状況では、すべてのポイントには、イベントの作成時に「使用」される特定のリソースがあり、必要な量のリソースがある限り、ポイントは新しいイベントの一部にすることができます。

私が必要としているのは、できるだけ多くのイベントを作成することです(つまり、青または赤のグループのリソースが使い果たされるまで)。赤と青のポイントが2つあるとしましょう。はいおよびいいえは、それらが所定の条件を満たすかどうかを意味します。

B1R1はい
B1R2はい
B2R1はい
B2R2いいえ

B1とR1(各リストの一番上)を一致させると、B2とR2が一致しないため、1つのイベントしか取得されません。一方、B1をR2と一致させ、B2をR1と一致させると、2つのイベントを受け取ります。これが私に必要なものです。

また、私のイベントの平均距離(青い点から赤い点まで)はできるだけ短くする必要があります。

条件に一致する限り、青と赤のポイントをランダムに選択してイベントを作成することを考えました。プロセス全体を複数回実行し、イベントの数が最も多く、平均距離が最も短い結果を維持します。しかし、結果の品質については何も言えないので、私はそれが本当に好きではありません。また、結果は決定論的ではありません。

どんな助けでも大歓迎です。

4

2 に答える 2

0

これは興味深い問題ですが、考慮すべきパラメータが非常に多いようです。

最初のステップとして、互換性マトリックスを使用して問題/パラメーターの表示を単純化しようとします。マトリックスの行は青い点に対応し、マトリックスの列は赤い点を表します。サンプルの問題の場合、マトリックスは次のようになります。

     R1    R2

B1   1     1

B2   1     0

したがって、このマトリックスは、イベントを作成するためにどのポイントを他のどのポイントとペアにすることができるかを表します。

次に、この行列を使用して、説明のサンプル問題を解決してみましょう。これは、少し動的計画法を使用して行うことができます。

  1. Rすべてのポイントが存在するが、使用可能な青いポイントは。だけであると想定しますB1。可能な組み合わせをリストするソリューションベクトルを作成します。だからあなたは得るでしょう[(R1, B1)], [(R2, B1)]

  2. ここで、前のステップで作成したソリューションベクトルを段階的に導入します。B2解ベクトルの最初のコンポーネントについてはR1、前のステップですでに使い果たされており、R2と比較できないB2ため、この解を改善できないことに注意してください。ただし、解ベクトルの2番目のコンポーネントは、(R1, B2)追加できるため、改善できます。したがって、最終的な解のベクトルを取得し[(R1, B1)],[(R2, B1), (R1, B2)]ます。

  3. これで、ソリューションベクトルの個々のコンポーネントをカウントし、アイテム(または場合によってはイベント)の数が最も多いコンポーネントを選択できます。

このアプローチを問題の完全版に拡張することは可能だと思いますが、(リソースの使用状況も追跡する必要があるため)さらに多くのハウスキーピングが必要になります。サンプルとは異なり、最初のステップでペアリングするR1ことB1は、必ずしもそれR1が終了したことを意味するわけではありません...再利用できるように十分なリソースがある可能性があります。

これにより、少なくともいくつかの洞察が得られることを願っています。幸運を!:)

于 2012-11-29T18:05:25.157 に答える
0

疑わしい場合は、ブルート フォースから始めます (少なくとも他のソリューションの有効性を確認できるようにするため) - 非常に小さなテスト データ セット *(例: 4+3 ポイント => n=4*3 の可能なペア):

  1. すべての可能なペアの積から、可能なイベントの配列を作成します(条件に一致する青と赤のペアのリスト、このステップで距離も事前計算します)
    - 最悪の場合のサイズn = red_count * blue_count
  2. この配列をセットのセットにコピーします。それぞれのセットには 1 つのイベントのみが含まれます。{{(r1,b1)}, {(r1,b2)}, ...}
  3. 各セット:

    • ポイントのリソースを更新します(コースごとに個別に保存されます)
    • 一致するリソースがまだある場合は、次のように、さらに 1 つのペアを追加して現在のセットを分割し(追加できるペアごとに実行します)、現在の未完了のセットを削除します。

      4 sets of 1 event     10 sets of 2 events
      e1 e2 e3 e4              e1 e2 e3 e4
      x  x  x  x            e1 x  x  x  x
                        ->  e2    x  x  x
                            e3       x  x
                            e4          x
      
    • 新しいペアで改善できるセットがなくなるまで繰り返します (リソースがなくなるか、すべてのペアが使用されます)。

=> 最悪のケースO(n 2k ) (n=r*b=考えられるすべての赤/青のペア、k = 最大セット内のイベントの数)

次に、グローバルな最適化手法に触発されます。より詳細な仕様がないと、要件をどのように組み合わせることができるかわかりません...

ステップ 1 と 2 は O(n) => おそらく5000*300 = 1.5mペアで許容可能

イベントの配列を距離でソートしようとします-O(nlogn) -そして、ヒューリスティックアルゴリズムの開始点として最短のイベントのみを使用xします(パフォーマンス/精度のトレードオフを確認するために1〜10の最短をテストします)+x最短のセットのみを保持します分割...

于 2012-11-29T16:26:08.830 に答える