編程世界中的18個重要的算法

2020-12-01 網易

核心提示:下面的這些,有的我們經常在用,有的基本不用。有的很常見,有的很偏。不過了解一下也是好事。

下面是一些比較重要的算法,原文羅列了32個,但我覺得有很多是數論裡的,和計算機的不相干,所以沒有選取。下面的這些,有的我們經常在用,有的基本不用。有的很常見,有的很偏。不過了解一下也是好事。也歡迎你留下你覺得有意義的算法。(註:本篇文章並非翻譯,其中的算法描述大部份摘自Wikipedia,因為維基百科描述的很專業了)

A*搜尋算法

俗稱A星算法。這是一種在圖形平面上,有多個節點的路徑,求出最低通過成本的算法。常用於遊戲中的NPC的移動計算,或線上遊戲的BOT的移動計算上。該算法像Dijkstra算法一樣,可以找到一條最短路徑;也像BFS一樣,進行啟發式的搜索。

Beam Search

束搜索(beam search)方法是解決優化問題的一種啟發式方法,它是在分枝定界方法基礎上發展起來的,它使用啟發式方法估計k個最好的路徑,僅從這k個路徑出發向下搜索,即每一層只有滿意的結點會被保留,其它的結點則被永久拋棄,從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法,他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯,並快速地獲得一個解。

二分取中查找算法

一種在有序數組中查找某一特定元素的搜索算法。搜素過程從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜素過程結束;如果某一特定元素大於或者小於中間元素,則在數組大於或小於中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。這種搜索算法每一次比較都使搜索範圍縮小一半。

Branch and bound

分支定界(branch and bound)算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同,分支定界算法採用廣度優先或最小耗費優先的方法搜索解空間樹,並且,在分支定界算法中,每一個活結點只有一次機會成為擴展結點。

數據壓縮

數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度,達到增大數據密度,最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網絡帶寬的擴展。

Diffie–Hellman密鑰協商

Diffie–Hellman key exchange,簡稱「D–H」,是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。

Dijkstra’s 算法

迪科斯徹算法(Dijkstra)是由荷蘭計算機科學家艾茲格·迪科斯徹(Edsger Wybe Dijkstra)發明的。算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說,如果圖中的頂點表示城市,而邊上的權重表示著城市間開車行經的距離,迪科斯徹算法可以用來找到兩個城市之間的最短路徑。

動態規劃

動態規劃是一種在數學和計算機科學中使用的,用於求解包含重疊子問題的最優化問題的方法。其基本思想是,將原問題分解為相似的子問題,在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種算法的基礎,被廣泛應用於計算機科學和工程領域。比較著名的應用實例有:求解最短路徑問題,背包問題,項目管理,網絡流優化等。這裡也有一篇文章說得比較詳細。

歐幾裡得算法

在數學中,輾轉相除法,又稱歐幾裡得算法,是求最大公約數的算法。輾轉相除法首次出現於歐幾裡得的《幾何原本》(第VII卷,命題i和ii)中,而在中國則可以追溯至東漢出現的《九章算術》。

最大期望(EM)算法

在統計計算中,最大期望(EM)算法是在概率(probabilistic)模型中尋找參數最大似然估計的算法,其中概率模型依賴於無法觀測的隱藏變量(Latent Variable)。最大期望經常用在機器學習和計算機視覺的數據聚類(Data Clustering)領域。最大期望算法經過兩個步驟交替進行計算,第一步是計算期望(E),利用對隱藏變量的現有估計值,計算其最大似然估計值;第二步是最大化(M),最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中,這個過程不斷交替進行。

快速傅立葉變換(FFT)

快速傅立葉變換(Fast Fourier Transform,FFT),是離散傅立葉變換的快速算法,也可用於計算離散傅立葉變換的逆變換。快速傅立葉變換有廣泛的應用,如數位訊號處理、計算大整數乘法、求解偏微分方程等等。本條目只描述各種快速算法,對於離散傅立葉變換的性質和應用,請參見離散傅立葉變換。

哈希函數

HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合,重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字符串。好的散列函數在輸入域中很少出現散列衝突。在散列表和數據處理中,不抑制衝突來區別數據,會使得資料庫記錄更難找到。

堆排序

Heapsort是指利用堆積樹(堆)這種數據結構所設計的一種排序算法。堆積樹是一個近似完全二叉樹的結構,並同時滿足堆積屬性:即子結點的鍵值或索引總是小於(或者大於)它的父結點。

歸併排序

Merge sort是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法(Divide and Conquer)的一個非常典型的應用。

RANSAC 算法

RANSAC 是」RANdom SAmpleConsensus」的縮寫。該算法是用於從一組觀測數據中估計數學模型參數的迭代方法,由Fischler and Bolles在1981提出,它是一種非確定性算法,因為它只能以一定的概率得到合理的結果,隨著迭代次數的增加,這種概率是增加的。該算法的基本假設是觀測數據集中存在」inliers」(那些對模型參數估計起到支持作用的點)和」outliers」(不符合模型的點),並且這組觀測數據受到噪聲影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。

RSA加密演算法

這是一個公鑰加密算法,也是世界上第一個適合用來做籤名的算法。今天的RSA已經專利失效,其被廣泛地用於電子商務加密,大家都相信,只要密鑰足夠長,這個算法就會是安全的。

併查集Union-find

併查集是一種樹型的數據結構,用於處理一些不相交集合(Disjoint Sets)的合併及查詢問題。常常在使用中以森林來表示。

Viterbi algorithm

尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)

本文來源:網易教育頻道專稿 責任編輯:王曉易_NE0011

相關焦點

  • DSP集成開發環境中的混合編程及FFT算法的實現
    CCS一般工作在兩種模式下:軟體仿真器和與硬體開發板相結合的在線編程。前者可以脫離DSP晶片,在PC機上模擬DSP指令集與工作機制,主要用於前期算法實現和調試。後者實時運行在DSP晶片上,可以在線編制和調試應用程式。
  • 關於計算機編程中的算法問題,這2個案例的觀點值得去思考
    算法的五大特徵是,有窮性,可行性,確切性,輸入,輸出。凡是任何一個算法都必須滿足這5個基本特徵,只要是數學問題,不存在模稜兩可的事情。哪怕是概率問題在數學裡專門有一門課程叫「概率論」與之對應,能將這些不確定問題進行數學化。
  • 計算思維:編程教育的價值追求
    我們在「編程」的旅途中,時常有茫然失措、忘了初心的感覺。為什麼要踏上編程之旅?為什麼要帶孩子們一起編程?有個聲音不早不晚地出現:因為通過編程,可以讓孩子們擁有與讀、寫、算同等重要的認知能力——計算思維! 是的,計算思維是我們俯下身子和計算機對話的入口,也是編程學習漫漫歷程中對編程學科本質的一種洞見。
  • AI系統首次實現真正自主編程:利用遺傳算法,完爆初級程式設計師
    讓AI自動編程是人工智慧領域長久以來的夢想之一。現在,來自彭博和英特爾實驗室的兩位研究人員,號稱實現了首個能夠自動生成完整軟體程序的AI系統「AI Programmer」,這個「AI程式設計師」利用遺傳算法和圖靈完備語言,開發的程序理論上能夠完成任何類型的任務。AI自動編程的時代,大幕已開。 讓AI自動編程一直是計算機科學家的夢想。
  • 少兒編程,存在即是合理,但卻未必是必選項,關於成長有更重要的
    這其中,有一大半都與能力有關,少兒編程的存在,其實是可以培養出孩子像科學家一樣思考,像工程師一樣解決問題的能力。人類文明從農業文明發展到工業文明再到信息文明,信息已經成為世界的最重要資源。每一個孩子都必須能認識「信息」、理解「信息」,最後能駕馭「信息」。
  • PLC最全編程算法,收藏備用!
    PLC編程算法(1):PLC中無非就是三大量:開關量、模擬量、脈衝量。搞清楚三者之間的關係,你就能熟練的掌握PLC了。1、 開關量也稱邏輯量,指僅有兩個取值,0或1、ON或OFF。它是最常用的控制,對它進行控制是PLC的優勢,也是PLC最基本的應用。
  • PLC最全編程算法,總結的很全面!
    PLC編程算法(1) PLC中無非就是三大量:開關量、模擬量、脈衝量。只在搞清楚三者之間的關係,你就能熟練的掌握PLC了。 1、 開關量也稱邏輯量,指僅有兩個取值,0或1、ON或OFF。
  • 算法是個什麼鬼?其實很簡單!
    有關所有三個級別中描述的簡單算法「添加m+n」的示例,請參見算法示例。設計算法設計是指求解問題的一種方法或數學過程以及工程算法。算法的設計是運籌學許多解理論的一部分,如動態規劃、分治等。設計和實現算法設計的技術也稱為算法設計模式,例如模板方法模式和裝飾器模式。算法設計的一個最重要的方面是創建一個具有高效運行時的算法,也稱為大O。
  • Python視頻教程網課編程零基礎入門數據分析網絡爬蟲全套Python...
    python教程大合集,包含python所有就業方向,每套課程均來自市面上主流培訓機構的原版教程,價值都在數百元以上 每套課程均包含:視頻課程+課件+原始碼 重要:建議根據自己工作方向和需求,重點選擇2到3套課程學精,吃透,然後在工作 重要:零基礎小白建議先選擇零基礎全能篇的一套課程學精,然後再根據自 己的需求和規劃選擇學習其他方向課程,學完後一定要多實踐
  • 影響計算機算法世界的十位大師 - OSCHINA - 中文開源技術交流社區
    其經典著作《電腦程式設計藝術》更是被譽為算法中「真正」的聖經,像KMP和LR(K)這樣令人不可思議的算法,在此書比比皆是。難怪連 Bill Gates都說:「如果能做對書裡所有的習題,就直接來微軟上班吧!」
  • 阿里三面慘遭被虐,關於數據結構與算法竟然一竅不通!
    以Java為描述語言,介紹計算機編程中使用的數據結構和算法,覆蓋相應競爭性考試的主題,目的不是提供關於數據結構和算法的定理及證明,而是強調問題及其分析,講解必備知識和解題技巧。書中匯集知名IT企業經典的編程面試題目並給出解題思路,為學生應試和軟體開發人員面試提供有益指導。本書特點:所有代碼用Java實現。數據結構難點啟發思考。為每個問題列舉可能的解決辦法。
  • 秒懂機器人編程與計算機編程的區別
    機器人編程:機器人課程,不僅涉及編程的知識,還需要孩子們了解學習機械、工程、信息等方面的知識。很多時候要運用機械解決問題,強調動手能力。解決問題的過程可能狀況百出,需要細心觀察、耐心解決,更強調團隊配合能力。
  • [活動入口]純粹的算法競賽 CodeM 2018美團點評編程大賽正式啟動
    CodeM是由美團點評主辦的編程競賽,旨在展示和激發軟體技術人才的專業實力、創新能力
  • KNN算法中的K有多重要
    K-最近鄰(KNN)是一種有監督的機器學習算法,可用於解決分類和回歸問題。它基於一個非常簡單的想法,數據點的值由它周圍的數據點決定。考慮的數據點數量由k值確定。因此,k值是算法的核心。KNN分類器根據多數表決原則確定數據點的類別。如果k設置為5,則檢查5個最近點的類別。也可以根據多數類進行回歸預測,同樣,KNN回歸取5個最近點的平均值。
  • 人人都可以學會的編程思維
    學習編程思維對於人們提高技術與知識水平至關重要。什麼是編程思維?編程思維,雖然包括理性推理、邏輯思維和數學運算,但實際上,它就是做事的工具。最重要的是指如何創造性地解決問題。>舉個例子:高斯算法如果叫你把1~100的所有數字用心算加起來,如果你不知道高斯方法的話,你最快多久能算出來?
  • [數值算法與編程]高斯消去法
    在線性有限元計算中,通過單元剛度矩陣推導,整體剛度矩陣組裝等步驟後,最終得到的是一個線性方程組:     其中,
  • DNA甲基化是體細胞重編程過程中重要的表觀遺傳屏障
    點擊查看 DNA甲基化是體細胞重編程過程中重要的表觀遺傳屏障。然而,整個基因組的甲基化是如何被重新編程的,這在很大程度上仍是未知的。Sardina等人通過繪製正在重新編程的細胞的DNA甲基化圖來解決這個問題,並表明TET蛋白和轉錄因子協同配合去甲基化對重新編程至關重要。
  • 技術篇:蟻群算法實例解析
    在蟻群算法中,螞蟻的眼睛觀察到的範圍是一個方格世界,相關參數為速度半徑,一般為3,可觀察和移動的範圍為3x3方格。我們設置螞蟻的數量為50個,信息素重要因子為1,啟發函數重要因子為5,初次迭代次數為1,最大迭代次數為200。接下來隨機產生各個螞蟻的起點城市,逐個螞蟻路徑選擇,逐個城市路徑選擇,將已訪問的城市和沒訪問的城市以及待訪問城市找出來,並採用輪盤賭法選擇下一個城市。
  • 非計算機專業的同學在學習編程時,除了程式語言還需要學什麼
    首先,對於想自學編程的同學來說,在學習程式語言的過程中,還需要同步學習很多內容,具體的學習內容要結合自己的主攻方向,比如學習C語言的同學如果想往嵌入式方向發展,就需要按照嵌入式開發的要求學習相關的知識。
  • 學計算機編程需要什麼基礎_一文了解
    計算機編程已經成為16-18歲學生的重點關注課程,對於每個學生來說,學計算機編程需要什麼基礎,是決定學生是否學習的前提條件。下面我們一起看看,學習計算機編程需要哪些基礎:1、英語基礎計算機英語與傳統的英語知識不同,需要了解的大部分是計算機的專業單詞或者詞彙,普遍較為簡單。但是在高級編程中,會出現比較生澀的詞彙,對於想要參與計算機語言設計以及在職業發展上有更多追求的同學可以自學一下大學英語。畢竟現在在學習IT技術上晉升的道路上,專業文檔的閱讀能力也是非常重要的。