文献类型：期刊文章

作　　者：李鸣鹏[1] 邹兆年[1] 高宏[1] 赵正理[2]

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 [2]哈尔滨工业大学英才学院,哈尔滨150001

出　　处：《计算机研究与发展》

基　　金：国家"九七三"重点基础研究发展计划基金项目(2012CB316200);国家自然科学基金项目(61173023;61190115;61033015);中央高校基本科研业务费专项基金项目(HIT.NSRIF.201180)

年　　份：2012

卷　　号：49

期　　号：10

起止页码：2208-2220

语　　种：中文

收录情况：AJ、BDHX、BDHX2011、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

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

关 键 词：不确定图  期望最短距离  随机采样 对称变量采样  采样方差  

分 类 号：TP301.6]