|
計(jì)算機(jī)、數(shù)學(xué)、運(yùn)籌學(xué)等領(lǐng)域的36個(gè)重要算法  重要算法 要學(xué)會(huì)
1. A *搜索算法 圖搜索算法,用于查找從給定初始節(jié)點(diǎn)到給定目標(biāo)節(jié)點(diǎn)的路徑。它采用啟發(fā)式估計(jì),通過(guò)估計(jì)通過(guò)該節(jié)點(diǎn)的最佳路徑對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行排名。它按照此啟發(fā)式估計(jì)的順序訪問(wèn)節(jié)點(diǎn)。因此,A *算法是最佳優(yōu)先搜索的示例。
2. 波束搜索 波束搜索是一種搜索算法,它是最佳優(yōu)先搜索的優(yōu)化。與最佳優(yōu)先搜索一樣,它使用啟發(fā)式函數(shù)來(lái)評(píng)估它檢查的每個(gè)節(jié)點(diǎn)的承諾。然而,波束搜索僅展開(kāi)每個(gè)深度處的前m個(gè)最有希望的節(jié)點(diǎn),其中m是固定數(shù)量,即波束寬度。 3. 二分搜索 通過(guò)排除每一步中的一半數(shù)據(jù)來(lái)查找線性陣列中特定值的技術(shù)。 4. 分支定界 用于尋找各種優(yōu)化問(wèn)題的最優(yōu)解的一般算法方法,尤其是在離散和組合優(yōu)化中。 5. Buchberger算法 在計(jì)算代數(shù)幾何和計(jì)算交換代數(shù)中,Buchberger算法是一種將多項(xiàng)式理想的給定發(fā)生器組轉(zhuǎn)換為Gr?bner基礎(chǔ)的方法,相對(duì)于某些單項(xiàng)式??梢詫⑵湟暈橛糜趩巫兞縢cd計(jì)算的歐幾里德算法和用于線性系統(tǒng)的高斯消元的概括。 6. 數(shù)據(jù)壓縮 數(shù)據(jù)壓縮或源編碼是使用比未編碼表示通過(guò)使用特定編碼方案使用的更少比特(或其他信息承載單元)來(lái)編碼信息的過(guò)程。 7. Diffie-Hellman密鑰交換 密碼協(xié)議允許彼此沒(méi)有先驗(yàn)知識(shí)的雙方在不安全的通信信道上共同建立共享密鑰。然后,該密鑰可用于使用對(duì)稱(chēng)密鑰密碼加密后續(xù)通信。 8. Dijkstra算法 解決具有非負(fù)邊權(quán)重的有向圖的單源最短路問(wèn)題。 9. 離散微分,公式f'(x)=(f(x + h) - f(xh))/ 2h。 10. 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃是一種用于減少表現(xiàn)出重疊子問(wèn)題和最佳子結(jié)構(gòu)的屬性的算法的運(yùn)行時(shí)間的方法,如下所述。 11. 歐幾里德算法 確定兩個(gè)整數(shù)的最大公約數(shù)(gcd)的算法。它是已知最古老的算法之一,因?yàn)樗霈F(xiàn)在公元前300年左右的Euclid元素中。該算法不需要將兩個(gè)整數(shù)分解。 12. 期望最大化算法(EM-Training) 在統(tǒng)計(jì)計(jì)算中,期望最大化(EM)算法是用于在概率模型中找到參數(shù)的最大似然估計(jì)的算法,其中模型取決于未觀察到的潛在變量。EM在執(zhí)行期望步驟和最大化步驟之間交替,期望步驟計(jì)算潛在變量的預(yù)期值,最大化步驟計(jì)算給定數(shù)據(jù)的參數(shù)的最大似然估計(jì)并將潛在變量設(shè)置為它們的期望。 13. 快速傅里葉變換(FFT) 高效算法計(jì)算離散傅里葉變換(DFT)及其逆。FFT對(duì)于各種應(yīng)用非常重要,從數(shù)字信號(hào)處理到求解偏微分方程,再到快速乘以大整數(shù)的算法。 14. 梯度下降 梯度下降是一種優(yōu)化算法,通過(guò)采用與當(dāng)前點(diǎn)處函數(shù)的梯度(或近似梯度)的負(fù)值成比例的步長(zhǎng)來(lái)逼近函數(shù)的局部最小值。相反,如果采用與梯度成比例的步長(zhǎng),則接近該函數(shù)的局部最大值; 然后將該過(guò)程稱(chēng)為梯度上升。 15. 哈希(Hashing) 用于匯總或概率識(shí)別數(shù)據(jù)的功能。通常,這意味著將數(shù)學(xué)公式應(yīng)用于數(shù)據(jù),從而生成可能或多或少獨(dú)特于該數(shù)據(jù)的字符串。該字符串比原始數(shù)據(jù)短得多,但可用于唯一標(biāo)識(shí)它。 16. 堆(堆排序) 在計(jì)算機(jī)科學(xué)中,堆是一種專(zhuān)門(mén)的基于樹(shù)的數(shù)據(jù)結(jié)構(gòu)。堆是許多應(yīng)用程序最喜歡的數(shù)據(jù)結(jié)構(gòu):堆排序,選擇算法(找到它們的最小值,最大值或最大值,中間線甚至是次線性時(shí)間中的任何第k個(gè)元素),圖算法。 17. Karatsuba乘法 對(duì)于需要乘以數(shù)千位數(shù)字的系統(tǒng),例如計(jì)算機(jī)代數(shù)系統(tǒng)和bignum庫(kù),長(zhǎng)乘法太慢。這些系統(tǒng)采用Karatsuba乘法,于1962年發(fā)現(xiàn)。 18. LLL算法 Lenstra-Lenstra-Lovasz晶格簡(jiǎn)化(LLL)算法是一種算法,在給定格子基礎(chǔ)作為輸入的情況下,輸出具有短的,幾乎正交的矢量的基礎(chǔ)。LLL算法在公鑰加密方案的密碼分析中發(fā)現(xiàn)了許多應(yīng)用:背包密碼系統(tǒng),具有特定設(shè)置的RSA等。 19. 最大流算法 網(wǎng)絡(luò)優(yōu)化的基本算法,最大流量問(wèn)題是通過(guò)最大流量網(wǎng)絡(luò)找到合法流量。有時(shí)它被定義為找到這種流的價(jià)值。最大流量問(wèn)題可以看作是更復(fù)雜的網(wǎng)絡(luò)流量問(wèn)題的特例。最大流量與Max-flow min-cut定理中的網(wǎng)絡(luò)中的切割有關(guān)。Ford-Fulkerson算法計(jì)算流網(wǎng)絡(luò)中的最大流量。 20. 合并排序 用于將列表(或只能按順序訪問(wèn)的任何其他數(shù)據(jù)結(jié)構(gòu),例如文件流)重新排列為指定順序的排序算法。 21. 牛頓方法 用于查找實(shí)值函數(shù)的零(或根)近似的高效算法。牛頓方法也是一種眾所周知的算法,用于在一個(gè)或多個(gè)維度中找到方程的根。它還可用于查找函數(shù)的局部最大值和局部最小值。 牛頓法的思想是非線性函數(shù)的二次函數(shù)局部近似。 22. Q-learning Q-learning是一種強(qiáng)化學(xué)習(xí)技術(shù),通過(guò)學(xué)習(xí)一個(gè)動(dòng)作 - 值函數(shù)來(lái)實(shí)現(xiàn),該函數(shù)給出了在給定狀態(tài)下執(zhí)行給定動(dòng)作并且之后遵循固定策略的預(yù)期效用。Q-learning的優(yōu)勢(shì)在于它能夠在不需要環(huán)境模型的情況下比較可用操作的預(yù)期效用。 23. 二次篩子 二次篩分算法(QS)是一種現(xiàn)代整數(shù)分解算法,并且在實(shí)踐中,已知第二種最快的方法(在數(shù)字篩分之后,NFS)。對(duì)于小數(shù)位數(shù)為110左右的整數(shù),它仍然是最快的,并且比數(shù)字字段篩網(wǎng)簡(jiǎn)單得多。 24. 隨機(jī)抽樣一致算法(RANdom SAmple Consensus) 它是一種根據(jù)包含“異常值”的一組觀測(cè)數(shù)據(jù)估計(jì)數(shù)學(xué)模型參數(shù)的算法。一個(gè)基本假設(shè)是數(shù)據(jù)由“內(nèi)部”組成,即可以通過(guò)一組模型參數(shù)解釋的數(shù)據(jù)點(diǎn),以及作為不適合模型的數(shù)據(jù)點(diǎn)的“異常值”。 25. 用于公鑰加密的 RSA算法 這是第一個(gè)已知適合簽名和加密的算法。RSA仍然廣泛用于電子商務(wù)協(xié)議中,并且被認(rèn)為在給定足夠長(zhǎng)的密鑰時(shí)是安全的。 26. Sch?nhage-Strassen算法 在數(shù)學(xué)中,Sch?nhage-Strassen算法是一種漸近快速的大整數(shù)乘法。運(yùn)行時(shí)間為O(N log(N)log(log(N)))。該算法在環(huán)中使用快速傅立葉變換。 27. 單純形算法 在數(shù)學(xué)優(yōu)化理論中,單純形算法是一種流行的線性規(guī)劃問(wèn)題數(shù)值解法。線性規(guī)劃問(wèn)題包括許多實(shí)變量上的線性不等式的集合和要最大化(或最小化)的固定線性函數(shù)。 28. 奇異值分解(SVD) 在線性代數(shù)中,SVD是矩形實(shí)數(shù)或復(fù)數(shù)矩陣的重要分解,在信號(hào)處理和統(tǒng)計(jì)中有多種應(yīng)用,例如,計(jì)算矩陣的偽逆(解決最小二乘問(wèn)題),求解超定線性系統(tǒng),矩陣近似,數(shù)值天氣預(yù)報(bào)。 29. 求解線性方程組 系統(tǒng)線性方程組屬于數(shù)學(xué)中最古老的問(wèn)題,它們有很多應(yīng)用,如數(shù)字信號(hào)處理,估計(jì),預(yù)測(cè),一般在線性規(guī)劃和數(shù)值分析中非線性問(wèn)題的近似。通過(guò)Gauss-Jordan消除或Cholesky分解給出了求解線性方程組的有效方法。 30. Strukturtensor 在模式識(shí)別中:計(jì)算每個(gè)像素的度量,該度量告訴您此像素是否位于同質(zhì)區(qū)域中,是否屬于邊緣,或者它是否是頂點(diǎn)。 31. 并查集(Union-find) 給定一組元素,將它們分成許多單獨(dú)的非重疊組通常很有用。不相交集數(shù)據(jù)結(jié)構(gòu)是跟蹤這種分區(qū)的數(shù)據(jù)結(jié)構(gòu)。聯(lián)合查找算法是一種對(duì)此類(lèi)數(shù)據(jù)結(jié)構(gòu)執(zhí)行兩個(gè)有用操作的算法:查找:確定特定元素所在的組。聯(lián)合:將兩個(gè)組合并或合并為一個(gè)組。 32. 維特比算法 用于查找最可能的隱藏狀態(tài)序列的動(dòng)態(tài)編程算法 - 稱(chēng)為維特比路徑 - 導(dǎo)致一系列觀察事件,特別是在隱馬爾可夫模型的背景下。 33. 內(nèi)點(diǎn)法 它是由John von Neumann發(fā)明的,他利用戈?duì)柕?span style="text-indent: 28px; font-family: arial, 宋體, sans-serif;">的線性齊次系統(tǒng)提出了這種新的求解線性規(guī)劃的方法。后被Narendra Karmarkar于1984年推廣應(yīng)用到線性規(guī)劃,即Karmarkar算法。內(nèi)點(diǎn)法不同于單純性從邊界上尋找最優(yōu)解,它是從內(nèi)點(diǎn)開(kāi)始尋找最優(yōu)解。目前是求解線性規(guī)劃的最有效算法。 34. 迪杰斯特拉(Dijkstra) 算法 迪杰斯特拉算法由荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾·迪杰斯特拉在1956年提出。迪杰斯特拉算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖的單源最短路徑問(wèn)題。 35. 割平面方法 1958年由美國(guó)學(xué)者高莫利(R.E.GoMory)提出的求解全整數(shù)規(guī)劃的一種比較簡(jiǎn)單的方法。其基本思想和分枝定界法大致相同,即先不考慮變量的取整約束,用單純形法求解相應(yīng)的線性規(guī)劃。 36. 高斯消元算法 是線性代數(shù)中的一個(gè)算法,可用來(lái)求解線性方程組,并可以求出矩陣的秩,以及求出可逆方陣的逆矩陣。其思想是化整為零,從零歸整(分步走),以簡(jiǎn)御繁。
|