算法分類

算法分類

在數學和計算機科學之中,算法(Algorithm)為一個計算的具體步驟,常用於計算、數據處理和自動推理。精確而言,算法是一個表示為有限長列表的有效方法。算法應包含清晰定義的指令用於計算函式。 算法分類可以根據算法設計原理、算法的具體套用和其他一些特性進行分類。

分類

算法(Algorithm)是指解題方案的準確而完整的描述,是一系列解決問題的清晰指令,算法代表著用系統的方法描述解決問題的策略機制。目前國內外有關的研究和科學文獻中對於算法分類這個術語還沒有明確定義,算法分類簡單可以根據算法設計原理、算法的具體套用和其他一些特性進行分類。可分為基本算法或根據具體套用領域進行分類,在機器學習中,按照學習方式,常把算法分為監督學習算法、非監督學習算法及半監督學習算法。按照圖論的算法進行分類,算法可以分為哈夫曼編碼、樹的遍歷、最短路徑算法、最小生成樹算法、最小樹形圖、網路流算法、匹配算法。

算法

算法(Algorithm)是指解題方案的準確而完整的描述,是一系列解決問題的清晰指令,算法代表著用系統的方法描述解決問題的策略機制。也就是說,能夠對一定規範的輸入,在有限時間內獲得所要求的輸出。如果一個算法有缺陷,或不適合於某個問題,執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間複雜度與時間複雜度來衡量。

算法中的指令描述的是一個計算,當其運行時能從一個初始狀態和(可能為空的)初始輸入開始,經過一系列 有限而清晰定義的狀態,最終產生 輸出停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在內的一些算法,包含了一些隨機輸入。

一個算法應該具有以下五個重要的特徵:

算法有窮性(Finiteness)

算法的有窮性是指算法必須能在執行有限個步驟之後終止;

算法確切性(Definiteness)

算法的每一步驟必須有確切的定義;

算法輸入項(Input)

一個算法有0個或多個輸入,以刻畫運算對象的初始情況,所謂0個輸入是指算法本身定出了初始條件;

算法輸出項(Output)

一個算法有一個或多個輸出,以反映對輸入數據加工後的結果。沒有輸出的算法是毫無意義的;

算法可行性(Effectiveness)

算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步,即每個計算步都可以在有限時間內完成(也稱之為有效性)。

基本算法

枚舉

在數學和計算機科學理論中,一個集的 枚舉是列出某些有窮序列集的所有成員的程式,或者是一種特定類型對象的計數。這兩種類型經常(但不總是)重疊。

枚舉是一個被命名的整型常數的集合,枚舉在日常生活中很常見,例如表示星期的SUNDAY、MONDAY、TUESDAY、WEDNESDAY、THURSDAY、FRIDAY、SATURDAY就是一個枚舉。 枚舉的說明與結構和聯合相似,其形式為:

如果枚舉沒有初始化,即省掉"=整型常數"時,則從第一個標識符開始,順次賦給標識符0, 1, 2, ...。但當枚舉中的某個成員賦值後,其後的成員按依次加1的規則確定其值。

搜尋

寬度優先搜尋

寬度優先搜尋算法是沿著樹的寬度遍歷樹的節點,如果發現目標,則算法中止。屬於盲目搜尋。

深度優先搜尋

深度優先搜尋沿著樹的最大深度方向生成節點並與目標節點進行比較,只有當上次訪問的節點不是目標節點,而且沒有其他節點可以生成的時候,才轉到上次訪問節點的父節點,然後搜尋該節點的其他子節點。因此深度優先搜尋也稱為回溯搜尋。它既不是完備的,也不是最優的。有時候,某些特定的問題會產生大量重複的節點。例如“八數碼”問題就是這樣的,當每次運用向上、向下、向左、向右移動空格的算符時,可能產生與已經產生的節點重複的節點。當再次搜尋到這個重複節點時,由於套用的算符基本一致,還會產生重複,所以為了節約時間和存儲空間,往往在深度優先算法中設立一個機制,用來刪除這些重複的節點,以提高效率。

疊代加深搜尋(ID搜尋)

對深度優先搜尋進行了一定改進,對搜尋樹的深度進行控制,即有界深度優先搜尋。

在程式找到目標之前,通過疊代不斷增大d以保證完備性和最優性。雖然會有不少重複搜尋,但是鑒於每增加一次d,則搜尋的時間複雜度會以指數級別增加,所以重複搜尋的時間可以忽略,亦可以與A*算法結合(即IDA*搜尋算法)來剪枝。

疊代加深搜尋通常用於那種搜尋樹又深又寬、但是解並不是很深的情況,這時廣度優先搜尋會超空間,而深度優先搜尋會逾時。這時疊代加深搜尋很有用,可是說是在用遞歸方法在實現廣度優先搜尋。

啟發式OR圖搜尋算法

爬山算法

模擬退火算法

最好優先

通用圖

A*

約束滿足搜尋

搜尋策略還可以指在使用搜尋引擎中所使用的策略,它通常是搜尋之母,一個好的搜尋過程必定有一個好的搜尋策略來支持。

學習方式分類

監督學習:輸入的數據為訓練數據,並且每一個數據都會帶有標籤,比如“廣告/非廣告”,或者當時的股票的價格。通過訓練過程建模,模型需要作出預測,如果預測出錯會被修正。直到模型輸出準確的訓練結果,訓練過程會一直持續。常用於解決問題有分類和回歸。常用的算法包括邏輯回歸和BP神經網路。

無監督學習:輸入的標籤沒有數據,輸出沒有標準答案,就是一系列的樣本。無監督學習通過推斷輸入數據中的結構建模。這可能是提取一般規律,可以是通過數學處理系統系統的減少冗雜,或者根據相似性組織數據。常用於解決的問題有聚類,降維和關聯規則的學習。常用的算法包括了Apriori算法和K均值算法。

半監督學習:半監督學習的輸入數據包含標籤和不帶標籤的樣本。半監督學習的情況是有一個預期中的預測,但是模型必須通過學習結構整理數據從而做出預測。常用於解決的問題是分類和回歸。常用的算法是對所有的無標籤的數據建模進行的預測算法(可以看做無監督學習的延伸)。

相關詞條

熱門詞條

聯絡我們