我正在寻找一种具有与alias method相似的特征的加权随机选择算法,除了在选择项目后将其删除的地方。

例如,我有一个袋子可以生产:

  • 70%的时间是红色大理石。
  • 绿色大理石有10%的时间。
  • 和20%的时间是蓝色大理石。

  • 我给袋子取样,得到红色的大理石。现在红色被去除了,所以我想袋子现在会产生:
  • 33%的时间是绿色大理石。
  • 一种蓝色大理石,占66%的时间。

  • 我相信您可以预先计算每个可能的概率表的树,这样样本仍然是O(1)。是否有更聪明的算法来进行恒定时间加权选择(带去除)?

    最佳答案

    其实,我似乎误解了这个问题。我不知道别名方法,下面的答案也不是类似的算法。我将答案留在这里,因为它仍然可以提供信息。

    我不知道O(1)算法,但是在log(N)2搜索和log(N)更新中很容易做到。可以使用更具体的算法对此进行改进。

    将元素以概率作为值放在Fenwick tree中。同样,在更改元素时,请跟踪总累积概率。

    现在,我们可以做得比删除元素更好!我们可以任意更改项目的概率,但是将项目的概率设置为0等同于将其删除。然后可以在log(N)中查询第n个元素的累积概率。这在逻辑上扩展为对第一元素进行log(N)2二进制搜索,其累积概率大于p。

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

    我对上述内容进行了改进,因为使用Fenwick树很容易对累积概率大于或等于p的第一个元素执行log(N)搜索。我强烈建议您阅读this explanation of Fenwick trees

    简而言之,要查找元素,请像在其他任何树上一样,在Fenwick树上进行常规的二进制搜索,不同之处在于您保留了当前的累积总和(从0开始)。只要您在二分查找中选择右手子代,就将当前累积总和增加当前节点的值。然后,在将当前节点的值与累加总和进行比较时,我们需要在比较之前将当前节点的值与总和相加。

    关于algorithm - 带去除的O(1)加权随机选择算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/33624904/

    10-11 23:02
    查看更多