算法
 |
算法（英語：algorithm），在數學（算學）和計算機科學之中，指一個被定義好的、計算機可施行其指示的有限步驟或次序[1]，常用於計算、數據處理和自動推理。算法可以使用條件語句通過各種途徑轉移代碼執行（稱為自動決策），並推導出有效的推論（稱為自動推理），最終實現自動化。
相反，啟發式是一種解決問題的方法，可能沒有完全指定，也可能不能保證正確或最優的結果，尤其是在沒有明確定義的正確或最優結果的問題領域。[2]例如，社交媒體推薦系統依賴於啟發式，儘管在21世紀的流行媒體中被廣泛稱為算法，但由於問題的性質，它無法提供正確的結果。
早在嘗試解決希爾伯特提出的判定問題時，算法的不完整概念已經初步定型；在其後的正式化階段中人們嘗試去定義「有效可計算性[3]」或者「有效方法[4]」。這些嘗試包括庫爾特·哥德爾、雅克·埃爾布朗和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年埃米爾·萊昂·珀斯特的波斯特-圖靈機和艾倫·圖靈1937年提出的圖靈機。即使在當下，依然常有符合直覺的想法難以定義為形式化算法的情況。[5]
算法是有效方法，包含一系列定義清晰的指令[6]，並可於有限的時間及空間內清楚的表述出來[7]。算法中的指令描述的是一個計算，它執行時從一個初始狀態和初始輸入（可能為空）開始，[8]經過一系列有限[9]而清晰定義的狀態最終產生輸出[10]並停止於一個終態。 一個狀態到另一個狀態的轉移不一定是確定的。 包括隨機化算法在內的一些算法，都包含了一些隨機輸入。[11][12]
歷史
[編輯]算法在中國古代文獻中稱為「術」，最早出現在《周髀算經》、《九章算術》。特別是《九章算術》，給出四則運算、最大公約數、最小公倍數、開平方根、開立方根、求素數的埃氏篩，線性方程組求解的高斯消元法。三國時代的劉徽給出求圓周率的算法：劉徽割圓術。
自唐代以來，歷代更有許多專門論述「算法」的專著：
- 唐代：《一位算法》 一卷，《算法》 一卷；
- 宋代：《算法緒論》 一卷、《算法秘訣》 一卷；最著名的是楊輝的《楊輝算法》；
- 元代：《丁巨算法》；
- 明代：程大位 《算法統宗》
- 清代：《開平算法》、《算法一得》、《算法全書》。
而英文名稱「algorithm」來自於9世紀波斯數學家花拉子米（比阿勒·霍瓦里松，波斯語：خوارزمی ，拉丁轉寫：al-Khwarizmi），因為比阿勒·霍瓦里松在數學上提出了算法這個概念。「算法」原為「algorism」，即「al-Khwarizmi」的音轉，意思是「花剌子模的」運算法則，在18世紀演變為「algorithm」。
歐幾里得算法被人們認為是史上第一個算法。
第一次編寫程序是愛達·勒芙蕾絲（Ada Byron）於1842年為巴貝奇分析機編寫求解解伯努利微分方程的程序，因此愛達·勒芙蕾絲被大多數人認為是世界上第一位程序員[13]。因為查爾斯·巴貝奇（Charles Babbage）未能完成他的巴貝奇分析機，這個算法未能在巴貝奇分析機上執行。 因為「well-defined procedure」缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的電腦的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了算法定義的難題，圖靈的思想對算法的發展起到了重要的作用。
特徵
[編輯]以下是高德納在他的著作《計算機程序設計藝術》裡對演算法的特徵歸納：
- 輸入：一個算法必須有零個或以上輸入量。
- 輸出：一個算法應有一個或以上輸出量，輸出量是算法計算的結果。
- 明確性：算法的描述必須無歧義，以保證算法的實際執行結果是精確地符合要求或期望，通常要求實際執行結果是確定的。
- 有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統模擬的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必須在有限個步驟內完成任務。
- 有效性：又稱可行性。能夠實現，算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現。
基本要素
[編輯]算法的核心是建立問題抽象的模型和明確求解目標，之後可以根據具體的問題選擇不同的模式和方法完成算法的設計。
常用設計模式
[編輯]完全遍曆法和不完全遍曆法：在問題的解是有限離散解空間，且可以驗證正確性和最優性時，最簡單的算法就是把解空間的所有元素完全遍歷一遍，逐個檢測元素是否是我們要的解。這是最直接的算法，實現往往最簡單。但是當解空間特別龐大時，這種算法很可能導致工程上無法承受的計算量。這時候可以利用不完全遍歷方法——例如各種搜索法和規劃法——來減少計算量。 分治法：把一個問題分割成互相獨立的多個部分分別求解的思路。這種求解思路帶來的好處之一是便於進行並行計算。 動態規劃法：當問題的整體最優解就是由局部最優解組成的時候，經常採用的一種方法。貪婪算法：常見的近似求解思路。當問題的整體最優解不是（或無法證明是）由局部最優解組成，且對解的最優性沒有要求的時候，可以採用的一種方法。 線性規劃法：見條目。 簡併法：把一個問題通過邏輯或數學推理，簡化成與之等價或者近似的、相對簡單的模型，進而求解的方法。
常用實現方法
[編輯]遞歸方法與迭代方法 順序計算、並行計算和分布式運算：順序計算就是把形式化算法用程序設計語言進行單線程序列化後執行。 確定性算法和非確定性算法 精確求解和近似求解
形式化算法
[編輯]算法是電腦處理信息的本質，因為計算機程序本質上是一個算法來告訴電腦確切的步驟來執行一個指定的任務，如計算職工的薪水或打印學生的成績單。一般地，當算法在處理信息時，會從輸入裝置或數據的存儲地址讀取數據，把結果寫入輸出設備或某個存儲地址供以後再調用。
複雜度
[編輯]時間複雜度
[編輯]算法的時間複雜度是指算法需要消耗的時間資源。一般來說，電腦算法是問題規模的函數，算法的時間複雜度也因此記做 ： 算法執行時間的增長率與的增長率正相關，稱作漸近時間複雜度，簡稱時間複雜度。 常見的時間複雜度有：常數階，對數階，線性階，線性對數階，平方階，立方階，…，次方階，指數階。隨着問題規模的不斷增大，上述時間複雜度不斷增大，算法的執行效率越低。
空間複雜度
[編輯]算法的空間複雜度是指算法需要消耗的空間資源。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示。同時間複雜度相比，空間複雜度的分析要簡單得多。
實現
[編輯]算法不單單可以用計算機程序來實現，也可以在人工神經網絡、電路或者機械設備上實現。
示例
[編輯]求最大值演算法
[編輯]這是算法的一個簡單的例子。 我們有一串隨機數列。我們的目的是找到這個數列中最大的數。如果將數列中的每一個數位看成是一顆豆子的大小，可以將下面的算法形象地稱為「撿豆子」：
- 首先將第一顆豆子放入口袋中。
- 從第二顆豆子開始檢查，如果正在檢查的豆子比口袋中的還大，則將它撿起放入口袋中，同時丟掉原先口袋中的豆子。反之則繼續下一顆豆子。直到最後一顆豆子。
- 最後口袋中的豆子就是所有的豆子中最大的一顆。以上算法在中國大陸的教科書中通常被叫做「打擂法」或者「循環打擂」[14][15][16]：在一個for循環中，每輪循環都有新的挑戰者。若挑戰者勝的話，挑戰者做新擂主，否則擂主衛冕。for循環結束後輸出最後的擂主。
下面是一個形式算法，用ANSI C代碼表示
int max（int *array, int size）
{
int mval = *array;
int i;
for （i = 1; i < size; i++）
if （array[i] > mval）
mval = array[i];
return mval;
}
求最大公約數演算法
[編輯]求兩個自然數的最大公約數 設兩個變量和
- 如果，則交換和
- 除以，得到餘數
- 判斷，正確則即為「最大公約數」，否則下一步
- 將賦值給，將賦值給，重做第一步。
用ANSI C代碼表示
//交換2數
void swapi（int *x, int *y）
{
int tmp = *x;
*x = *y;
*y = tmp;
}
int gcd（int m, int n）
{
int r;
do
{
if （m < n）
swapi（&m, &n）;
r = m % n;
m = n;
n = r;
} while （r）;
return m;
}
利用if函式以及遞迴則能做出更為精簡的程式碼，更可省去交換的麻煩。（但是也因為遞迴呼叫，其空間複雜度提高）
int gcd（int a,int b）
{
if（a%b）
return gcd（b,a%b）;
return b;
}
分類
[編輯]分類算法有多種方法，每種方法都有自己的優點。
通過實施
[編輯]分類算法的一種方法是通過實現手段。
int gcd（int A, int B） {
if （B == 0）
return A;
else if （A > B）
return gcd（A-B,B）;
else
return gcd（A,B-A）;
}
|
| 從上面的流程圖遞歸 C 實現歐幾里得算法 |
- 遞歸
- 遞歸算法是一種重複調用（引用）自身的算法，直到某個條件（也稱為終止條件）匹配，這是函數式編程常用的方法。迭代算法使用循環之類的重複構造，有時使用堆棧之類的附加數據結構來解決給定的問題。有些問題自然適合於這種或那種實現。例如，使用遞歸實現可以很好地理解河內的塔。每個遞歸版本都有一個等價的（但可能或多或少複雜）迭代版本，反之亦然。
- 串聯的、平行的或分布的
- 算法通常是在假設計算機一次執行一條算法指令的情況下討論的。那些計算機有時被稱為串行計算機。針對這種環境設計的算法稱為串行算法，而不是並行算法或分布式算法。並行算法是利用計算機體系結構的算法，其中多個處理器可以同時處理一個問題。分布式算法是使用與計算機網絡連接的多台機器的算法。並行和分布式算法將問題劃分為更加對稱或不對稱的子問題，並將結果收集在一起。例如，CPU 就是並行算法的一個例子。這種算法的資源消耗不僅是每個處理器上的處理器周期，而且是處理器之間的通信開銷。有些排序算法可以有效地並行化，但是它們的通信開銷很大。迭代算法通常是可並行的，但有些問題沒有並行算法，稱為固有的串行問題。
- 確定的或不確定的
- 確定性算法在算法的每一步都用精確的決策來解決問題，而非確定性算法通過猜測來解決問題，雖然通過啟發式使典型的猜測更加精確。
- 精確的或近似的
- 雖然許多算法達到一個精確的解決方案，近似算法尋求一個近似，更接近真正的解決方案。這種近似可以通過使用確定性策略或隨機策略來實現。這些算法對許多難題都有實用價值。近似算法的一個例子是背包問題，其中有一組給定的項目。它的目標是包裝背包，以獲得最大的總價值。每個物品都有一定的重量和價值。可攜帶的總重量不超過某個固定數字 X，因此，解決方案必須考慮物品的重量及其價值。[17]
- 量子算法
- 量子算法運行在一個現實的量子計算模型上。這個術語通常用於那些本質上似乎是量子的算法，或者使用量子計算的一些基本特性，如態疊加原理或量子糾纏。
通過設計範例
[編輯]對算法進行分類的另一種方法是通過它們的設計方法或範例。有一定數量的範例，每一個不同於其他。此外，這些類別中的每一個都包括許多不同類型的算法。一些常見的範例是:
- 暴力搜查或徹底搜查
- 蠻力是一種解決問題的方法，包括系統地嘗試每一種可能的選擇，直到找到最佳解決方案。這種方法可能非常耗時，因為它需要遍歷所有可能的變量組合。但是，當其他方法不可用或過於複雜時，常常使用這種方法。蠻力可以用來解決各種問題，包括尋找兩點之間的最短路徑和破解密碼。
- 各個擊破
- 分而治之的算法重複地將一個問題的實例減少為同一個問題的一個或多個更小的實例（通常是遞歸的） ，直到這些實例足夠小以便於解決。分而治之的一個例子是合併排序。在將數據分割成片段後，可以對每個片段進行排序，在征服階段通過合併片段可以對整個數據進行排序。一種更簡單的分而治之的算法稱為減而治算法，它解決一個相同的子問題，並使用這個子問題的解決方案來解決更大的問題。分治算法將問題劃分為多個子問題，因此分治階段比減少分治算法複雜。遞減和征服算法的一個例子是二進制搜索算法。
- 搜索和枚舉
- 許多問題（比如下棋）可以建模為圖形上的問題。圖探索算法規定了在圖中移動的規則，對於這類問題非常有用。這一類別還包括搜索算法、分支和界枚舉以及回溯。
- 隨機算法
- 這樣的算法隨機（或偽隨機）做出一些選擇。它們可以非常有用地找到近似解決方案的問題，找到精確的解決方案可能是不切實際的（見下面的啟發式方法）。對於其中的一些問題，我們知道最快的近似必須包含一些隨機性。[18] 對於某些問題，具有多項式時間複雜度的隨機算法能否成為最快的算法，是一個被稱為「 P/NP問題」的懸而未決的問題。這種算法有兩大類:
- 蒙特卡羅算法以高概率返回正確答案。例如 RP 是這些運行在多項式時間的子類。
- 拉斯維加斯算法總是返回正確的答案，但他們的運行時間只是概率約束，例如 ZPP。
- 降低複雜性
- 這種技術涉及到通過將一個困難問題轉化為一個更廣為人知的問題來解決它，我們（希望）已經有了漸近最優算法。目標是找到一種複雜度不受所得到的簡化算法控制的簡化算法。例如，一種用於在未排序列表中查找中值的選擇算法首先對列表進行排序（代價較高的部分） ，然後取出排序列表中的中間元素（代價較低的部分）。這種技術也被稱為轉換和征服。
- 反向追蹤
- 在這種方法中，多個解決方案是逐步構建的，當確定它們不能生成有效的完整解決方案時，就會放棄這些解決方案。
優化問題
[編輯]對於最優化問題，有一個更具體的算法分類; 這類問題的算法可能屬於上述一個或多個一般類別，也可能屬於以下類別之一:
- 線性規劃
- 當搜索受線性等式和不等式約束的線性函數的最優解時，該問題的約束可以直接用於產生最優解。有一些算法可以解決這類問題，比如流行的單純形法。[19] 線性規劃可以解決的問題包括有向圖的最大流問題。如果一個問題額外要求一個或多個未知數必須是一個整數，那麼它被分類為整數規劃。一個線性規劃算法可以解決這樣的問題，如果它可以證明所有的限制整數值是表面的，即，解決方案滿足這些限制。在一般情況下，根據問題的難度，使用專門的算法或找到近似解的算法。
- 動態編程
- 當一個問題顯示出最優子結構ーー意味着一個問題的最優解可以從子問題的最優解構造出來ーー和重疊子問題，意味着同一個子問題可以用來解決許多不同的問題實例時，一種叫做動態規劃的快速方法可以避免重新計算已經計算出來的解。例如，Floyd-Warshall 算法，在一個加權圖中，通過使用從所有相鄰頂點到達目標的最短路徑，可以找到從一個頂點到達目標的最短路徑。動態編程和制表一起使用。動態規劃與分治的主要區別在於子問題在分治中或多或少是獨立的，而子問題在動態規劃中是重疊的。動態編程和簡單遞歸的區別在於遞歸調用的緩存或制表。當子問題是獨立的並且沒有重複時，制表不起作用; 因此動態編程不是所有複雜問題的解決方案。通過使用制表法或維護已經解決的子問題表，動態規劃將許多問題的指數性質降低到多項式複雜度。
- 貪婪的方法
- 貪婪算法類似於動態規劃算法，它通過檢查子結構來工作，在這種情況下，不是檢查問題，而是檢查給定的解。這種算法從某種解開始，這種解可能已經給出或已經以某種方式構造出來，然後通過小的修改對其進行改進。對於一些問題，他們可以找到最優解，而對於其他問題，他們停留在局部最優，也就是說，在解決方案，不能改進的算法，但不是最優的。貪婪算法最常用的用途是尋找最小生成樹，在這種方法中可以找到最優解。霍夫曼樹，克魯斯卡爾，普里姆，Sollin 是貪婪的算法，可以解決這個最佳化問題。
- 啟發式方法
- 在優化問題中，如果不能找到最優解，可以使用啟發式算法來尋找接近最優解的解。這些算法的工作原理是隨着它們的進展越來越接近最優解。原則上，如果運行無限長的時間，他們會找到最優解。它們的優點是能夠在相對較短的時間內找到一個非常接近最優解的解。這些算法包括本地搜索、禁忌搜索、模擬退火搜索和遺傳算法。其中一些算法，如模擬退火，是非確定性算法，而其他的，如禁忌搜索，是確定性的。當非最優解的誤差界限已知時，該算法進一步被歸類為近似演算法。
通過研究領域
[編輯] |
每個科學領域都有自己的問題，需要高效的算法。一個領域中的相關問題經常被一起研究。一些示例類是搜索算法、排序算法、合併算法、數值算法、圖形算法、字符串算法、計算幾何算法、組合算法、醫學算法、機器學習、密碼學、數據壓縮算法和解析技術。
字段之間往往相互重疊，一個字段的算法進步可能會改進其他字段的算法，有時候這些字段完全不相關。例如，動態規劃是為了優化工業中的資源消耗而發明的，但是現在被用於解決許多領域中的廣泛問題。
通過複雜性
[編輯] |
算法可以根據它們需要完成的時間和它們的輸入大小進行分類:
- 常數時間: 如果算法所需的時間相同，則不管輸入大小如何。例如，對數組元素的訪問。
- 對數時間: 如果時間是輸入大小的對數函數。二進制搜索算法。
- 線性時間: 如果時間與輸入大小成正比。列表的遍歷。
- 多項式時間: 如果時間是輸入大小的冪次。例如，氣泡排序算法具有二次時間複雜度。
- EXPTIME: 如果時間是輸入大小的指數函數。例如暴力搜索法。
一些問題可能有多個不同複雜度的算法，而另一些問題可能沒有算法或者沒有已知的有效算法。還有從一些問題到其他問題的映射。由於這個原因，我們發現根據問題的最佳可能算法的複雜性，將問題本身分類比將算法分為等價類更為合適。
連續算法
[編輯]形容詞「連續」用於「算法」一詞時，可以表示:
- 對表示連續數量的數據進行操作的算法，即使這些數據是由離散近似表示的ーー這種算法是在數值分析中研究的; 或
- 一種微分方程形式的算法，在模擬計算機上運行，不斷地對數據進行操作。[20]
參考文獻
[編輯]- ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein; 殷建平等譯. 第1章 算法在计算机中的作用. 算法导论 原書第3版. 北京: 機械工業出版社. 2013年1月: 3[5] [2017-11-14]. ISBN 978-7-111-40701-0 （中文）.
- ^ David A.Grossman，Ophir Frieder，「信息檢索：算法和啟發式」，2004年第2版，ISBN 1402030045
- ^ Kleene（斯蒂芬·科爾·克萊尼）1943 in Davis 1965:274
- ^ Rosser（巴克利·羅瑟）1939 in Davis 1965:225
- ^ Moschovakis, Yiannis N. What is an algorithm?. Engquist, B.; Schmid, W. (編). Mathematics Unlimited—2001 and beyond. Springer. 2001: 919–936 （Part II） [2012-09-27]. （原始內容存檔於2021-04-24）.
- ^ Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations"（Rogers 1987:2）.
- ^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words"（Rogers 1987:2）.
- ^ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins"（Knuth 1973:5）
- ^ "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'"（Knuth 1973:5）
- ^ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs"（Knuth 1973:5）
- ^ Whether or not a process with random interior processes （not including the input） is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2）.
- ^ Whether or not a process with random interior processes （not including the input） is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2）.
- ^ Ada Lovelace honoured by Google doodle. The Guardian. 10 December 2012 [10 December 2012]. （原始內容存檔於2018-12-25）.
- ^ 2.4 赛场统分. 讀書頻道-IT技術圖書-51CTO.COM. [2017-06-07]. （原始內容存檔於2017-03-24）.
- ^ 实验3-9：循环打擂. 湖南科技大學程序設計在線評測（Online Judge）.[永久失效連結]
- ^ 高中,算法与程序设计,教案. 在點網. [2017-06-07]. （原始內容存檔於2019-06-03）.
- ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack Problems | Hans Kellerer | Springer. Springer. 2004 [September 19, 2017]. ISBN 978-3-540-40286-2. doi:10.1007/978-3-540-24777-7. （原始內容存檔於October 18, 2017） （英語）.Kellerer, Hans; Pferschy, Ulrich; Pisinger, David （2004）. Knapsack Problems | Hans Kellerer | Springer （頁面存檔備份，存於網際網路檔案館）. Springer. doi:10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. S2CID 28836720. Archived from the original on October 18, 2017. Retrieved September 19, 2017.
- ^ For instance, the volume of a convex polytope （described using a membership oracle） can be approximated to high accuracy by a randomized polynomial time algorithm, but not by a deterministic one: see Dyer, Martin; Frieze, Alan; Kannan, Ravi. A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies. J. ACM. January 1991, 38 (1): 1–17. CiteSeerX 10.1.1.145.4600
. S2CID 13268711. doi:10.1145/102782.102783.Dyer, Martin; Frieze, Alan; Kannan, Ravi （January 1991）. "A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies". J. ACM. 38 （1）: 1–17. CiteSeerX 10.1.1.145.4600 （頁面存檔備份，存於網際網路檔案館）. doi:10.1145/102782.102783. S2CID 13268711.
- ^ George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
- ^ Tsypkin. Adaptation and learning in automatic systems. Academic Press. 1971: 54. ISBN 978-0-08-095582-7.Tsypkin （1971）. Adaptation and learning in automatic systems. Academic Press. p. 54. 國際標準書號 978-0-08-095582-7.
參考書目
[編輯]- Rogers, Jr, Hartley. Theory of Recursive Functions and Effective Computability. The MIT Press. 1987. ISBN 0-262-68052-1.
- Davis, Martin. The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. 1965. ISBN 0-486-43228-9. Davis此書中有列出許多相關的論文，包括哥德爾、邱奇、圖靈、巴克利·羅瑟、斯蒂芬·科爾·克萊尼及埃米爾·波斯特的論文。在參考文獻中也會列出原作者的姓名。
參閱
[編輯]
.gif){kind=small}
延伸閱讀
[編輯][在維基數據編輯]
