自計(jì)算機(jī)科學(xué)誕生之日起——這個(gè)領(lǐng)域以其有條不紊地解決問(wèn)題的方法而聞名——隨機(jī)性就發(fā)揮了重要作用。在世界上第一臺(tái)通用電子計(jì)算機(jī)上運(yùn)行的第一個(gè)程序使用隨機(jī)性來(lái)模擬核過(guò)程。此后，類(lèi)似的方法被用于天體物理學(xué)、氣候科學(xué)和經(jīng)濟(jì)學(xué)。在所有這些情況下，在算法的某些步驟插入隨機(jī)數(shù)有助于研究人員解釋復(fù)雜過(guò)程可以發(fā)揮作用的多種方式的不確定性。
但是，將隨機(jī)性添加到算法中也可以幫助你計(jì)算出明確判斷真假問(wèn)題的正確答案。「你只要說(shuō)『好吧，讓我放棄，讓我不要嘗試，讓我隨機(jī)挑選一些東西。』」滑鐵盧大學(xué)的計(jì)算機(jī)科學(xué)家 Eric Blais 說(shuō)，「對(duì)于太多的問(wèn)題，這最終成為一種成功的方法。」
假設(shè)你要確定給定數(shù)字是質(zhì)數(shù)（只能被 1 和它本身整除）還是合數(shù)（也可以被其他整數(shù)整除）。你可以簡(jiǎn)單地嘗試將其除以所有可能的因數(shù)，但對(duì)于大數(shù)，這種「蠻力」方法和其他因式分解算法速度極慢。如果結(jié)果是合數(shù)，分解算法會(huì)告訴你它的除數(shù)的值——比你要求的更多的信息。如果你只關(guān)心數(shù)字的「素性」，有沒(méi)有更高效的算法？
如果你使用隨機(jī)性的話(huà)。基本思想可以追溯到 17 世紀(jì)法國(guó)數(shù)學(xué)家 Pierre de Fermat （費(fèi)馬）的一個(gè)結(jié)果，即他的「小定理」。Fermat 考慮了兩個(gè)整數(shù)——稱(chēng)它們?yōu)?N 和 x。他證明了如果 N 是質(zhì)數(shù)，那么 x^N ? x 總是 N 的倍數(shù)，而不管 x 的值如何。等價(jià)地，如果 x^N ? x 不是 N 的倍數(shù)，則 N 不可能是質(zhì)數(shù)。但逆命題并不總是正確的：如果 x^N ? x 是 N 的倍數(shù)，則 N 并不總是質(zhì)數(shù)。
要將費(fèi)馬小定理變成素?cái)?shù)檢驗(yàn)，只需取你感興趣的 N，隨機(jī)選擇 x，然后將這兩個(gè)數(shù)代入 x^N ? x。如果結(jié)果不是 N 的倍數(shù)，那么你就完了：你知道 N 肯定是合數(shù)。如果結(jié)果是 N 的倍數(shù)，那么 N 可能是素?cái)?shù)。現(xiàn)在選擇另一個(gè)隨機(jī) x 并重試。在大多數(shù)情況下，經(jīng)過(guò)幾十次嘗試，你幾乎可以肯定地得出 N 是質(zhì)數(shù)的結(jié)論。「你這樣做的次數(shù)很少。」Blais 說(shuō)，「不知何故，現(xiàn)在你出錯(cuò)的概率小于從現(xiàn)在到你看到答案時(shí)小行星撞擊地球的概率。」
https://www.sciencedirect.com/science/article/pii/0022314X80900840
使用隨機(jī)算法（基于對(duì)費(fèi)馬小定理的改進(jìn)）的第一個(gè)素?cái)?shù)測(cè)試開(kāi)創(chuàng)了一個(gè)新時(shí)代。事實(shí)證明，與非隨機(jī)或確定性算法相比，用隨機(jī)算法解決一個(gè)又一個(gè)問(wèn)題要容易得多。關(guān)鍵是將每個(gè)問(wèn)題重新定義為可以在給定某個(gè)數(shù)字 x 的適當(dāng)值的情況下快速解決的問(wèn)題，然后證明幾乎任何 x 都可以解決。即使研究人員不知道如何確定任何特定選擇是否是一個(gè)好的解決方案，該解決方案仍然有效。數(shù)學(xué)家開(kāi)玩笑說(shuō)，這個(gè)不尋常的挑戰(zhàn)就像大海撈針。
但這些成功讓研究人員想知道為什么隨機(jī)性應(yīng)該有助于解決諸如素?cái)?shù)測(cè)試之類(lèi)的問(wèn)題，這些問(wèn)題都是關(guān)于尋找隱藏的、非隨機(jī)的模式。「這有點(diǎn)自相矛盾。」牛津大學(xué)計(jì)算機(jī)科學(xué)家 Rahul Santhanam 說(shuō)， 「純粹的隨機(jī)性正在幫助你掌握解決問(wèn)題的結(jié)構(gòu)。」
1994 年，計(jì)算機(jī)科學(xué)家 Noam Nisan 和 Avi Wigderson 通過(guò)證明隨機(jī)性雖然有用但可能并非必需，幫助解決了這一困惑。他們證明了以下兩件事之一必須是正確的：要么所有可以使用隨機(jī)性有效解決的問(wèn)題也有快速確定性算法，要么許多眾所周知的難題實(shí)際上很容易。計(jì)算機(jī)科學(xué)家認(rèn)為第二種可能性極小。
https://www.sciencedirect.com/science/article/pii/S0022000005800431
事實(shí)上，計(jì)算機(jī)科學(xué)家經(jīng)常發(fā)現(xiàn)通過(guò)從隨機(jī)版本開(kāi)始然后「去隨機(jī)化」它來(lái)開(kāi)發(fā)確定性算法更容易。布朗大學(xué)的計(jì)算機(jī)科學(xué)家 Eli Upfal 說(shuō)：「一旦我有了它，我突然看到了一種非常明顯的方法來(lái)讓它具有確定性……但如果我不以隨機(jī)方式將其視為概率問(wèn)題，我可能不會(huì)想到它。」
在 Nisan 和 Wigderson 具有里程碑意義的證明之后將近 30 年，隨機(jī)算法仍然一如既往地流行，因?yàn)槿ルS機(jī)化可能很棘手，而確定性算法通常僅在原則上有效。直到 2002 年，三位研究人員才找到一種去隨機(jī)化素性測(cè)試的方法，而且在實(shí)踐中，他們的算法比最好的隨機(jī)算法慢得多。對(duì)于其他問(wèn)題，甚至不知道從哪里開(kāi)始——最著名的算法有一個(gè)雞和蛋的問(wèn)題，你只能通過(guò)隨機(jī)性來(lái)逃避。
https://annals.math.princeton.edu/2004/160-2/p12
圖論最近的突破就是這種情況。2022 年，三位計(jì)算機(jī)科學(xué)家開(kāi)發(fā)了一種快速算法，用于通過(guò)圖形（由線(xiàn)段連接的節(jié)點(diǎn)網(wǎng)絡(luò)）找到最短路徑，即使某些線(xiàn)段從總路徑長(zhǎng)度中減去而不是添加，該算法也能正常工作。他們的算法涉及通過(guò)刪除某些段將圖形轉(zhuǎn)換為更簡(jiǎn)單的圖形，解決簡(jiǎn)化圖形的問(wèn)題，然后考慮刪除的段。他們可以證明，如果沒(méi)有最短路徑經(jīng)過(guò)太多已刪除的段，算法將運(yùn)行得很快——否則，最后一步將花費(fèi)太長(zhǎng)時(shí)間。
https://arxiv.org/abs/2203.03456#
但是如何決定首先刪除哪些段呢？確定性地找到理想的細(xì)分市場(chǎng)不僅很難——這是不可能的。該集合取決于最短的路徑，這正是三位研究人員試圖解決的問(wèn)題。但即使他們找不到要?jiǎng)h除的最佳片段集，他們也可以證明大多數(shù)隨機(jī)選擇都很好，這足以打破自我參照循環(huán)。在極少數(shù)情況下，算法做出了一個(gè)不幸的選擇并在最后一步陷入困境，他們可以停止并再次運(yùn)行它。
「隨機(jī)性基本上是一種在不知道最佳解決方案的情況下確保最佳解決方案為真的方法，」新算法的作者之一 Aaron Bernstein 說(shuō)。
隨機(jī)性在計(jì)算機(jī)科學(xué)中發(fā)現(xiàn)了無(wú)數(shù)其他用途，從密碼學(xué)到博弈論再到機(jī)器學(xué)習(xí)。很有可能，它會(huì)留在這里。
https://www.quantamagazine.org/how-randomness-improves-algorithms-20230403/
文章來(lái)源：ScienceAI
IEEE Spectrum
《科技縱覽》
官方微信公眾平臺(tái)
