0

次のことを行うアルゴリズムを設計しようとしています。

入力：

プロパティのセットにマップされたキーのセット (合計 n) があります。プロパティには、各プロパティの重みとプロパティの値が含まれています。

出力：

プロパティのセットとそれぞれの重みと値に基づいて、修飾されたキーのセット (合計 k) を特定します。

さらに、勝者を選択するサイクルごとにデータを変更して、次のサイクルで選ばれなかった人の可能性が上がるようにする必要があります (一方、勝者の可能性は、その人がまったく新しい人であるかのようになります)。システム）。

うまくいけば、当面の問題は明確です。基本的に、プロパティの値とそれぞれの重みによって、どのキーが勝つ可能性が高いかが決まり (値が大きく、重みが大きいほど、そのキーが勝つ可能性が高くなります)、最終的には全員を選択することになります。

これを行う方法についてのご意見をいただければ幸いです。

ありがとう！- アジーム

4

2 に答える 2

1

ウェイトをラインのセグメントと見なし、ライン全体の長さはウェイトの合計に等しくなります。0 からその長さの間の一様乱数を選びます。勝者は、番号が該当するセグメントの候補です。

その勝者を削除し、それに応じて行全体の長さを減らします。を選択するまで、残りの候補を使用してプロセスを繰り返しますk。

サイクルの後、敗者を再スケーリングして元の長さのほとんどを占め、残りの小さなチャンクを均等に分割して勝者を追加します。

于 2010-10-18T17:22:39.863 に答える
0

最適化されていないが効果的な方法は、すべての競技者のリストを作成し、重みに比例して競技者に追加のインデックスを追加することです。

疑似は実際の実装のコンテキストから完全に外れていますが、アイデアを得る必要があります。

const int DEFAULT_WEIGHT = 1;
public List<Contestant> items = new List<Contestant>();
public List<Guid> LotteryPool = new List<int>();

public Contestant Roll()
{
     Random rnd = new Random();
     rnd.Seed = DateTime.Now.Ticks;

     // Generate LotteryPool
     foreach(Contestant item in items)
     {
              for(int i = 0; i < item.Weight; i++)
              {
                       LotteryPool.Add(item.Id);
              }

              item.Weight++;
     }

     // Find the contestant matching a random id from the pool.
     Contestant result = FindContestant(LotteryPool[rnd.Next(0, LotterPool.Count]);

     // apply the default weight the winner
     result.Weight = DEFAULT_WEIGHT;

     return result;
}
于 2010-10-18T17:11:39.250 に答える