| 不确定图上期望最短距离的计算 |
| |
| 引用本文： | 李鸣鹏,邹兆年,高宏,赵正理.不确定图上期望最短距离的计算[J].计算机研究与发展,2012,49(10):2208-2220. |
| |
| 作者姓名： | 李鸣鹏 邹兆年 高宏 赵正理 |
| |
| 作者单位： | 1. 哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001
2. 哈尔滨工业大学英才学院 哈尔滨 150001 |
| |
| 基金项目： | 国家"九七三"重点基础研究发展计划基金项目，国家自然科学基金项目，中央高校基本科研业务费专项基金项目 |
| |
| 摘 要： | 研究了不确定图上的最短距离问题,提出了期望最短距离的概念,证明了该问题不存在多项式时间的算法.为了解决该问题,使用了随机采样技术获得不确定图的一些可能世界,在每个可能世界上计算有穷的最短距离,最后计算出平均值作为期望最短距离的估计值.为提高计算效率,使用了过滤条件来减少采样过程中采样的边数从而加快随机采样.在此基础上,提出了一种基于对称变量的、无偏的随机采样近似算法,并证明了与直接随机采样方法相比,该方法在不增加时间开销的同时能减小采样方差.通过真实数据上的实验表明,提出的算法在时间开销和采样方差上均明显好于直接随机采样方法.
|
| 关 键 词： | 不确定图 期望最短距离 随机采样 对称变量采样 采样方差 |
Computing Expected Shortest Distance in Uncertain Graphs |
| |
| Li Mingpeng
,
Zou Zhaonian
,
Gao Hong
,
Zhao Zhengli.Computing Expected Shortest Distance in Uncertain Graphs[J].Journal of Computer Research and Development,2012,49(10):2208-2220. |
| |
| Authors: | Li Mingpeng Zou Zhaonian Gao Hong Zhao Zhengli |
| |
| Affiliation: | 1 ( School of Computer Science and Technology , Harbin Institute of Technology , Harbin150001 ) 2 ( School of Honors , Harbin Institute of Technology , Harbin150001 ) |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
