☰

最常用的五大算法總結！附算法題思路，看完茅塞頓開！

算法總結---最常用的五大算法（算法題思路）

一、總結一句話總結：【明確所求：dijkstra是求點到點的距離，輔助數組就是源點到目標點的數組】【最簡實例分析：比如思考dijkstra：假設先只有三個點】

1、貪心算法是什麼？當前看來最好的選擇局部最優解可能得到整體最優解或是最優解的近似解

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對範圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。

2、貪心算法實例？求最小生成樹的Prim算法：【邊集中依次選取那些權值最小的邊】求最小生成樹的Kruskal算法：【和求最短路徑有點相似：不過這裡是求兩個集合之間的距離】：【一維中間數組記錄到當前已經選擇頂點的最短距離】：【二維表記錄每個點到每個點的最短距離】計算強連通子圖的Dijkstra算法：【和最小生成樹Kruskal類似】【二維表記錄每個點到每個點的最短距離】【明確所求：dijkstra是求點到點的距離，輔助數組就是源點到目標點的數組】【每次從輔助數組中選擇最小的，用選出的點來更新輔助數組】【最簡實例分析：比如思考dijkstra：假設先只有三個點】構造huffman樹的算法：【每次都選取權值小的兩個點合成二叉樹】

Kruskal算法簡述

在帶權連通圖中，不斷地在邊集合中找到最小的邊，如果該邊滿足得到最小生成樹的條件，就將其構造，直到最後得到一顆最小生成樹。

假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾算法構造最小生成樹的過程爲：先構造一個只含 n 個頂點，而邊集爲空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊爲止。

普利姆算法的核心步驟是：

在帶權連通圖中，從圖中某一頂點v開始，此時集合U={v}，重複執行下述操作：在所有u∈U,w∈V-U的邊(u,w)∈E中找到一條權值最小的邊，將(u,w)這條邊加入到已找到邊的集合，並且將點w加入到集合U中，當U=V時，就找到了這顆最小生成樹。

3、分治法的思想？規模爲N的問題分解爲K個規模較小的子問題這些子問題相互獨立且與原問題性質相同解題思路：分解->求解->合併

分治算法的基本思想是將一個規模爲N的問題分解爲K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。

4、分治法實例？二分法：猜數字遊戲，【你給數字我來猜】快排：【選取基準數（比如第一個），比我小的往前挪，比我大的往後挪】【輔助變量：指向第一個數據的哨兵i，指向最後一個數據的哨兵j】【分別從初始序列“6 1 2 7 9 3 4 5 10 8”兩端開始“探測”。先從右往左找一個小於6的數，再從左往右找一個大於6的數，然後交換他們】【交換哨兵ij對應的值】【哨兵ij相遇，交換相遇的位置和基準數】【哨兵i走過的位置所有的都比基準數小，j走過的都大】【設置的基準數是最左邊的數，所以需要讓哨兵j先出動：因爲j會先發現比基準小的數，然後ij再相遇，然後在交換基準數和ij相遇的這個數】歸併排序：【遞歸實現】【一直拆分到一個數】【排序完再合併】【利用完全二叉樹特性的排序】【操作數組下標實現二叉樹】【合併的過程和鏈表合併有點相似】

5、動態規劃基本思想？空間換時間：如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重複計算，節省時間。和分治法的區別：與分治法不同的是，適合於用動態規劃求解的問題，【經分解得到子問題往往不是互相獨立的】。若用分治法來解這類問題，則【分解得到的子問題數目太多】，有些【子問題被重複計算了很多次】。狀態轉移方程如何書寫：【看如何將問題分解爲子問題：分解的過程就是狀態轉移方程】【確定狀態，就是所求：dijkstra是求點到點的距離，輔助數組就是源點到目標點的數組】【最簡實例分析：比如思考dijkstra：假設先只有三個點】

6、動態規劃實例？求全路徑最短路徑的Floyd算法：【從i號頂點到j號頂點只經過前k號點的最短路程】揹包問題：【從揹包中取哪幾個有最優價值】

for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];

7、回溯法基本思想？深度優先算法搜索某一步時，走不通，就退回剪枝：回溯法優化

回溯法（探索與回溯法）是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術爲回溯法，而滿足回溯條件的某個狀態的點稱爲“回溯點”。

8、回溯法經典實例？八皇后：

9、分支限界法的基本思想？廣度優先搜索：節點出隊，節點的孩子全入隊操作常見兩種：隊列式和優先隊列式

分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。在分支限界法中，每一個活結點只有一次機會成爲擴展結點。活結點一旦成爲擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被捨棄，其餘兒子結點被加入活結點表中。此後，從活結點表中取下一結點成爲當前擴展結點，並重覆上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表爲空時爲止。

常見的兩種分支限界法：

（1）隊列式(FIFO)分支限界法按照隊列先進先出（FIFO）原則選取下一個節點爲擴展節點。（2）優先隊列式分支限界法按照優先隊列中規定的優先級選取優先級最高的節點成爲當前擴展節點。

10、分支限界法與回溯法的區別？求解目標：回溯-所有解，分支限界法-一個解搜索方式：回溯-深搜，分支限界法-廣搜

（1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。（2）搜索方式的不同：回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。

二、最常用的五大算法（轉）

轉自：最常用的五大算法https://blog.csdn.net/watson2016/article/details/77857824

一、貪心算法

用貪心法設計算法的特點是一步一步地進行，常以當前情況爲基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況，它省去了爲找最優解要窮盡所有可能而必須耗費的大量時間，它採用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化爲一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪心法不需要回溯。

注意：對於一個給定的問題，往往可能有好幾種量度標準。初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。因此，選擇能產生問題最優解的最優量度標準是使用貪婪算法的核心。

經典的求最小生成樹的Prim算法和Kruskal算法、計算強連通子圖的Dijkstra算法、構造huffman樹的算法都是漂亮的貪心算法

基本思路：

⒈建立數學模型來描述問題。⒉把求解的問題分成若干個子問題。⒊對每一子問題求解，得到子問題的局部最優解。⒋把子問題的解局部最優解合成原來解問題的一個解。實現該算法的過程：從問題的某一初始解出發；while 能朝給定總目標前進一步 do求出可行解的一個解元素；由所有解元素組合成問題的一個可行解。

例子：

馬踏棋盤的貪心算法【問題描述】馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，爲馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。

【貪心算法】其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的算法。在每個結點對其子結點進行選取時，優先選擇‘出口’最小的進行搜索，‘出口’的意思是在這些子結點中它們的可行子結點的個數，也就是‘孫子’結點越少的越優先跳，爲什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現‘死’結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。

二、分治算法

思想：

分治法應用場景：

運用分治策略解決的問題一般來說具有以下特點：1、原問題可以分解爲多個子問題這些子問題與原問題相比，只是問題的規模有所降低，其結構和求解方法與原問題相同或相似。2、原問題在分解過程中，遞歸地求解子問題由於遞歸都必須有一個終止條件，因此，當分解後的子問題規模足夠小時，應能夠直接求解。3、在求解並得到各個子問題的解後應能夠採用某種方式、方法合併或構造出原問題的解。不難發現，在分治策略中，由於子問題與原問題在結構和解法上的相似性，用分治方法解決的問題，大都採用了遞歸的形式。在各種排序方法中，如歸併排序、堆排序、快速排序等，都存在有分治的思想。

分治法解題的一般步驟：

（1）分解，將要解決的問題劃分成若干規模較小的同類問題；（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；（3）合併，按原問題的要求，將子問題的解逐層合併構成原問題的解。

三、動態規劃

基本思想：

動態規劃算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重複計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重複計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃算法多種多樣，但它們具有相同的填表格式。

與分治法最大的差別是：適合於用動態規劃法求解的問題，經分解後得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）

應用場景：

適用動態規劃的問題必須滿足最優化原理、無後效性和重疊性。1.最優化原理（最優子結構性質）最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。

2.無後效性將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無後向性，又稱爲無後效性。

3.子問題的重疊性動態規劃將原來具有指數級時間複雜度的搜索算法改進成了具有多項式時間複雜度的算法。其中的關鍵在於解決冗餘，這是動態規劃算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間複雜度要大於其它的算法。

求全路徑最短路徑的Floyd算法就是漂亮地運用了動態規劃思想。

下面是我找到的一個關於 0-1揹包問題的動態規劃思想PPT截圖：

問題描述：給定n種物品和一揹包。物品i的重量是wi，其價值爲vi，揹包的容量爲C。問應如何選擇裝入揹包的物品，使得裝入揹包中物品的總價值最大?

對於一種物品，要麼裝入揹包，要麼不裝。所以對於一種物品的裝入狀態可以取0和1.我們設物品i的裝入狀態爲xi,xi∈ (0,1)，此問題稱爲0-11揹包問題。

數據：物品個數n=5,物品重量w[n]={0，2，2，6，5，4},物品價值V[n]={0，6，3，5，4，6},（第0位，置爲0，不參與計算，只是便於與後面的下標進行統一，無特別用處，也可不這麼處理。）總重量c=10。揹包的最大容量爲10，那麼在設置數組m大小時，可以設行列值爲6和11，那麼，對於m(i,j)就表示可選物品爲i…n揹包容量爲j(總重量)時揹包中所放物品的最大價值。

四、回溯法

基本思想：

回溯法在問題的解空間樹中，按深度優先策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含（剪枝過程），則跳過對該結點爲根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先策略搜索。

回溯法就是對隱式圖的深度優先搜索算法

回溯法：爲了避免生成那些不可能產生最佳解的問題狀態，要不斷地利用限界函數(bounding function)來處死(剪枝)那些實際上不可能產生所需解的活結點，以減少問題的計算量。具有限界函數的深度優先生成法稱爲回溯法。（回溯法 = 窮舉 +　剪枝）

一般步驟：

(1)針對所給問題，定義問題的解空間；(2)確定易於搜索的解空間結構；(3)以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。

兩個常用的剪枝函數：

(1)約束函數：在擴展結點處減去不滿足約束的子數(2)限界函數：減去得不到最優解的子樹

用回溯法解題的一個顯著特徵是在搜索過程中動態產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度爲h(n)，則回溯法所需的計算空間通常爲O(h(n))。而顯式地存儲整個解空間則需要O(2^h(n))或O(h(n)!)內存空間。

五、分支限界法

基本思想：

分支限界法與回溯法的區別：

常見的兩種分支限界法：

例子：單源最短路徑問題（參考http://www.cnblogs.com/chinazhangjie/archive/2010/11/01/1866136.html）

1、問題描述在下圖所給的有向圖G中，每一邊都有一個非負邊權。要求圖G的從源頂點s到目標頂點t之間的最短路徑。

下圖是用優先隊列式分支限界法解有向圖G的單源最短路徑問題產生的解空間樹。其中，每一個結點旁邊的數字表示該結點所對應的當前路長。

找到一條路徑：

目前的最短路徑是8，一旦發現某個結點的下界不小於這個最短路進，則剪枝：

同一個結點選擇最短的到達路徑：

2.剪枝策略在算法擴展結點的過程中，一旦發現一個結點的下界不小於當前找到的最短路長，則算法剪去以該結點爲根的子樹。在算法中，利用結點間的控制關係進行剪枝。從源頂點s出發，2條不同路徑到達圖G的同一頂點。由於兩條路徑的路長不同，因此可以將路長長的路徑所對應的樹中的結點爲根的子樹剪去。3.算法思想解單源最短路徑問題的優先隊列式分支限界法用一極小堆來存儲活結點表。其優先級是結點所對應的當前路長。算法從圖G的源頂點s和空優先隊列開始。結點s被擴展後，它的兒子結點被依次插入堆中。此後，算法從堆中取出具有最小當前路長的結點作爲當前擴展結點，並依次檢查與當前擴展結點相鄰的所有頂點。如果從當前擴展結點i到頂點j有邊可達，且從源出發，途經頂點i再到頂點j的所相應的路徑的長度小於當前最優路徑長度，則將該頂點作爲活結點插入到活結點優先隊列中。這個結點的擴展過程一直繼續到活結點優先隊列爲空時爲止。

源碼如下：

[cpp] view plain copy

/* 主題：單源最短路徑問題

* 作者：chinazhangjie

* 郵箱：chinajiezhang@gmail.com

* 開發語言：C++

* 開發環境：Mircosoft Virsual Studio 2008

* 時間: 2010.11.01

#include

usingnamespace std;

struct node_info

public:

node_info (int i,int w)

: index (i), weight (w) {}

node_info ()

: index(0),weight(0) {}

node_info (const node_info & ni)

: index (ni.index), weight (ni.weight) {}

friend

bool operator < (const node_info& lth,const node_info& rth) {

return lth.weight > rth.weight ; // 爲了實現從小到大的順序

public:

int index; // 結點位置

int weight; // 權值

struct path_info

public:

path_info ()

: front_index(0), weight (numeric_limits::max()) {}

public:

int front_index;

int weight;

// single source shortest paths

class ss_shortest_paths

public:

ss_shortest_paths (const vector >& g,int end_location)

:no_edge (-1), end_node (end_location), node_count (g.size()) , graph (g)

// 打印最短路徑

void print_spaths () const {

cout << "min weight : " << shortest_path << endl;

cout << "path: " ;

copy (s_path_index.rbegin(),s_path_index.rend(),

ostream_iterator (cout, " "));

cout << endl;

// 求最短路徑

void shortest_paths () {

vector path(node_count);

priority_queue > min_heap;

min_heap.push (node_info(0,0)); // 將起始結點入隊

while (true) {

node_info top = min_heap.top (); // 取出最大值

min_heap.pop ();

// 已到達目的結點

if (top.index == end_node) {

break ;

// 未到達則遍歷

for (int i = 0; i < node_count; ++ i) {

// 頂點top.index和i間有邊，且此路徑長小於原先從原點到i的路徑長

if (graph[top.index][i] != no_edge &&

(top.weight + graph[top.index][i]) < path[i].weight) {

min_heap.push (node_info (i,top.weight + graph[top.index][i]));

path[i].front_index = top.index;

path[i].weight = top.weight + graph[top.index][i];

if (min_heap.empty()) {

break ;

shortest_path = path[end_node].weight;

int index = end_node;

s_path_index.push_back(index) ;

while (true) {

index = path[index].front_index ;

s_path_index.push_back(index);

if (index == 0) {

break;

private:

vector > graph ; // 圖的數組表示

int node_count; // 結點個數

constint no_edge; // 無通路

constint end_node; // 目的結點

vector s_path_index; // 最短路徑

int shortest_path; // 最短路徑

int main()

constint size = 11;

vector > graph (size);

for (int i = 0;i < size; ++ i) {

graph[i].resize (size);

for (int i = 0;i < size; ++ i) {

for (int j = 0;j < size; ++ j) {

graph[i][j] = -1;

graph[0][1] = 2;

graph[0][2] = 3;

graph[0][3] = 4;

graph[1][2] = 3;

graph[1][5] = 2;

graph[1][4] = 7;

graph[2][5] = 9;

graph[2][6] = 2;

graph[3][6] = 2;

graph[4][7] = 3;

graph[4][8] = 3;

graph[5][6] = 1;

graph[5][8] = 3;

graph[6][9] = 1;

graph[6][8] = 5;

graph[7][10] = 3;

graph[8][10] = 2;

graph[9][8] = 2;

graph[9][10] = 2;

ss_shortest_paths ssp (graph, 10);

ssp.shortest_paths ();

ssp.print_spaths ();

return 0;

測試數據（圖）

測試結果：

min weight :8path: 0 2 6 9 10

轉載於:

https://www.cnblogs.com/Renyi-Fan/p/10815119.html

最常用的五大算法總結！附算法題思路，看完茅塞頓開！

相關資訊