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

Question

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

1. 给定图中的一个节点，我会根据相对权重随机选择一个相邻节点。
2. 每次选择后，我会收到有关选择是否好或坏的反馈，并更新网络。例如，在做出错误选择后，我会降低指向所选节点的所有边缘的权重。

我昨天了解到yesterday使用别名方法模拟掷骰子的方法，这与进行一次选择（每个节点都是一个加权骰子，每个面对应其他节点）相同。一次投掷非常高效，但更新权重则不然；由于我将更新的骰子数量多于投掷的骰子数量，因此可能不适用别名方法！ 我应该使用什么数据结构，可以允许频繁更新，并且哪种相应的算法最适合做出选择？

---

一些想法/笔记:

• 我可以通过记录每个权重调整来减少更新次数，然后仅在必要时（即直接在掷骰子之前）更新节点/骰子。但我仍然需要为每次投掷预先计算别名数据。
• 相反，我可以将图形存储为原样（以便更新廉价），并放弃别名方法。我将在每次掷骰子之前实时计算相对权重（这里使用二分查找）。
• 实时计算相对权重的另一个好处是，我可以将每个节点的“全局权重”因素分解出来，以进一步减少更新次数。然后，错误选择只会导致2次更新：传入边缘权重和节点的全局权重。
• 添加：也许有一种折中方案：维护数据结构中的本地相对权重（例如树或别名方法），然后在每次掷骰子时将它们与“全局权重”合并。

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

- jmilloy

---

你正在对权重进行哪些更新？是重新计算所有权重，只更新一个权重，还是更新一半的权重等等？ - templatetypedef

@templatetypedef "例如，在做出错误选择后，我会降低指向所选节点的所有边的权重。此外，当使用别名方法（或具有预计算概率的二进制搜索）时，更改一个出边权重意味着需要重新计算所有别名信息（或概率）。" - jmilloy

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。由于我们在叶子节点，声明输出即2

如果v=210：向左走，v=v-130=80，再向左走，v=v-70=10，返回叶子节点=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)）。

- ElKamina

---

@ElKamina 是的，我明白你的意思。如果我构建和维护树，则每次投掷可能会有数千次更新（因为我想要更新节点的“全局”权重，该权重被合并到每个树中）。最好在每次投掷之前从权重构建树，如果是这样，那么全局权重可以存储在一个中央位置，并且每次投掷只需更新一次，这是进一步的好处。也许有一个折中方案，在每次投掷之前维护单独的骰子权重树，然后有效地将其与第二个“全局”权重树合并。你有什么想法？ - jmilloy

@jmilloy 需要澄清。假设pij是从i到j的相对概率。当您更新j的权重时，是否对所有p * j执行相同的转换？（例如，对于所有i，pij = pij / 2？）如果是这种情况，我将尝试改进解决方案。否则，如果您执行非相同的转换，则最佳理论复杂度为O（n），因为您必须单独进行这些转换。在实践中，O（n）和O（nlog（n））之间没有太大区别。 - ElKamina

@ElKamina- 我担心的是，我没有看到这个更新时间是O(log n)，因为如果你存储了累积概率，那么你必须更新搜索树中所有在被改变的概率上面的值，导致一个朴素实现需要O(n log n)的工作量，而优化实现则需要O(n)的工作量。这对我来说不比别名方法好多少。我有什么遗漏吗？ - templatetypedef

请参考解决方案底部的示例，了解树是如何构建和更新的。 - ElKamina

我还添加了“懒惰更新”变体。在这个变体中，您的复杂度将是O(log(k))或O(k)，具体取决于是否需要更新。 - ElKamina