演算法
演算法（英語：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}
延伸閱讀
編輯[編]
