Efficently可模拟滚动加权色子（或遍历加权图），与频繁的更新 [英] Efficently simulate rolling weighted dice (or traversing a weighted graph), with frequent updates

问题描述

我有一个加权，有向图是密集的约20,000节点。

I have a weighted, directed graph which is dense with around 20,000 nodes.

1. 由于图中的一个节点，我选择相邻节点随机与相关的相对权重的概率。
2. 在每一个选择后，我收到有关的选择是好还是坏的反馈，更新网络。例如，在一个糟糕的选择，我降低重量的所有边缘的指向所选择的节点。

1. Given an node in the graph, I choose an adjacent node randomly with a probability related to the relative weights.
2. After each choice, I receive feedback about whether the choice was good or bad, and update the network. For example, after a bad choice I decrease the weight of all edges pointing to the chosen node.

我学到<一个href="http://stackoverflow.com/questions/8745607/random-walks-in-directed-graphs-networks">yesterday有关别名方法以模拟轧制的加权模，这是一样的进行一个选择（每个节点是加权模，和两侧对应于其它节点）。一个卷是高效率的，但更新的权重不大;别名方法可能并不合适，因为我将更新更多的骰子比我将推出！

I learned yesterday about the alias method for simulating rolling a weighted die, which is the same as making one choice (each node is one weighted die, and the sides correspond to other nodes). One roll is highly efficient, but updating the weights is not; the alias method may not be appropriate because I will be updating more dice than I will be rolling!

我应该使用什么数据结构，它允许频繁的更新，什么相应的算法是最适合做的选择？

一些想法/注意事项：

• 我可以通过记录每一个权重调整减少更新，那么只有实际更新的节点/（一个前滚翻，即直接）必要时死亡。但是我仍然是precomputing别名数据一次的每个的卷。
• 相反，我可以简单地存储的图的是（使更新很便宜），并放弃别名方法。我会计算在飞行的相对权重每卷前（二进制搜索在这里工作）。
• 计算对飞相对权重的另外一个好处是，我可以分解出了全球重量为每个节点，以进一步减少更新。然后，一个不错的选择将导致只有2更新：传入边的权重和节点的全局重量
• 的加入的：也许有介于两者之间：一种方法来维持在一个数据结构局部相对权重（例如，树或别名方法），然后每卷过程中与上整体权重合并它们飞。

• I can decrease updates by recording each weight adjustment, and then only actually updating a node/die when necessary (i.e. directly before a roll). But I'd still be precomputing the alias data once for each roll.
• Instead, I could simply store the graph as is (so that updates are cheap) and forgo the alias method. I would calculate relative weights on the fly before each roll (binary search works here).
• An additional benefit of calculating relative weights on the fly is that I could factor out out the "global weight" for each node to further reduce updates. Then, a bad choice would result in only 2 updates: the incoming edge weight and the node's global weight.
• added: Maybe there is something in between: a way to maintain local relative weights in a data structure (e.g. tree or alias method) and then during each roll merge them with "global weights" on the fly.

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

The truth is that in practice I don't need to make choices very often (no more than once a minute), so I don't need the most efficient solution. But this is a fun side project and I'm interested in finding a theoretically optimal solution.

推荐答案

我认为你可以登录做到这一点（k）的复杂性，其中k为面的骰子的数量。

I think you can do it with log(k) complexity where k is number of faces in the dice.

有一个特定节点设P1，P2，...，pk的是相对概率。让P1 + P2，...，+ PK =第

for one particular node let p1, p2, ..., pk be the relative probabilities. Let p1+p2,...,+pk = p.

构造一个树状结构与这些相对概率为叶。每个非叶子节点的父是子女的相对概率的总和。要滚骰子之间划出0和P的随机值，并按照它通过树。当你想更新一个骰子面的相对概率，只是改变了相应的叶节点值，并通过该树传播起来。

Construct a tree structure with these relative probabilities as leaves. the parent of each non-leaf node is sum of relative probabilities of of their children. To "roll a dice" draw a random value between 0 and p, and follow it through the tree. When you want to update relative probability of a dice face, just change the corresponding leaf node value and propagate it up through the tree.

在这种方式，您可以选择一个随机值和一个随机数与log（K）找到对应的随机数叶所需的步骤，当你更新一个叶花数（k）的时间来更新树

In this way you can choose a random value with one random number with log(k) steps needed to find the leaf corresponding to the random number, and when you update one leaf it takes log(k) time to update the tree.

这是解决方案一个非常简单的描述，让我知道，如果你需要完整的描述。我相信它的工作原理，但不知道这是否是足够的效率对您的需要。

This is a very simple description of solution and let me know if you need complete description. I am sure it works, but not sure if this is efficient enough for you needs.

来概括，这个算法需要： 1.只有一个介于0和p的随机数 2 O（日志（k））的复杂性，掷骰子（即找到下一个节点），其中k为面的骰子数 3. O（日志（K）），以更新骰子一个给定的节点。如果有从原来的节点m的边缘，那么复杂度为O（日志（K1））+ O（日志（K2））... O（（公里）），其中K1，K2，...公里，相邻的连接节点。

to summarize, this algorithm needs: 1. Only one random number between 0 and p 2. O(log(k)) complexity to "roll the dice" (i.e. find the next node) where k is the number of faces in the dice 3. O(log(k)) to "update the dice" of a given node. If there are m edges from the original node, then complexity is O(log(k1))+O(log(k2))...O((km)) where k1, k2, ... km are connectivity of adjacent nodes.

====Tree Example====

如果有4个面的骰子和相对概率是1:50，2:80，3:20，4:70构建树如下：

If there are 4 faces to the dice and the relative probabilities are 1:50, 2:80, 3:20, 4:70 construct the tree as follows:

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

生成介于0和220随机数v如果是V = 100：向左走的路线（因为1​​00℃，130），然后采取正确的路线（因为1​​00> 80），并更新V = V-80 = 20.由于我们是在叶申报O / P，即2

Generate a random number v between 0 and 220. If it is v=100: take the left route (since 100<130) and then take the right route (since 100>80) and update v = v-80 = 20. Since we are at leaf declare o/p i.e. 2

如果V = 210：左和v = V-130 = 80，左V =-70 = 10，返回叶= 4

If v=210: left and v=v-130=80, left v=v-70=10, return leaf=4

如果4变为60，更改70到60，90到80和220到210。

If 4 changes to 60, change 70 to 60, 90 to 80 and 220 to 210.

==== Lazy update variation ====

每当权重改变不会立即更新树。相反，只是将其标记为肮脏的权重等到你需要prediction从这个特殊的节点。

Whenever weights are changed don't update the tree immediately. Instead, just mark it as a "dirty weight" wait until you need to make prediction from this particular node.

当你需要从一个特定节点做出prediction，如果一些权重是肮脏的，无论是。只有肮脏的节点或b更新树。更新整个树。如果脏权重的数目为t而总重量k的数目，如果吨*日志（k）的＆其中; K，则对应于肮脏的权重（T * O（K））仅更新树，否则更新整个树（O（K））。

When you need to make a prediction from a particular node and if some of the weights are dirty, either a. update the tree with only dirty nodes or b. update the whole tree. If the number of dirty weights is t and number of total weights k, if t*log(k) < k, then only update the tree corresponding to dirty weights ( t*O(k)) otherwise update the whole tree (O(k)).

这篇关于Efficently可模拟滚动加权色子（或遍历加权图），与频繁的更新的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！