第10章 最后的招数
第11章 尾声
第10章 最后的招数
本章不同于前面的章节,前面所讲述的都是用于解决常见问题的算法,而这一章的问题有所不同,需要一些特别的算法。这些算法的知识能够帮助设计者去选择如何使用它们去解决那些很不寻常的问题。
另一个不同在于,在前面的内容中,随机和概率是用于分析算法的一般行为,而这里随机则是算法本质的部分。实际上,这里我们将要介绍的概率算法是确定性算法一个很有趣的替代方案。同样的输入同样的算法,运行两次的结果可能是不一样的,有时候我们会容忍错误的发生,也会接受算法最终告知问题无法解决。
一个重要假设是,算法可以利用随机位序列。其实随机性很难定义,虽然我们已经有几个用于检测随机性的测试,不过实际上很难生成满足这些测试的比特串。
另类算法
本书前面所提到的所有算法都是在一个顺序的确定性的计算平台上,为问题的单个实例计算出正确的结果。而现在已经出现的不少有趣研究却是摒弃以下四大设定的算法。
·结果必须是正确的。
·每次只解决一个实例。
·顺序的。
·确定性的。
抛开这些设定使我们能够创造出各种各样不同类型的算法。