3

したがって、私はいくつかのセットを持っており、すべてのセットから少なくとも1つの要素を含むセットの最小数を見つける必要があります。これをより具体的にするために、私は一連のサーバー名を持っており、各サーバーにはサービスウィンドウがあります。特定の期間を指定して、指定されたすべてのサーバーをカバーするサービスウィンドウの最小セットを見つけたいと思います。

目的のマシンごとに、重複しないすべてのN分の時間セグメントのリストを生成するコードがすでにあります。可能なすべての組み合わせを生成し、一意の要素の数が最も少ないものを選択することで、ブルートフォース攻撃を行うつもりでしたが、最初にすべてのホストからの一意のウィンドウだけにセットを減らしたとしても、それは信じられないほど非効率的です（特にいくつかのシステムよりも）。

次に、各タイムスロットに収まるホストの数でタイムスロットを並べ替え、ホストの数が最も多いスロットを選択し、割り当てられていないホストのすべてのスロットのリストを再生成して、最も多くを選択するようなことを考えました。すべてのホストが考慮されるまで、人気のあるスロット、再計算など。それで答えは得られますが、最もバランスの取れたセットを選択する機会は実際にはありません。第2の目標は、サービスあたりのホスト数の標準偏差が最小のサービスウィンドウのセットを見つけることです。窓。したがって、100個のホストがある場合、上記のアルゴリズムで検出される可能性のある3つの「98、1、および1」ウィンドウを実行するのではなく、ウィンドウごとに約50個のホストを提供するウィンドウを優先します。しかし、私のオプションが「98、1、1」の場合 または、それぞれ10個のウィンドウが10個あります。私はむしろ3つをしたいです。

とにかく、この問題を表すためにある種のグラフを使用できるようですが、CSパスではソフトウェアよりもハードウェアに重点を置いており、グラフの問題を解決することは決して私の得意ではありませんでした。したがって、この特定の問題や適切な検索用語の詳細をどこで読むかについて、いくつかの提案をいただければ幸いです。:)

4

2 に答える 2

2

これは集合被覆最適化問題であり、NP困難です。つまり、最悪の場合、ブルートフォースよりもうまくやることはできません。それはあなたがすぐにカバーを見つけることができるセットのいくつかの配置があります。しかし、特に実世界のデータでは、問題を確実に単純化できます。

まず、データに対していくつかの変換を行います。セットをブール値のグリッドとして想像してください。各列はサーバーを表し、各行はセットを表します。セル内のTrueは、サーバーがそのセットに存在することを意味します。

  1. まったく同じセットに属する複数のサーバーがある可能性があります。つまり、このマトリックスには同じ列が存在する可能性があります。重複する列はすべて削除できます。したがって、AとBに正確に保存サービスウィンドウがある場合、Aを含むカバーを取得するとBも含まれます。この列の値で各サーバーをハッシュし、同じハッシュバケット内の各サーバーをチェックすることでこれを高速に行うことができます。同一のセットメンバーシップ。サーバーを1つだけ保持し、「ライドアロング」サーバーのリストを作成します。例えば。この時点から、これらのサーバーはセットの単一メンバーとして扱われます。

  2. 他の単一のセットのサブセットであるセットをすべて削除します。たとえば、{1,2,3}と{1,2}がある場合。問題から{1,2}を削除します。カバーするセットを選ぶときは、{1,2,3}が常により良い選択になります。したがって、サブセットをダンプします。たとえば、そのような行をすべて削除します。

  3. 各サーバー（たとえば、各列）を繰り返し処理します。1つのセット（たとえば、列に1つだけtrue）に存在する各サーバーは、そのセットがソリューションの一部である必要があります。したがって、そのセットをソリューションに追加し、マトリックスから削除します。これで、削除されたセット内の列をマトリックスから削除できます。サーバーAがセット1、つまり{A、B、C}にのみ存在するとします。ウェルセット1はソリューションの一部である必要があります。もしそうなら、サーバーA、B、Cが自動的にカバーされることを自動的に知っています。そこで、A、B、Cの行列と列からセット1を削除します。

  4. すべてのセットにあるサーバーをすべて削除します。彼らはどんな解決策にもなります。

この後、データセットが「逆」でない限り、実際の問題セットは大幅に削減されます。実世界のデータは、多くの行と列が問題から脱落するのに十分な順序である可能性があります。

実際には、実世界のデータの総当たり攻撃よりも優れた時間で最適なカバレッジに非常に近い答えを検索するための良い方法があると確信しています。

DPまたはA-Star検索ソリューションを検討します。時間切れです。後でスケッチするかもしれません。

于 2012-07-11T11:25:42.933 に答える
1

各時間セグメントに関連付けられた個々のサーバーのセットを検討してください。ユニオンにすべてのサーバーが含まれるように、これらのセットのサブセットを構築しようとしています。これは集合被覆問題として知られており、NP完全であることが示されています。これは、質問で説明した力ずくのアプローチよりもうまくいくことができないことを意味します。したがって、すべてのホストからの一意のウィンドウの数をできるだけ少なくしてください。

PStemplatetypedefが彼の答えを削除した 理由がわかりません-それは正しかったと思います。

于 2012-07-11T03:52:09.573 に答える