这是我前一段时间接受采访的问题,我找不到答案.
给定一些样本S1,S2,... Sn和它们的概率分布(或权重,无论它叫什么)P1,P2,... Pn,设计算法随机选择样本考虑其概率.我带来的解决方案如下:
构建累积的权重数组Ci,例如
C0 = 0; Ci = C [i-1] + Pi.
同时计算T = P1 + P2 + ... Pn.这需要O(n)时间
现在的实际问题是:假设我想要改变其中一个初始权重Pj.如何在O(n)时间内做到这一点？其他数据结构是可以接受的,但随机抽样算法不应该比O(logN)差.
我有一个加权图(实际上)最多50,000个顶点.给定一个顶点,我想根据所有相邻边的相对权重随机选择一个相邻的顶点.
我应该如何将此图存储在内存中,以便进行选择？什么是最好的算法？它可以像每个顶点的键值存储一样简单,但这可能不适合最有效的算法.我还需要能够更新网络.
请注意,我一次只想采取一个"步骤".
更正式:给定的加权,定向,和潜在的完全图,让W(A,B)是边缘A-> B的重量,并让W¯¯ 一个是从所有的边缘的总和一个.给定一个输入顶点v,我想随机选择一个顶点,其中选择顶点x的可能性是W(v,x)/W v
示例:
假设W(v,a) = 2,W(v,b) = 1,W(v,c) = 1.
给定输入v,函数应以概率0.5和b或c以概率0.25 返回a.