《算法基礎：打開算法之門》一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“近似最優”就是近似算法輸出的解的量化測度值介于最優解的量化測度值的一個已知因子之内。隻要指定了目标因子，我們就可以說一個近似算法的正确解是任意一個量化測度值在最優解目标因子之内的解決方案。