C++倒加权随机播放/随机

Question

我有重物即：

A->1 B->1 C->3 D->2 E->3

是有在C++中的高效算法根据它们的重量挑选随机元素的列表？

例如可能性元件A或B具有较低的权重被拾取率较高（30％）比算法选择的可能性元件CE（10％）或d（20％）

Answer 1

作为@杜克林说，我们需要更多的信息。就像你如何解读和使用选择机会一样。

至少在进化算法领域，健身缩放（或选择机会缩放）是一个相当大的话题。

假设你开始了与不良得分

B[i] = how badly you don't want to select the i-th item 

，目标是计算健身 /选择得分S[i]我以为你是在roulette wheel的方式来使用它。

正如你所说，一个明显的方法是使用乘法逆：

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 

我就扔一个可能的替代方案，这里现在。

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]。 二进制搜索可用于快速查找哪个项目拥有获奖彩票，正如您已在this question中看到的那样。使用二分查找需要查找的是票号为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个单位的不良导致变化选择机会的差异。