分枝定界演算法

❶ 什麼是分支演算法

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

利用分支定界演算法對問題的解空間樹進行搜索，它的搜索策略是：

1 ．產生當前擴展結點的所有孩子結點；

2 ．在產生的孩子結點中，拋棄那些不可能產生可行解（或最優解）的結點；

3 ．將其餘的孩子結點加入活結點表；

4 ．從活結點表中選擇下一個活結點作為新的擴展結點。

如此循環，直到找到問題的可行解（最優解）或活結點表為空。

從活結點表中選擇下一個活結點作為新的擴展結點，根據選擇方式的不同，分支定界演算法通常可以分為兩種形式：

1 ． FIFO(First In First Out) 分支定界演算法：按照先進先出原則選擇下一個活結點作為擴展結點，即從活結點表中取出結點的順序與加入結點的順序相同。

2 ．最小耗費或最大收益分支定界演算法：在這種情況下，每個結點都有一個耗費或收益。如果要查找一個具有最小耗費的解，那麼要選擇的下一個擴展結點就是活結點表中具有最小耗費的活結點；如果要查找一個具有最大收益的解，那麼要選擇的下一個擴展結點就是活結點表中具有最大收益的活結點。

又稱分支定界搜索法。過程系統綜合的一類方法。該法是將原始問題分解，產生一組子問題。分支是將一組解分為幾組子解，定界是建立這些子組解的目標函數的邊界。如果某一子組的解在這些邊界之外，就將這一子組舍棄（剪枝）。分支定界法原為運籌學中求解整數規劃(或混合整數規劃)問題的一種方法。用該法尋求整數最優解的效率很高。將該法原理用於過程系統綜合可大大減少需要計算的方案數日。

分支定界法的思想是：首先確定目標值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。

在競賽中，我們有時會碰到一些題目，它們既不能通過建立數學模型解決，又沒有現成演算法可以套用，或者非遍歷所有狀況才可以得出正確結果。這時，我們就必須採用搜索演算法來解決問題。
搜索演算法按搜索的方式分有兩類，一類是深度優先搜索，一類是廣度優先搜索。我們知道，深度搜索編程簡單，程序簡潔易懂，空間需求也比較低，但是這種方法的時間復雜度往往是指數級的，倘若不加優化，其時間效率簡直無法忍受；而廣度優先搜索雖然時間復雜度比前者低一些，但其龐大的空間需求量又往往讓人望而卻步。
所以，對程序進行優化，就成為搜索演算法編程中最關鍵的一環。
本文所要討論的便是搜索演算法中優化程序的一種基本方法棗「剪枝」。

什麼是剪枝
相信剛開始接觸搜索演算法的人，都做過類似迷宮這樣的題目吧。我們在「走迷宮」的時候，一般回溯法思路是這樣的：
1、這個方向有路可走，我沒走過
2、往這個方向前進
3、是死胡同，往回走，回到上一個路口
4、重復第一步，直到找著出口
這樣的思路很好理解，編程起來也比較容易。但是當迷宮的規模很大時，回溯法的缺點便暴露無遺：搜索耗時極巨，無法忍受。
我們可不可以在向某個方向前進時，先一步判斷出這樣走會不會走到死胡同里呢？這樣一來，搜索的時間不就可以減少了嗎？
答案是：可以的。
剪枝的概念，其實就跟走迷宮避開死胡同差不多。若我們把搜索的過程看成是對一棵樹的遍歷，那麼剪枝顧名思義，就是將樹中的一些「死胡同」，不能到達我們需要的解的枝條「剪」掉，以減少搜索的時間。
搜索演算法，絕大部分需要用到剪枝。然而，不是所有的枝條都可以剪掉，這就需要通過設計出合理的判斷方法，以決定某一分支的取捨。在設計判斷方法的時候，需要遵循一定的原則。
剪枝的原則
1、正確性
正如上文所述，枝條不是愛剪就能剪的。如果隨便剪枝，把帶有最優解的那一分支也剪掉了的話，剪枝也就失去了意義。所以，剪枝的前提是一定要保證不丟失正確的結果。
2、准確性
在保證了正確性的基礎上，我們應該根據具體問題具體分析，採用合適的判斷手段，使不包含最優解的枝條盡可能多的被剪去，以達到程序「最優化」的目的。可以說，剪枝的准確性，是衡量一個優化演算法好壞的標准。
3、高效性 設計優化程序的根本目的，是要減少搜索的次數，使程序運行的時間減少。但為了使搜索次數盡可能的減少，我們又必須花工夫設計出一個准確性較高的優化演算法，而當演算法的准確性升高，其判斷的次數必定增多，從而又導致耗時的增多，這便引出了矛盾。
因此，如何在優化與效率之間尋找一個平衡點，使得程序的時間復雜度盡可能降低，同樣是非常重要的。倘若一個剪枝的判斷效果非常好，但是它卻需要耗費大量的時間來判斷、比較，結果整個程序運行起來也跟沒有優化過的沒什麼區別，這樣就太得不償失了。
綜上所述，我們可以把剪枝優化的主要原則歸結為六個字：正確、准確、高效。
剪枝演算法按照其判斷思路可大致分成兩類：可行性剪枝及最優性剪枝。

對於分支定界演算法,上界是已求得的可行解的目標函數值中的最小者,分為初始上界和在探測過程中產生的動態上界.分支定界法在求最優解的迭代過程中, 若某結點估計的下界不小於已知的上界, 則不必從該節點往下繼續搜索. 因此若能產生一個較好的上界, 可以消除許多不必要的列舉計算.

分支定界演算法的實現
在描述分支定界演算法步驟之前, 先對演算法涉及到的有關術語進行定義如下:
p —— 分支層數;
C*—— 當前最優目標函數值;
P*—— 相應於C*的工件順序;
P1—— 當前節點(現在需要進行分支的節點)所對應的部分序列.
分支定界演算法的實施步驟如下:
步驟1 初始化: 設置p = 0, P 1 = Á (空集) , C* = ∞.設當前節點總是與P 1 相對應. 此時, 當前節點即根節點.
步驟2 計算從當前節點分支得到的各個子節點的下界, 並按下界值由小到大對各子節點排序. 令p ←p + 1.
步驟3 如果當前節點被探測盡, 令p ←p - 1, 轉步驟6. 否則, 設當前層(第p 層) 各活動子節點中具有最小下界值的節點為Q , 則在P 1末尾加入Q 對應第p 位置上的工件, 此時的當前節點轉為Q , 轉步驟4.
步驟4 因為當前節點是同層同父節點具有最小下界值的節點, 如果當前節點下界值大於或等於C* , 則不必再搜索當前節點及其同層同父的活動節點, 這樣, 當前節點的上一層節點(父節點)被探測盡, p ←p - 1, 去掉P 1 中的最後一個工件,轉步驟6. 否則, 轉步驟5.
步驟5 如果p = n, 則得到一個較優順序.令P* = P 1, C* 是當前節點的下界值, p ←p - 1,去掉P 1 中最後一個工件, 轉步驟6; 否則轉步驟2.
步驟6 若p ≠ 0, 去掉P 1 中最後一個工件,轉步驟3; 否則, 演算法停止. C* 是最優的目標函數值, P* 是最優順序.

❷ 是的 計算機演算法

計算機演算法是以一步接一步的方式來詳細描述計算機如何將輸入轉化為所要求的輸出的過程，或者說，演算法是對計算機上執行的計算過程的具體描述。
編輯本段演算法性質一個演算法必須具備以下性質： （1）演算法首先必須是正確的，即對於任意的一組輸入，包括合理的輸入與不合理的輸入，總能得到預期的輸出。如果一個演算法只是對合理的輸入才能得到預期的輸出，而在異常情況下卻無法預料輸出的結果，那麼它就不是正確的。 （2）演算法必須是由一系列具體步驟組成的，並且每一步都能夠被計算機所理解和執行，而不是抽象和模糊的概念。 （3）每個步驟都有確定的執行順序，即上一步在哪裡，下一步是什麼，都必須明確，無二義性。 （4）無論演算法有多麼復雜，都必須在有限步之後結束並終止運行，即演算法的步驟必須是有限的。在任何情況下，演算法都不能陷入無限循環中。 一個問題的解決方案可以有多種表達方式，但只有滿足以上4個條件的解才能稱之為演算法。編輯本段重要演算法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)。編輯本段演算法特點1.有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他是為有效演算法。 2. 確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。 3. 有零個或多個輸入、所謂輸入是指在執行演算法是需要從外界取得必要的信息。 4. 有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。 5.有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。編輯本段演算法與程序雖然演算法與計算機程序密切相關，但二者也存在區別：計算機程序是演算法的一個實例，是將演算法通過某種計算機語言表達出來的具體形式；同一個演算法可以用任何一種計算機語言來表達。 演算法列表 圖論 路徑問題 0/1邊權最短路徑 BFS 非負邊權最短路徑（Dijkstra） 可以用Dijkstra解決問題的特徵 負邊權最短路徑 Bellman-Ford Bellman-Ford的Yen-氏優化 差分約束系統 Floyd 廣義路徑問題 傳遞閉包 極小極大距離 / 極大極小距離 Euler Path / Tour 圈套圈演算法 混合圖的 Euler Path / Tour Hamilton Path / Tour 特殊圖的Hamilton Path / Tour 構造 生成樹問題 最小生成樹 第k小生成樹 最優比率生成樹 0/1分數規劃 度限制生成樹 連通性問題 強大的DFS演算法 無向圖連通性 割點 割邊 二連通分支 有向圖連通性 強連通分支 2-SAT 最小點基 有向無環圖 拓撲排序 有向無環圖與動態規劃的關系 二分圖匹配問題 一般圖問題與二分圖問題的轉換思路 最大匹配 有向圖的最小路徑覆蓋 0 / 1矩陣的最小覆蓋 完備匹配 最優匹配 穩定婚姻 網路流問題 網路流模型的簡單特徵和與線性規劃的關系 最大流最小割定理 最大流問題 有上下界的最大流問題 循環流 最小費用最大流 / 最大費用最大流 弦圖的性質和判定 組合數學 解決組合數學問題時常用的思想 逼近 遞推 / 動態規劃 概率問題 Polya定理 計算幾何 / 解析幾何 計算幾何的核心：叉積 / 面積 解析幾何的主力：復數 基本形 點 直線，線段 多邊形 凸多邊形 / 凸包 凸包演算法的引進，卷包裹法 Graham掃描法 水平序的引進，共線凸包的補丁 完美凸包演算法 相關判定 兩直線相交 兩線段相交 點在任意多邊形內的判定 點在凸多邊形內的判定 經典問題 最小外接圓 近似O(n)的最小外接圓演算法 點集直徑 旋轉卡殼，對踵點 多邊形的三角剖分 數學 / 數論 最大公約數 Euclid演算法 擴展的Euclid演算法 同餘方程 / 二元一次不定方程 同餘方程組 線性方程組 高斯消元法 解mod 2域上的線性方程組 整系數方程組的精確解法 矩陣 行列式的計算 利用矩陣乘法快速計算遞推關系 分數 分數樹 連分數逼近 數論計算 求N的約數個數 求phi(N) 求約數和 快速數論變換 …… 素數問題 概率判素演算法 概率因子分解 數據結構 組織結構 二叉堆 左偏樹 二項樹 勝者樹 跳躍表 樣式圖標 斜堆 reap 統計結構 樹狀數組 虛二叉樹 線段樹 矩形面積並 圓形面積並 關系結構 Hash表 並查集 路徑壓縮思想的應用 STL中的數據結構 vector deque set / map 動態規劃 / 記憶化搜索 動態規劃和記憶化搜索在思考方式上的區別 最長子序列系列問題 最長不下降子序列 最長公共子序列 一類NP問題的動態規劃解法 樹型動態規劃 背包問題 動態規劃的優化 四邊形不等式 函數的凸凹性 狀態設計 規劃方向 線性規劃 常用思想 二分 最小表示法 串 KMP Trie結構 後綴樹/後綴數組 LCA/RMQ 有限狀態自動機理論 排序 選擇/冒泡 快速排序 堆排序 歸並排序 基數排序 拓撲排序 排序網路
擴展閱讀：
1
《計算機演算法設計與分析導論》朱清新等編著人民郵電出版社
開放分類：
計算機，演算法

❸ 分支定界法的演算法步驟

(1)求整數規劃的鬆弛問題最優解。
(2)若鬆弛問題的最優解滿足整數要求，得到整數規劃的最優解，否則轉下一步。
(3)任意選一個非整數解的變數 ，在鬆弛問題中加上約束 及 +1組成兩個新的鬆弛問題，稱為分支。新的鬆弛問題具有如下特徵：當原問題是求最大值時，目標值是分支問題的上界；當原問題足求最小值時，目標值是分支問題的下界。
(4)檢查所有分支的解及目標函數值，若某分支的解是整數並且目標函數值大於(max)等於其他分支的目標值，則將其他分支剪去不再計算，若還存在非整數解並且目標值大於( max)整數解的目標值，需要繼續分支，再檢查，直到得到最優解。

❹ 什麼事演算法

計算機的演算法具有可行性，有窮性、輸入輸出、確定性。

計算機演算法特點

1.有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他視為有效演算法。

2. 確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。

3. 有零個或多個輸入、所謂輸入是指在執行演算法是需要從外界取得必要的信息。

4. 有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。

5.有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。

拓展資料：

重要演算法

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)。

參考資料：計算機演算法

❺ 什麼是分支定界法

先不考慮整數限制，求出相應的線性規劃的最優解，若此解不符合整數要求，則去掉不包含整數解的部分可行域，將可行域D分成D1、D2兩部分（分枝） ，然後分別求解這兩部分可行域對應的線性規劃，如果它們的解仍不是整數解，則繼續去掉不包含整數解的部分可行域，將可行域或分成與兩部分，再求解與對應的線性規劃，……，在計算中若已得到一個整數可行解，則以該解的目標函數值作為分枝的界限，如果某一線性規劃的目標值Z≤Z0，就沒有必要繼續分枝，因為分枝（增加約束）的結果所得的最優解只能更差。反之若Z＞Z0，則該線性規劃分枝後，有可能產生更好的整數解，一旦真的產生了一個更好的整數解，則以這個更好的整數解目標值作為新的界限，繼續進行分枝，直至產生不出更好的整數解為止。