通过频繁更新,可以模拟滚动加权骰子(或遍历加权图)

Question

我有一个加权的有向图,它有大约20,000个节点.

1. 给定图中的节点,我随机选择一个相邻节点,其概率与相对权重相关.
2. 在每次选择之后,我会收到有关选择是好还是坏的反馈,并更新网络.例如,在选择错误之后,我减少了指向所选节点的所有边的权重.

我昨天了解了模拟滚动加权骰子的别名方法,这与做出一个选择相同(每个节点是一个加权骰子,而侧面对应于其他节点).一卷是高效的,但更新权重不是; 别名方法可能不合适,因为我将更新骰子而不是我将要滚动!

我应该使用哪种数据结构,允许频繁更新,以及哪种相应的算法最适合做出选择？

---

一些想法/说明:

• 我可以通过记录每个权重调整来减少更新,然后仅在必要时(即直接在滚动之前)实际更新节点/模具.但是我仍然会为每个卷预先计算一次别名数据.
• 相反,我可以简单地存储图形(以便更新便宜)并放弃别名方法.我会在每次滚动之前动态计算相对权重(二进制搜索在这里工作).
• 动态计算相对权重的另一个好处是,我可以将每个节点的"全局权重"分解出来,以进一步减少更新.然后,错误的选择将导致仅2个更新:传入边缘权重和节点的全局权重.
• 补充:可能之间有一些东西:一种在数据结构中保持局部相对权重的方法(例如树或别名方法),然后在每次滚动时将它们与动态"全局权重"合并.

事实是,在实践中我不需要经常做出选择(每分钟不超过一次),所以我不需要最有效的解决方案.但这是一个有趣的副项目,我有兴趣找到一个理论上最优的解决方案.

Answer 1

我认为你可以用 log(k) 复杂度来做到这一点，其中 k 是骰子中的面数。

对于一个特定节点，令 p1, p2, ..., pk 为相对概率。令 p1+p2,...,+pk = p。

用这些相对概率作为叶子构造一个树结构。每个非叶节点的父节点是其子节点的相对概率之和。要“掷骰子”，请在 0 和 p 之间绘制一个随机值，并按照它遍历树。当您想要更新骰子面的相对概率时，只需更改相应的叶节点值并将其通过树向上传播即可。

通过这种方式，您可以选择一个随机值，其中一个随机数需要 log(k) 步来找到与该随机数对应的叶子，并且当您更新一个叶子时，需要 log(k) 时间来更新树。

这是解决方案的非常简单的描述，如果您需要完整的描述，请告诉我。我确信它有效，但不确定这是否足够有效满足您的需求。

总而言之，该算法需要： 1. 0 和 p 之间只有一个随机数 2. “掷骰子”（即找到下一个节点）的复杂度为 O(log(k))，其中 k 是骰子中的面数3. O(log(k)) 来“更新给定节点的骰子”。如果原始节点有 m 条边，则复杂度为 O(log(k1))+O(log(k2))...O((km))，其中 k1、k2、... km 是相邻节点的连通性节点。

====Tree Example====

如果骰子有 4 个面，相对概率为 1:50、2:80、3:20、4:70，则按如下方式构造树：

          220
       /       \
    130         90
   /   \      /    \
 50    80    20    70
  |    |     |      |
  1    2     3      4

生成一个 0 到 220 之间的随机数 v。如果 v=100：走左边的路线（因为 100<130），然后走右边的路线（因为 100>80）并更新 v = v-80 = 20。我们在 leaf 声明 o/p ie 2

如果v=210：左且v=v-130=80，左v=v-70=10，返回leaf=4

如果4变为60，则70变为60，90变为80，220变为210。

==== Lazy update variation ====

每当权重发生变化时，不要立即更新树。相反，只需将其标记为“脏权重”，直到您需要从该特定节点进行预测为止。

当您需要从特定节点进行预测并且某些权重是脏的时，要么 仅使用脏节点更新树或 b．更新整个树。如果脏权重的数量为t，总权重的数量为k，如果t*log(k) < k，则只更新脏权重对应的树( t*O(k))，否则更新整个树(O( k))。