我有一个加权的有向图,它有大约20,000个节点.
- 给定图中的节点,我随机选择一个相邻节点,其概率与相对权重相关.
- 在每次选择之后,我会收到有关选择是好还是坏的反馈,并更新网络.例如,在选择错误之后,我减少了指向所选节点的所有边的权重.
我昨天了解了模拟滚动加权骰子的别名方法,这与做出一个选择相同(每个节点是一个加权骰子,而侧面对应于其他节点).一卷是高效的,但更新权重不是; 别名方法可能不合适,因为我将更新骰子而不是我将要滚动!
我应该使用哪种数据结构,允许频繁更新,以及哪种相应的算法最适合做出选择？
一些想法/说明:
- 我可以通过记录每个权重调整来减少更新,然后仅在必要时(即直接在滚动之前)实际更新节点/模具.但是我仍然会为每个卷预先计算一次别名数据.
- 相反,我可以简单地存储图形(以便更新便宜)并放弃别名方法.我会在每次滚动之前动态计算相对权重(二进制搜索在这里工作).
- 动态计算相对权重的另一个好处是,我可以将每个节点的"全局权重"分解出来,以进一步减少更新.然后,错误的选择将导致仅2个更新:传入边缘权重和节点的全局权重.
- 补充:可能之间有一些东西:一种在数据结构中保持局部相对权重的方法(例如树或别名方法),然后在每次滚动时将它们与动态"全局权重"合并.
事实是,在实践中我不需要经常做出选择(每分钟不超过一次),所以我不需要最有效的解决方案.但这是一个有趣的副项目,我有兴趣找到一个理论上最优的解决方案.