O（1）带去除加权随机选择的算法

2018-06-10 05:25:54

我正在寻找一种与别名方法具有相似特征的加权随机选择算法，除非在选择项目后将其删除。

例如，我有一个袋子可以产生：

70％的时间是红色大理石。

10％的时间是绿色大理石。

20％的时间是蓝色的大理石。

我抽样袋子，并得到一个红色的大理石。红色现在被删除，所以我想这个包现在会产生：

33％的时间是绿色大理石。

蓝色大理石66％的时间。

我相信你可以预先计算每个可能概率表的一棵树，这样样本仍然是O(1) 。是否有更加聪明的算法用于去除恒定时间加权选择？

其实，我似乎误解了这个问题。我不知道别名方法，下面的答案不是一个类似的算法。我会在这里留下我的答案，因为它仍然是内容丰富的。

我不知道O（1）算法，但在log（N）2搜索和log（N）更新中很容易做到。这可以通过更具体的算法来改进。

将你的元素放在Fenwick树中，并将它们的概率作为它们的值。另外，当变化的元素跟踪总累积概率。

现在，我们可以做得更好，而不仅仅是删除元素！我们可以任意改变项目的概率，但是将项目的概率设置为0相当于将其删除。然后可以在log（N）中查询第n个元素的累积概率。这在逻辑上延伸到第一个元素的log（N）2二元搜索，累积概率大于p。

现在，要进行加权随机选择，我们生成一个介于0和P之间的数字p，其中P是总累积概率。然后我们进行上述二元搜索以找到并选择累积概率大于p的第一个元素。

我对上述内容进行了改进，因为使用Fenwick树可以很容易地对累积概率大于或等于p的第一个元素进行log（N）搜索。我强烈建议阅读Fenwick树的解释。

简单地说，要找到该元素，就像在任何其他树上一样，在Fenwick树上执行常规二分搜索，但保留当前累计和（从0开始）。无论何时在二分搜索中选择右侧子节点，都会将当前累计和与当前节点的值相加。然后，比较当前节点的值和我们正在寻找的累计总和，在比较之前将当前节点的值添加到总和中。

链接地址: http://www.djcxy.com/p/30313.html