一些重要的算法The Most Important Algorithms
生活随笔
收集整理的這篇文章主要介紹了
一些重要的算法The Most Important Algorithms
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
下面是一些比較重要的算法，原文羅列了32個(gè)，但我覺得有很多是數(shù)論里的，和計(jì)算機(jī)的不相干，所以沒有選取。下面的這些，有的我們經(jīng)常在用，有的基本不用。有的很常見，有的很偏。不過了解一下也是好事。也歡迎你留下你覺得有意義的算法。（注：本篇文章并非翻譯，其中的算法描述大部份摘自Wikipedia，因?yàn)榫S基百科描述的很專業(yè)了）
俗稱A星算法。這是一種在圖形平面上，有多個(gè)節(jié)點(diǎn)的路徑，求出最低通過成本的算法。常用于游戲中的NPC的移動(dòng)計(jì)算，或線上游戲的BOT的移動(dòng)計(jì)算上。該算法像Dijkstra算法一樣，可以找到一條最短路徑；也像BFS一樣，進(jìn)行啟發(fā)式的搜索。
束搜索(beam search) 方法是解決優(yōu)化問題的一種啟發(fā)式方法,它是在分枝定界方法基礎(chǔ)上發(fā)展起來的,它使用啟發(fā)式方法估計(jì)k 個(gè)最好的路徑,僅從這k 個(gè)路徑出發(fā)向下搜索,即每一層只有滿意的結(jié)點(diǎn)會(huì)被保留,其它的結(jié)點(diǎn)則被永久拋棄,從而比分枝定界法能大大節(jié)省運(yùn)行時(shí)間。束搜索于20 世紀(jì)70 年代中期首先被應(yīng)用于人工智能領(lǐng)域,1976 年Lowerre 在其稱為HARPY的語音識(shí)別系統(tǒng)中第一次使用了束搜索方法,他的目標(biāo)是并行地搜索幾個(gè)潛在的最優(yōu)決策路徑以減少回溯,并快速地獲得一個(gè)解。
一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索算法每一次比較都使搜索范圍縮小一半。
分支定界 (branch and bound) 算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方法搜索解空間樹，并且，在分支定界算法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。
數(shù)據(jù)壓縮是通過減少計(jì)算機(jī)中所存儲(chǔ)數(shù)據(jù)或者通信傳播中數(shù)據(jù)的冗余度，達(dá)到增大數(shù)據(jù)密度，最終使數(shù)據(jù)的存儲(chǔ)空間減少的技術(shù)。數(shù)據(jù)壓縮在文件存儲(chǔ)和分布式系統(tǒng)領(lǐng)域有著十分廣泛的應(yīng)用。數(shù)據(jù)壓縮也代表著尺寸媒介容量的增大和網(wǎng)絡(luò)帶寬的擴(kuò)展。
Diffie–Hellman key exchange，簡(jiǎn)稱“D–H”， 是一種安全協(xié)議。它可以讓雙方在完全沒有對(duì)方任何預(yù)先信息的條件下通過不安全信道建立起一個(gè)密鑰。這個(gè)密鑰可以在后續(xù)的通訊中作為對(duì)稱密鑰來加密通訊內(nèi)容。
迪科斯徹算法（Dijkstra）是由荷蘭計(jì)算機(jī)科學(xué)家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發(fā)明的。算法解決的是有向圖中單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問題。舉例來說，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示著城市間開車行經(jīng)的距離，迪科斯徹算法可以用來找到兩個(gè)城市之間的最短路徑。
動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。比較著名的應(yīng)用實(shí)例有：求解最短路徑問題，背包問題，項(xiàng)目管理，網(wǎng)絡(luò)流優(yōu)化等。這里也有一篇文章說得比較詳細(xì)。
在數(shù)學(xué)中，輾轉(zhuǎn)相除法，又稱歐幾里得算法，是求最大公約數(shù)的算法。輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現(xiàn)的《九章算術(shù)》。
在統(tǒng)計(jì)計(jì)算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計(jì)的算法，其中概率模型依賴于無法觀測(cè)的隱藏變量（Latent Variable）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺的數(shù)據(jù)聚類（Data Clustering）領(lǐng)域。最大期望算法經(jīng)過兩個(gè)步驟交替進(jìn)行計(jì)算，第一步是計(jì)算期望（E），利用對(duì)隱藏變量的現(xiàn)有估計(jì)值，計(jì)算其最大似然估計(jì)值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計(jì)算參數(shù)的值。M 步上找到的參數(shù)估計(jì)值被用于下一個(gè) E 步計(jì)算中，這個(gè)過程不斷交替進(jìn)行。
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速算法，也可用于計(jì)算離散傅里葉變換的逆變換?？焖俑道锶~變換有廣泛的應(yīng)用，如數(shù)字信號(hào)處理、計(jì)算大整數(shù)乘法、求解偏微分方程等等。本條目只描述各種快速算法，對(duì)于離散傅里葉變換的性質(zhì)和應(yīng)用，請(qǐng)參見離散傅里葉變換。
Hash Function是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字“指紋”的方法。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個(gè)叫做散列值的指紋。散列值通常用來代表一個(gè)短的隨機(jī)字母和數(shù)字組成的字符串。好的散列函數(shù)在輸入域中很少出現(xiàn)散列沖突。在散列表和數(shù)據(jù)處理中，不抑制沖突來區(qū)別數(shù)據(jù)，會(huì)使得數(shù)據(jù)庫記錄更難找到。
Heapsort?是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積樹是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積屬性：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父結(jié)點(diǎn)。
Merge sort是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。
RANSAC 是”RANdom SAmple Consensus”的縮寫。該算法是用于從一組觀測(cè)數(shù)據(jù)中估計(jì)數(shù)學(xué)模型參數(shù)的迭代方法，由Fischler and Bolles在1981 提出，它是一種非確定性算法，因?yàn)樗荒芤砸欢ǖ母怕实玫胶侠淼慕Y(jié)果，隨著迭代次數(shù)的增加，這種概率是增加的。 該算法的基本假設(shè)是觀測(cè)數(shù)據(jù)集中存在”inliers”（那些對(duì)模型參數(shù)估計(jì)起到支持作用的點(diǎn)）和”outliers”（不符合模型的點(diǎn)），并且這組觀測(cè)數(shù)據(jù)受到噪聲影響。RANSAC 假設(shè)給定一組”inliers”數(shù)據(jù)就能夠得到最優(yōu)的符合這組點(diǎn)的模型。
這是一個(gè)公鑰加密算法，也是世界上第一個(gè)適合用來做簽名的算法。今天的RSA已經(jīng)專利失效，其被廣泛地用于電子商務(wù)加密，大家都相信，只要密鑰足夠長(zhǎng)，這個(gè)算法就會(huì)是安全的
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。常常在使用中以森林來表示。
尋找最可能的隱藏狀態(tài)序列(Finding most probable sequence of hidden states)
附錄
- 關(guān)于這個(gè)世界上的算法，你可以看看Wikipedia的這個(gè)網(wǎng)頁：http://en.wikipedia.org/wiki/List_of_algorithms
- 關(guān)于排序算法，你可以看看本站的這幾篇文章《一個(gè)顯示排序過程的Python腳本》、《一個(gè)排序算法比較的網(wǎng)站》
附：英文版原文：
The Most Important Algorithms
After a long discussion with some of my RISC colleagues about what the 5 most important algorithms on the world are, we couldn't reach a consensus on this question. So I suggested to perform a little survey. The criterion for suggestions was that these algorithms should be widely used. Further we restrict ourselves to the fields of computer science and mathematics.?As I expected the number of different suggestions is close to 5 * (no. of participants) In the following you find the results (in alphabetical order) of this survey (which of course is highly non-representative since most of the participants are computer scientists).
Graph search algorithm that finds a path from a given initial node to a given goal node. It employs a heuristic estimate that ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A* algorithm is therefore an example of best-first search.
Beam search is a search algorithm that is an optimization of best-first search. Like best-first search, it uses a heuristic function to evaluate the promise of each node it examines. Beam search, however, only unfolds the first m most promising nodes at each depth, where m is a fixed number, the beam width.
Technique for finding a particular value in a linear array, by ruling out half of the data at each step.
A general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization.
In computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gr?bner basis with respect to some monomial order. One can view it as a generalization of the Euclidean algorithm for univariate gcd computation and of Gaussian elimination for linear systems.
Data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes.
Cryptographic protocol which allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.
Algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights.
I.e., the formula f'(x) = (f(x+h) - f(x-h)) / 2h.
Dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below.
Algorithm to determine the greatest common divisor (gcd) of two integers. It is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. The algorithm does not require factoring the two integers.
In statistical computing, an expectation-maximization (EM) algorithm is an algorithm for finding maximum likelihood estimates of parameters in probabilistic models, where the model depends on unobserved latent variables. EM alternates between performing an expectation step, which computes the expected value of the latent variables, and a maximization step, which computes the maximum likelihood estimates of the parameters given the data and setting the latent variables to their expectation.
Efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. FFTs are of great importance to a wide variety of applications, from digital signal processing to solving partial differential equations to algorithms for quickly multiplying large integers.
Gradient descent is an optimization algorithm that approaches a local minimum of a function by taking steps proportional to the negative of the gradient (or the approximate gradient) of the function at the current point. If instead one takes steps proportional to the gradient, one approaches a local maximum of that function; the procedure is then known as gradient ascent.
A function for summarizing or probabilistically identifying data. Typically this means one applies a mathematical formula to the data, producing a string which is probably more or less unique to that data. The string is much shorter than the original data, but can be used to uniquely identify it.
In computer science a heap is a specialized tree-based data structure. Heaps are favourite data structures for many applications: Heap sort, selection algorithms (finding the min, max or both of them, median or even any kth element in sublinear time), graph algorithms.
For systems that need to multiply numbers in the range of several thousand digits, such as computer algebra systems and bignum libraries, long multiplication is too slow. These systems employ Karatsuba multiplication, which was discovered in 1962.
The Lenstra-Lenstra-Lovasz lattice reduction (LLL) algorithm is an algorithm which, given a lattice basis as input, outputs a basis with short, nearly orthogonal vectors. The LLL algorithm has found numerous applications in cryptanalysis of public-key encryption schemes: knapsack cryptosystems, RSA with particular settings, and so forth.
The maximum flow problem is finding a legal flow through a flow network that is maximal. Sometimes it is defined as finding the value of such a flow. The maximum flow problem can be seen as special case of more complex network flow problems. The maximal flow is related to the cuts in a network by the Max-flow min-cut theorem. The Ford-Fulkerson algorithm computes the maximum flow in a flow network.
A sorting algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order.
Efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. Newton's method is also a well-known algorithm for finding roots of equations in one or more dimensions. It can also be used to find local maxima and local minima of functions.
Q-learning is a reinforcement learning technique that works by learning an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter. A strength with Q-learning is that it is able to compare the expected utility of the available actions without requiring a model of the environment.
The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the number field sieve, NFS). It is still the fastest for integers under 110 decimal digits or so, and is considerably simpler than the number field sieve.
RANSAC is an abbreviation for "RANdom SAmple Consensus". It is an algorithm to estimate parameters of a mathematical model from a set of observed data which contains "outliers". A basic assumption is that the data consists of "inliers", i. e., data points which can be explained by some set of model parameters, and "outliers" which are data points that do not fit the model.
Algorithm for public-key encryption. It was the first algorithm known to be suitable for signing as well as encryption. RSA is still widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys.
In mathematics, the Sch?nhage-Strassen algorithm is an asymptotically fast method for multiplication of large integer numbers. The run-time is O(N log(N) log(log(N))). The algorithm uses Fast Fourier Transforms in rings.
In mathematical optimization theory, the simplex algorithm a popular technique for numerical solution of the linear programming problem. A linear programming problem consists of a collection of linear inequalities on a number of real variables and a fixed linear functional which is to be maximized (or minimized).
In linear algebra, SVD is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics, e.g., computing the pseudoinverse of a matrix (to solve the least squares problem), solving overdetermined linear systems, matrix approximation, numerical weather prediction.
Systems of linear equations belong to the oldest problems in mathematics and they have many applications, such as in digital signal processing, estimation, forecasting and generally in linear programming and in the approximation of non-linear problems in numerical analysis. An efficient way to solve systems of linear equations is given by the Gauss-Jordan elimination or by the Cholesky decomposition.
In pattern recognition: Computes a measure for every pixel which tells you if this pixel is located in a homogenous region, if it belongs to an edge, or if it is a vertex.
Given a set of elements, it is often useful to partition them into a number of separate, nonoverlapping groups. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:?
Find: Determine which group a particular element is in.?
Union: Combine or merge two groups into a single group.
Dynamic programming algorithm for finding the most likely sequence of hidden states - known as the Viterbi path - that result in a sequence of observed events, especially in the context of hidden Markov models.
總結(jié)
以上是生活随笔為你收集整理的一些重要的算法The Most Important Algorithms的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【Visual C++】一些开发心得与调
- 下一篇： 一些很有用的技术工具