| 随机算法的一般性原理 |
| |
| 引用本文： | 贺红,马绍汉.随机算法的一般性原理[J].计算机科学,2002,29(1):90-92. |
| |
| 作者姓名： | 贺红 马绍汉 |
| |
| 作者单位： | 山东大学计算机科学系,济南,250100 |
| |
| 基金项目： | 国家自然科学基金(69873027) |
| |
| 摘 要： | 最近十几年来,国际上对随机算法(randomized algo-rithm)的研究有了巨大进展。在此期间,随机算法从一个计数理论的工具发展到今天在许多类型的算法中都得到了广泛应用,显示了随机算法本身强大的生命力。所谓随机算法,就是在执行过程中要做出随机选择的算法。随机算法有两种不同类型:其一是总能给出正确的解,两次运行之间唯一的区别是运行时间不同,我们把这种随机算法叫做Las Vegas算法;其二是有时会产生不正确解的算法,然而我们能够界定产生不正确解的概率,我们把这种随机算法叫做Monte Carlo算法。这两种算法哪种更好些,要看它应用于哪类问题,Las Vegas算法可以看成是Monte Carlo算法当错误的概率为零的情况。
|
| 关 键 词： | 随机算法 一般性原理 LasVegas算法 MonteCarlo算法 NP问题 计算机 |
The General Principles of Randomized Algorithms |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
