高效模拟滚动加权骰子（或遍历加权图），并进行频繁更新

  • Z时代
  • 2024-01-10
  • 分类：问答

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

  1. 给定图中的一个节点，我以与相对权重有关的概率随机选择一个相邻节点。

  2. 每次选择之后，我都会收到有关选择是好是坏的反馈，并更新网络。例如，在做出错误选择之后，我减小了指向所选节点的 所有边缘 的权重。

昨天我了解了用于模拟滚动加权模具的别名方法，该方法与做出选择相同（每个节点是一个加权模具，而侧面对应于其他节点）。一卷效率很高，但更新权重却不高。别名方法可能不合适，因为我将更新的骰子比滚动的要多！

一些想法/笔记：

  • 我可以通过记录每个权重调整来减少更新，然后仅在必要时（即，在滚动之前）实际更新节点/模具。但是我仍然会为 每一 卷预先计算一次别名数据。

  • 相反，我可以简单地按原样存储图形（这样更新就便宜了），并放弃使用alias方法。我会在每次掷骰之前即时计算相对权重（此处二进制搜索有效）。

  • 快速计算相对权重的另一个好处是，我可以排除每个节点的“全局权重”，以进一步减少更新。然后，错误的选择将仅导致2个更新：传入边缘权重和节点的全局权重。

  • 添加 ：也许介于两者之间：一种在数据结构中维护局部相对权重的方法（例如，树或别名方法），然后在每次滚动期间将它们与“全局权重”动态合并。

事实是，在实践中，我不需要经常做出选择（每分钟不超过一次），因此我 不需要

最有效的解决方案。但这是一个有趣的附带项目，我对寻找理论上最佳的解决方案感兴趣。

回答：

我认为您可以使用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。我们在叶子声明o / p即2

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

如果4更改为60，则将70更改为60，将90更改为80，然后将220更改为210。

==== Lazy update variation ====

无论何时更改权重，都不要立即更新树。相反，只需将其标记为“脏重”，直到需要从该特定节点进行预测。

当您需要从特定节点进行预测并且某些权重不合理时，请选择a。仅使用脏节点或b更新树。更新整个树。如果脏权重数为t且总权重数为k，则如果t *

log（k）<k，则仅更新对应于脏权重（t * O（k））的树，否则更新整棵树（O（ k））。

以上是 高效模拟滚动加权骰子（或遍历加权图），并进行频繁更新 的全部内容， 来源链接： utcz.com/qa/415425.html

回到顶部