不确定图上期望最短距离的计算
研究了不确定图上的最短距离问题，提出了期望最短距离的概念，证明了该问题不存在多项式时间的算法。为了解决该问题，使用了随机采样技术获得不确定图的一些可能世界，在每个可能世界上计算有穷的最短距离，最后计算出平均值作为期望最短距离的估计值。为提高计算效率，使用了过滤条件来减少采样过程中采样的边数从而加快随机采样。在此基础上，提出了一种基于对称变量的、无偏的随机采样近似算法，并证明了与直接随机采样方法相比，该方法在不增加时间开销的同时能减小采样方差。通过真实数据上的实验表明，提出的算法在时间开销和采样方差上均明显好于直接随机采样方法。
不确定图 最短距离 随机采样技术 计算方法
Li Mingpeng 李鸣鹏 Zou Zhaonian 邹兆年 Gao Hong 高宏 Zhao Zhengli 赵正理
School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001 哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001 School of Honors, Harbin Institute of Technology, Harbin 150001 哈尔滨工业大学英才学院 哈尔滨 150001
国内会议
合肥
中文
2208-2220
2012-10-01（万方平台首次上网日期，不代表论文的发表时间）