重み付けされたオブジェクトのリストがあります。つまり:
A->1 B->1 C->3 D->2 E->3
重みに応じてランダムな要素を選択する C++ の効率的なアルゴリズムはありますか?
たとえば、アルゴリズムが要素 CE (10%) または要素 D (20%) を選択する可能性よりも、重みの低い要素 A または B が選択される可能性 (30%) が高くなります。
1049 次
1 に答える
2
@Dukeling が言ったように、もっと情報が必要です。選択のチャンスをどのように解釈して使用するかのように。
少なくとも進化的アルゴリズムの分野では、フィットネス スケーリング(または選択チャンス スケーリング) はかなりのトピックです。
悪いスコアから始めるとします
B[i] = how badly you don't want to select the i-th item
目的は、フィットネス/選択スコアを計算することです。これは、ルーレット ホイールS[i]の方法で使用することを想定しています。
あなたが言うように、明白な方法の 1 つは乗法逆数を使用することです。
S[i] = 1 / B[i]
ただし、それには少し問題があるかもしれません。価値が低い場合の同じ量の変化は、すでに価値が高いB[i]場合の同じ量の変化よりもはるかに大きな影響を与えます。B[i]
これを自問してください：
Say
B[1] = 1 -> S[1] = 1
B[2] = 2 -> S[2] = 0.5
So item 1 is twice times as likely to be selected compared to item 2
But with the same amount of change
B[3] = 1000 -> S[3] = 0.001
B[4] = 1001 -> S[4] = 0.000999001
Item 3 is only 1.001 times as likely to be selected compared to item 4
ここでは、考えられる代替案を 1 つだけ紹介します。
S[i] = max(B) - B[i] + 1
+ 1パーツが役立つので、選択される可能性がゼロになるアイテムはありません。
これで、選択スコアの計算の部分は終了です。
次に、選択スコアをルーレット式に使用する方法を明らかにしましょう。加法的逆スキームを使用することにしたとします。
B[1] = 1 -> S[1] = 1001
B[2] = 2 -> S[2] = 1000
B[3] = 1000 -> S[3] = 2
B[4] = 1001 -> S[4] = 1
次に、スコアの各ポイントが宝くじに対応していると想像してください。チケットに実行中の ID を割り当てましょう。
| Item | Score = #ticket | ticket ID | win chance |
| 1 | 1001 | 0 to 1000 | 1001/2004 ~ 0.499500998 |
| 2 | 1000 | 1001 to 2000 | 1000/2004 ~ 0.499001996 |
| 3 | 2 | 2001 to 2002 | 2/2004 ~ 0.000998004 |
| 4 | 1 | 2003 to 2003 | 1/2004 ~ 0.000499002 |
全部で2004枚のチケットがあります。
選択を行うには、当選チケット ID をランダムに選択します。つまり、ランダム範囲は [0,2004] です。
この質問ですでに見たように、バイナリ検索を使用して、どのアイテムが当選チケットを所有しているかをすばやく調べることができます。二分探索で調べる必要があるのは、スコアそのものではなく、チケット IDの境界値です。1001,2001,2003
比較のために、乗法逆法を使用した場合の選択確率を次に示します。
| Item | win chance |
| 1 | 1/1.501999001 ~ 0.665779404 |
| 2 | 0.5/1.501999001 ~ 0.332889702 |
| 3 | 0.001/1.501999001 ~ 0.000665779 |
| 4 | 0.000999001/1.501999001 ~ 0.000665114 |
加法的逆スキームでは、1 単位の悪さは一貫して選択確率の約 0.0005 の差に対応することがわかります。
一方、乗法逆スキームでは、1単位の悪さにより、さまざまな選択チャンスの差が生じます。
于 2013-05-25T17:07:41.563 に答える