论文部分内容阅读
研究了不确定图上的最短距离问题，提出了期望最短距离的概念，证明了该问题不存在多项式时间的算法．为了解决该问题，使用了随机采样技术获得不确定图的一些可能世界，在每个可能世界上计算有穷的最短距离，最后计算出平均值作为期望最短距离的估计值．为提高计算效率，使用了过滤条件来减少采样过程中采样的边数从而加快随机采样．在此基础上，提出了一种基于对称变量的、无偏的随机采样近似算法，并证明了与直接随机采样方法相比，该方法在不增加时间开销的同时能减小采样方差．通过真实数据上的实验表明，提出的算法在时间开销和采样方差上均明显