摘要
论述了随机行走算法的基本原理,理论分析了给定允许误差和置信概率下,随机行走算法的结束条件;讨论了随机行走算法在电路分析中的应用,并结合应用实例分析了算法的性能;讨论了算法的时间复杂性和影响算法执行时间的主要因素,重点分析了算法的并行特征,提出了采用并行计算技术提高算法性能的新方法,通过与串行算法的实验比较,表明了并行计算技术是提高随机行走算法执行速度的有效方法,比现有的方法适应性更广。
The random walk algorithm is introduced basically.The stop criterion of random walk algorithm is analyzed theoretically.Techniques of circuit analysis by random walk algorithm are discussed in details.Through an instance circuit,the performance of algorithm is studied carefully.And the complexity of random walk algorithm is analyzed.The factors related with algorithm runtime are discussed as well.As analyzing the parallel characteristics of random walk algorithm,a novel parallel computing technique is adopted to speedup the random walk algorithm.The experiment results indicate that parallel computing technique can improve random walk algorithm greatly.Moreover,the parallel computing techniques for random walk algorithm are much more adaptable than other methods.
出处
《计算机工程与应用》
CSCD
北大核心
2010年第18期199-201,243,共4页
Computer Engineering and Applications
基金
陕西省教育厅自然科学专项基金No.05JK293
the Special Foundation of Shaanxi Education Bureau of China under Grant No.05JK293
关键词
随机行走
电路分析
并行计算
random walk
circuit analysis
parallel computing
