《算法基础：打开算法之门》一1.1 正确性

本节书摘来自华章出版社《算法基础：打开算法之门》一书中的第1章，第1.1节，作者 ［美］托马斯 h 科尔曼（thomas h cormen），更多章节内容可以访问云栖社区“华章计算机”公众号查看

产生问题的一个正确解决方案意味着什么呢？我们通常会精确地定义一个正确的解决方案涉及的内容。例如，为了寻找出最佳旅行路线，你的gps会产生一个正确的解决方案。该方案可能是从你所在位置到目的地的所有可能路线中最快的路线，也可能是具有最短距离的路线，或者是能使你最快到达目的地同时也能免交过路费的路线。当然，你的gps确定路线时所使用的信息可能不完全匹配实际情况。除非你的gps能够获取实时路况信息，否则它可能假定穿过一条道路的时间等于道路的长度除以道路的限定时速。

然而，如果道路拥挤，当你在寻找一条最快路线时，gps可能不能给你提供好的建议。然而，即使算法的输入是不正确的，我们仍然可以说gps所提供的路线选择算法是正确的，即对于给定的输入，该路线选择算法输出最快的路线。然而，对于某些问题，可能难以判定甚至不可能判定一个算法是否产生了正确的输出。以光学字符识别为例。这个11×6像素的图像表示5还是s呢？

一些人可能会说它是5，而其他人可能说它是s，因此我们也不能判定计算机的输出是否正确。在本书中，我们将只关注有确定解的计算机算法。

然而，有些时候，我们可以接受可能会产生错误解的算法，只要产生错误解的频率可以被控制。加密算法就是一个范例。最常用的rsa加密系统依赖于确定大数是否为素数，这里的大数指相当大的数，如数百位那么长。如果你曾经写过一个计算机程序，你可能能够写出一个判定数n是否是素数的程序。它将测试从2到n-1的所有候选除数，如果这些候选除数中有一个除数确实能被n整除，那么n是合数。如果2和n-1之间的任何数均不能被n整除，那么n是素数。但是如果n是数百位长的数，那就会产生大量的候选除数，即使是一个运行相当快的计算机进行相应的检查操作也会超过合理的运行时间。当然，可以进行一些优化操作，例如当检测出2不是n的除数后，在候选除数中可以去除所有的偶数，或者循环到候选除数等于〖kf(]n〖kf)]时终止由于若d>〖kf(]n〖kf)],且n mod d=0,那么〖sx(]nd〖sx)]<〖kf(]n〖kf)],n mod (n/d)=0；这说明若n能整除一个大于〖kf(]n〖kf)]的数，则n也必定能够整除一个小于〖kf(]n〖kf)]的数。如果n是一个数百位的数，则尽管〖kf(]n〖kf)]的位数是数百位的一半，但是它仍然是一个非常大的数。好消息是，我们知道一个可以高效测试一个数是否是素数的算法。坏消息是，该算法可能会得出错误的结论。特别是，当该算法得出n是合数时，则n一定是一个合数，但是若该算法得出n是一个素数，n实际上也可能是一个合数。但是坏消息也不全不好，我们可以对其加以控制，使得错误率降到足够低，例如每执行250次才会出现一次错误。那是相当罕见的了——大约每千万亿次才出现一次错误——在rsa中应用这个方法来判定一个数是否是素数对于大多数人而言是安全的。对于另一类算法——近似算法，正确性也是一个需要着重考量的问题。近似算法适合于优化问题，即根据一些量化测度来寻找最优解的问题。例如gps中寻找最快路径问题就是一个优化问题，它的量化测度是旅程中花费的时间。对某些问题，我们找不到任何可以在合理的时间内求解出最优解的算法，但是我们能够找到一个近似算法，它可以在合理的时间内求解得出一个近似的最优解。3“近似最优”就是近似算法输出的解的量化测度值介于最优解的量化测度值的一个已知因子之内。只要指定了目标因子，我们就可以说一个近似算法的正确解是任意一个量化测度值在最优解目标因子之内的解决方案。