---

🚀一、分治法

?（一）算法思想

精煉：將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的子問(wèn)題，以便各個(gè)擊破，分而治之。這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。這種算法設(shè)計(jì)策略叫做分治法。

兩部分組成

分（divide）：遞歸解決較小的問(wèn)題
治（conquer）：然后從子問(wèn)題的解構(gòu)建原問(wèn)題的解

三個(gè)步驟

1、分解（Divide）：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；
2、解決（Conquer）：若子問(wèn)題規(guī)模較小而容易被解決則直接解決，否則遞歸地解各個(gè)子問(wèn)題；
3、合并（Combine）：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。

例子：

問(wèn)：一個(gè)裝有 16 枚硬幣的袋子，16 枚硬幣中有一個(gè)是偽造的，偽造的硬幣和普通硬幣從表面上看不出有任何差別，但是那 個(gè)偽造的硬幣比真的硬幣要輕?，F(xiàn)有給你一臺(tái)天平，請(qǐng)你在盡可能最短的時(shí)間內(nèi)找出那枚偽造的硬幣

1. 常規(guī)解決辦法：

   每次拿出兩枚硬幣比重量，只到遇到兩枚硬幣重量不等時(shí)，重量更輕的那枚就是假幣。這題這樣比最多需要比8次，更多硬幣就更耗時(shí)，時(shí)間復(fù)雜度位:O(n)

2. 分治思維解題：

   我們先將 16 枚硬幣分為左右兩個(gè)部分，各為 8 個(gè)硬幣，分別稱重，必然會(huì)有一半輕一半重，而我們要的就是輕的那組重的舍去。接下來(lái)我們繼續(xù)對(duì)輕的進(jìn)行五五分，直至每組剩下一枚或者兩枚硬幣，這時(shí)我們的問(wèn)題自然就解決了。使用分治法此題需要比4次。**時(shí)間復(fù)雜度為:O(log2 n) ，**分治法的效率是可見(jiàn)的，如果基數(shù)加大效率提升將會(huì)大大提高。

?（二）相關(guān)代碼

1、二分查找算法就使用了分而治之的思想：

#include <stdio.h>
#include <stdlib.h>/*遞歸實(shí)現(xiàn)二分查找
參數(shù):
arr - 有序數(shù)組地址 arr
minSub - 查找范圍的最小下標(biāo) minSub
maxSub - 查找范圍的最大下標(biāo) maxSub
num - 帶查找數(shù)字
返回:找到則返回所在數(shù)組下標(biāo)，找不到則返回-1
*/int BinarySearch(int* arr,int minSub,int maxSub,int num){if(minSub>maxSub){return -1;//找不到 num 時(shí),直接返回}int mid=(minSub+maxSub)/2;if(num<arr[mid]){return BinarySearch(arr,minSub,mid-1, num);  //遞歸找左邊一半}else if(num>arr[mid]){return BinarySearch(arr,mid+1,maxSub, num);  //遞歸找右邊一半}else{return mid;//找到 num 時(shí)直接返回}
}int main(void){int arr[]={1, 3, 7, 9, 11};int index = BinarySearch(arr, 0, 4, 8);printf("index: %d\n", index);system("pause");return 0;
}

2、如果機(jī)器人一次可以上 1 級(jí)臺(tái)階，也可以一次上 2 級(jí)臺(tái)階。求機(jī)器人走一個(gè) n 級(jí)臺(tái)階總共有多少種走法。

分治法核心思想 ， 從上往下分析問(wèn)題，大問(wèn)題可以分解為子問(wèn)題，子問(wèn)題中還有更小的子問(wèn)題：

• 比如總共有 5 級(jí)臺(tái)階,求有多少種走法；由于機(jī)器人一次可以走兩級(jí)臺(tái)階，也可以走一級(jí)臺(tái)階，所以我們可以分成兩個(gè)情況：

  機(jī)器人最后一次走了兩級(jí)臺(tái)階，問(wèn)題變成了“走上一個(gè) 3 級(jí)臺(tái)階，有多少種走法？”

  機(jī)器人最后一步走了一級(jí)臺(tái)階，問(wèn)題變成了“走一個(gè) 4 級(jí)臺(tái)階，有多少種走法？”

• 我們將求 n 級(jí)臺(tái)階的共有多少種走法用 f(n) 來(lái)表示，則：

  f(n) = f(n-1) + f(n-2);

  由上可得 f(5) = f(4) + f(3);

  f(4) = f(3) + f(2);

  f(3)

/*遞歸實(shí)現(xiàn)機(jī)器人臺(tái)階走法統(tǒng)計(jì) 
參數(shù):n - 臺(tái)階個(gè)數(shù) 
返回: 上臺(tái)階總的走法 */
int WalkCout(int n)
{ if(n<0) return 0; if(n==1) return 1; //一級(jí)臺(tái)階，一種走法 else if(n==2) return 2; //二級(jí)臺(tái)階，兩種走法 else { //n 級(jí)臺(tái)階， n-1 個(gè)臺(tái)階走法 + n-2 個(gè)臺(tái)階的 走法 return WalkCout(n-1) + WalkCout(n-2); } 
}

總結(jié)：總體來(lái)講，分治法思維較為簡(jiǎn)單，因?yàn)榉纸馑季S存在，常常需要使用遞歸、循環(huán)等，常見(jiàn)的使用分治法思維的問(wèn)題有：合并排序、快速排序、漢諾塔問(wèn)題、大整數(shù)乘法等。

🚀二、動(dòng)態(tài)規(guī)劃算法

?（一）算法思想

精煉：動(dòng)態(tài)規(guī)劃也是一種分治思想，但與分治算法不同的是，分治算法是把原問(wèn)題分解為若干子問(wèn)題，自頂向下，求解各子問(wèn)題，合并子問(wèn)題的解從而得到原問(wèn)題的解。動(dòng)態(tài)規(guī)劃也是自頂向下把原問(wèn)題分解為若干子問(wèn)題，不同的是，之后自底向上，先求解最小的子問(wèn)題，把結(jié)果存儲(chǔ)在表格中，在求解大的子問(wèn)題時(shí)，直接從表格中查詢小的子問(wèn)題的解，避免重復(fù)計(jì)算，從而提高算法效率。

1. 具體步驟：

   • 判題題意是否為找出一個(gè)問(wèn)題的最優(yōu)解
   • 從上往下分析問(wèn)題，大問(wèn)題可以分解為子問(wèn)題，子問(wèn)題中還有更小的子問(wèn)題
   • 從下往上分析問(wèn)題 ，找出這些問(wèn)題之間的關(guān)聯(lián)
   • 討論底層的邊界問(wèn)題
   • 求解每個(gè)子問(wèn)題僅一次，并將其結(jié)果保存在一個(gè)表中，以后用到時(shí)直接存取，不重復(fù)計(jì)算，節(jié)省計(jì)算時(shí)間，自底向上地計(jì)算。
   • 整體問(wèn)題最優(yōu)解取決于子問(wèn)題的最優(yōu)解（狀態(tài)轉(zhuǎn)移方程）（將子問(wèn)題稱為狀態(tài)，最終狀態(tài)的求解歸結(jié)為其他狀態(tài)的求解）

2. 什么時(shí)候要用動(dòng)態(tài)規(guī)劃：

   如果要求一個(gè)問(wèn)題的最優(yōu)解（通常是最大值或者最小值），而且該問(wèn)題能夠分解成若干個(gè)子問(wèn)題，并且小問(wèn)題之間也存在重疊的子問(wèn)題，則考慮采用動(dòng)態(tài)規(guī)劃。

例子：

以動(dòng)態(tài)規(guī)劃中的機(jī)器人代碼為例，是否發(fā)現(xiàn)上面的代碼中存在很多重復(fù)的計(jì)算？比如：

比如: f(5) = f(4) + f(3)，計(jì)算分成兩個(gè)分支：

f(4) = f(3)+f(2) = f(2) + f(1) + f(2);

f(3) = f(2) + f(1) ;

上面紅色的部分就是重復(fù)計(jì)算的一部分！

?（二）相關(guān)代碼

我們將機(jī)器人代碼改為使用動(dòng)態(tài)規(guī)劃的思想：從下向上分析問(wèn)題

f(1) = 1

f(2) = 2

f(3) = f(1) + f(2) = 3

f(4) = f(3) + f(2) = 3 + 2 = 5

f(5) = f(4) + f(3) = 5 + 3 = 8

。。。依次類推 。。。

#include <iostream>
#include <assert.h>
using namespace std;
/*
如果機(jī)器人 一次可以上 1 級(jí)臺(tái)階，也可以一次上 2 級(jí)臺(tái)階。
求機(jī)器人走一個(gè) n 級(jí)臺(tái)階總共有多少種走法。
*///分治思想 
int GetSteps(int steps)
{assert(steps>0);if (1 == steps) return 1;if (2 == steps) return 2;return GetSteps(steps - 1)+ GetSteps(steps - 2);
}
//動(dòng)態(tài)規(guī)劃思想
int GetSteps2(int steps)
{assert(steps > 0);//由于臺(tái)階數(shù)從 1 開(kāi)始計(jì)數(shù)，而數(shù)組索引從 0 開(kāi)始計(jì)數(shù)，所以我們需要一個(gè)長(zhǎng)度為 steps+1 的數(shù)組，以確保能夠存儲(chǔ)起始臺(tái)階到目標(biāo)臺(tái)階的所有走法數(shù)。int *values=new int[steps+1]; //數(shù)組用于存儲(chǔ)走steps個(gè)臺(tái)階的走法數(shù)values[1] = 1;values[2] = 2;for (int i=3;i<=steps;i++){values[i] = values[i - 1] + values[i - 2];}int n = values[steps];delete[] values;return n;
}

用分治思想的時(shí)間復(fù)雜度為：O(2^n)，空間復(fù)雜度為O(1)

用動(dòng)態(tài)規(guī)劃思想的時(shí)間復(fù)雜度為：O(n)，空間復(fù)雜度也為O(n)

🚀三、回溯算法

?（一）算法思想

**精煉：**回溯算法就是在問(wèn)題的解空間中，按照某種方法（路徑）去尋找問(wèn)題的解，如果發(fā)現(xiàn)在當(dāng)前情況繼續(xù)往下已查不到解時(shí)，就“回溯”返回，嘗試別的路徑。

1、如果嘗試求解的空間是一棵樹(shù)：那么可以理解為

• 在問(wèn)題的解空間中，按深度優(yōu)先遍歷策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。
• 算法搜索至解空間 的任意一個(gè)節(jié)點(diǎn)時(shí)，先判斷該節(jié)點(diǎn)是否包含問(wèn)題的解。如果確定不包含，跳過(guò)對(duì)以該節(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先節(jié)點(diǎn)回溯，否則進(jìn)入該子樹(shù)，繼續(xù)深度優(yōu)先搜索。
• 回溯法解問(wèn)題的所有解時(shí)，必須回溯到根節(jié)點(diǎn)，且根節(jié)點(diǎn)的所有子樹(shù)都被搜索后才結(jié)束。
• 回溯法解問(wèn)題的一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可結(jié)束。

2、基本步驟

• 定義問(wèn)題的解空間
• 確定易于搜索的解空間結(jié)構(gòu)
• 以深度優(yōu)先搜索的策略搜索解空間，并在搜索過(guò)程中盡可能避免無(wú)效搜索（將已經(jīng)搜索過(guò)的結(jié)點(diǎn)做個(gè)標(biāo)記）

?（二）相關(guān)代碼

例子：

請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中任意一格開(kāi)始，每一步可以在矩陣中向左、右、上、下移動(dòng)一格。如果一條路徑經(jīng)過(guò)了 矩陣的某一格，那么該路徑不能再次進(jìn)入該格子。例如在下面的 3×4 的矩陣中包含一條字符串 “bfce”的路徑（路徑中的字母用下劃線標(biāo)出）。但矩陣中不包含字符串“abfb”的路徑，因?yàn)樽址牡谝粋€(gè)字符 b 占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入這個(gè)格子

解題思路：

• 首先，在矩陣中任選一個(gè)格子作為路徑的起點(diǎn)。
• 如果路徑上的第 i 個(gè)字符不是待搜索的目標(biāo)字符 ch，那么這個(gè)格子不可能處在路徑上的第 i 個(gè)位置。
• 如果路徑上的第 i 個(gè)字符正好是 ch，那么往相鄰的格子尋找路徑上的第 i+1 個(gè)字符。除在矩陣邊界上的格子之外，其他格子都有 4 個(gè)相鄰的格子。
• 重復(fù)這個(gè)過(guò)程直到路徑上的所有字符都在矩陣中找到相應(yīng)的位置。
• 由于路徑不能重復(fù)進(jìn)入矩陣的格子，還需要定義和字符矩陣大小一樣的布爾值矩陣，用來(lái)標(biāo)識(shí)路徑是否已經(jīng)進(jìn)入每個(gè)格子。
• 當(dāng)矩陣中坐標(biāo)為（row, col）的格子和路徑字符串中相應(yīng)的字符一樣時(shí)，從 4 個(gè)相鄰的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路徑字符串中下一個(gè)字符, 如果 4 個(gè)相鄰的格子都沒(méi)有匹配字符串中下一個(gè)的字符，表明當(dāng)前路徑字符串中字符在矩陣中的定位不正確，我們需要回到前一個(gè)，然后重新定位。

#include <iostream>
#include<assert.h>
using namespace std;/*
名企面試題： 請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。
路徑可以 從矩陣中任意一格開(kāi)始，每一步可以在矩陣中向左、右、上、下移動(dòng)一格。
如果一條路徑經(jīng)過(guò)了 矩陣的某一格，那么該路徑不能再次進(jìn)入該格子。
例如在下面的 3×4 的矩陣中包含一條字符串 “bfce”的路徑（路徑中的字母用下劃線標(biāo)出）。
但矩陣中不包含字符串“abfb”的路徑，因?yàn)?字符串的第一個(gè)字符 b 占據(jù)了矩陣中的第一行第二個(gè)格子之后，
路徑不能再次進(jìn)入這個(gè)格子。 
A B T G
C F C S
J D E H
*//*探測(cè)一個(gè)字符是否存在*/
bool isEqualSimpleStr(const char *matrix, int rows, int cols, int row, int col, int &strlength, const char * str,bool *visited);/*
功能: 判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。
參數(shù):
@ 矩陣 
@ 矩陣行數(shù)
@ 矩陣列數(shù)
@ 待查字符串
返回值：如果矩陣中存在 str 則返回 true ，否則返回 false
*/
bool IsHasStr(const char *matrix, int rows, int cols, const char *str)
{if (matrix == nullptr || rows < 1 || cols < 1 || str == nullptr) return false;int strLength = 0;bool *visited = new bool[rows*cols];memset(visited, 0, rows * cols);for (int row=0;row<rows;row++)for(int col=0;col<cols;col++){if (isEqualSimpleStr( matrix, rows, cols, row, col, strLength,str,visited)){//delete [] visited;return true;}}delete [] visited;return false;
}bool isEqualSimpleStr(const char *matrix, int rows, int cols, int row, int col, int &strlength, const char * str, bool *visited)
{if (str[strlength] == '\0') return true;//如果找到了字符串的結(jié)尾 則代表矩陣中存在該字符串路徑bool isEqual = false;if (row>=0&&row<rows && col>=0&&col<cols&& visited[row*cols+col]==false&& matrix[row*cols+col]==str[strlength]){strlength++;visited[row*cols + col] == true;isEqual = isEqualSimpleStr(matrix, rows, cols, row, col - 1, strlength, str, visited)|| isEqualSimpleStr(matrix, rows, cols, row, col + 1, strlength, str, visited)|| isEqualSimpleStr(matrix, rows, cols, row - 1, col, strlength, str, visited)|| isEqualSimpleStr(matrix, rows, cols, row + 1, col, strlength, str, visited);if (!isEqual) //如果沒(méi)找到{strlength--;visited[row*cols + col] == false;}	}return isEqual;
}int main()
{const char* matrix = "ABTG""CFCS""JDEH";const char* str = "BFCE";bool isExist = IsHasStr((const char*)matrix, 3, 4, str);if (isExist)cout << "matrix中存在 " << str << " 字符串的路徑" << endl;elsecout << "matrix中不存在 " << str << " 字符串的路徑" << endl;
}

回溯算法常常用在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹(shù)。

🚀四、貪心算法

?（一）算法思想

精煉：（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，算法得到的是在某種意義上的局部最優(yōu)解

基本步驟：

• 建立數(shù)學(xué)模型來(lái)描述問(wèn)題
• 把求解的問(wèn)題分成若干個(gè)子問(wèn)題
• 對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解
• 把子問(wèn)題對(duì)應(yīng)的局部最優(yōu)解合成原來(lái)整個(gè)問(wèn)題的一個(gè)近似最優(yōu)解

?（二）相關(guān)代碼

假設(shè) 1元、2元、5元、10元、50元、100元的紙幣分別有c0，c1，c2，c3，c4，c5，c6張，現(xiàn)在要用這些錢來(lái)支付K元，至少要用多少?gòu)埣垘?#xff1f;

解題思路：

用貪心算法的思想，很顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們自然而然也是這么做的。在程序中已經(jīng)事先將Value按照從小到大的順序排好

#include<iostream>
using namespace std;
/*
假設(shè) 1元、2元、5元、10元、50元、100元的紙幣分別有c0，c1，c2，c3，c4，c5，c6張
現(xiàn)在要用這些錢來(lái)支付K元，至少要用多少?gòu)埣垘?*/int money_Type_Count[6][2] = { {1,20},{2,5},{5,10},{10,2},{50,2},{100,3} };
/*
功能:獲取支付這些錢需要紙幣的張數(shù)
參數(shù)： @金額
返回值：返回需要紙幣的張數(shù)，如果找不開(kāi)返回-1
*/
int getPaperNums(int Money)
{int num = 0;for (int i=5;i>=0;i--){int tmp = Money / money_Type_Count[i][0];tmp = tmp > money_Type_Count[i][1] ? money_Type_Count[i][1] : tmp;cout << "給你 " << money_Type_Count[i][0] << " 的紙幣" << tmp << " 張" << endl;num += tmp;Money -= tmp * money_Type_Count[i][0];}if (Money > 0) return -1;return num;
}int main()
{int money;cout << "請(qǐng)輸入金額:" << endl;;cin >> money;int num = getPaperNums(money);if (num == -1){cout << "抱歉，你的錢不夠" << endl;}else{cout << "一共給了 " << num << " 張紙幣" << endl;}
}

貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。

🚀五、分支定界法

?（一）算法思想

**精煉：**和回溯法一樣，也是一種在問(wèn)題的解空間上搜索問(wèn)題的解的方法。但與回溯算法不同，分支定界算法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方法搜索解空間樹(shù)，并且，在分支定界算法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。

1、算法步驟：

1. 產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)；
2. 在產(chǎn)生的孩子結(jié)點(diǎn)中，拋棄那些不可能產(chǎn)生可行解（或最優(yōu)解）的結(jié)點(diǎn)；
3. 將其余的孩子結(jié)點(diǎn)加入活結(jié)點(diǎn)表；
4. 從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)。

如此循環(huán)，直到找到問(wèn)題的可行解（最優(yōu)解）或活結(jié)點(diǎn)表為空。

2、從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)，根據(jù)選擇方式的不同，分支定界算法通?？梢苑譃閮煞N形式：

• FIFO(First In First Out) 分支定界算法：按照先進(jìn)先出原則選擇下一個(gè)活結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，即從活結(jié)點(diǎn)表中取出結(jié)點(diǎn)的順序與加入結(jié)點(diǎn)的順序相同。（廣度優(yōu)先的方式）
• 最小耗費(fèi)或最大收益分支定界算法：在這種情況下，每個(gè)結(jié)點(diǎn)都有一個(gè)耗費(fèi)或收益。假如要查找一個(gè)具有最小耗費(fèi)的解，那么要選擇的下一個(gè)擴(kuò)展結(jié)點(diǎn)就是活結(jié)點(diǎn)表中具有最小耗費(fèi)的活結(jié)點(diǎn)；假如要查找一個(gè)具有最大收益的解，那么要選擇的下一個(gè)擴(kuò)展結(jié)點(diǎn)就是活結(jié)點(diǎn)表中具有最大收益的活結(jié)點(diǎn)。（最小耗費(fèi)優(yōu)先的方式：A*算法）

?（二）相關(guān)代碼

布線問(wèn)題：

• 印刷電路板將布線區(qū)域劃分成n*m個(gè)方格陣列。
• 精確的電路布線問(wèn)題要求確定連接方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。
• 在布線時(shí)，電路只能沿直線或直角布線。
• 為了避免線路相交，已布了線的方格做了封鎖標(biāo)記，其他線路不允許穿過(guò)被封鎖的方格。

解題思路：

回溯法：

回溯法的搜索是依據(jù)深度優(yōu)先的原則進(jìn)行的，如果我們把上下左右四個(gè)方向規(guī)定一個(gè)固定的優(yōu)先順序去進(jìn)行搜索，搜索會(huì)沿著某個(gè)路徑一直進(jìn)行下去直到碰壁才換到另一個(gè)子路徑，但是我們最開(kāi)始根本無(wú)法判斷正確的路徑方向是什么，這就造成了搜索的盲目和浪費(fèi)。

分支定界法：

采用廣度優(yōu)先的方式，過(guò)程：

• 從起始位置a開(kāi)始將它作為第一個(gè)擴(kuò)展結(jié)點(diǎn)
• 與該結(jié)點(diǎn)相鄰并且可達(dá)的方格被加入到活緩點(diǎn)隊(duì)列中，并且將這些方格標(biāo)記為1
• 接著從活結(jié)點(diǎn)隊(duì)列中取出隊(duì)首作為下一個(gè)擴(kuò)展結(jié)點(diǎn)，并將與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰且未標(biāo)記過(guò)的方格標(biāo)記為2，并存入活節(jié)點(diǎn)隊(duì)列
• 這個(gè)過(guò)程一直繼續(xù)到算法搜索到目標(biāo)方格b或活結(jié)點(diǎn)隊(duì)列為空時(shí)為止(表示沒(méi)有通路)

1、定義小方格位置

定義一個(gè)表示電路板上小方格位置的類Position,它的兩個(gè)私有成員row和col分別表示小方格所在的行和列。

在電路板的任何一個(gè)方格處，布線可沿右、下、左、上4個(gè)方向進(jìn)行。沿這4個(gè)方向的移動(dòng)分別記為0,1，2，3。沿著這4個(gè)方向前進(jìn)一步相對(duì)于當(dāng)前方格的位移如下表所示。

2、實(shí)現(xiàn)方格陣列

用二維數(shù)組grid表示所給的方格陣列。初始時(shí)，grid[i][j]=0，表示該方格允許布線，而grid[i][j]=1表示該方格被封鎖，不允許布線。

為了便于處理方格邊界的情況，算法在所給方格陣列四周設(shè)置一圈標(biāo)記為“1”的附加方格，即可識(shí)別方陣邊界。

3、初始化

算法開(kāi)始時(shí)，測(cè)試初始方格與目標(biāo)方格是否相同。如果相同，則不必計(jì)算，直接放回最短距離0，否則算法設(shè)置方格陣列的邊界，初始化位移矩陣offset。

4、算法搜索步驟

算法從start開(kāi)始，標(biāo)記所有標(biāo)記距離為1的方格并存入活結(jié)點(diǎn)隊(duì)列，然后依次標(biāo)記所有標(biāo)記距離為2,3…的方格，直到到達(dá)目標(biāo)方格finish或活結(jié)點(diǎn)隊(duì)列為空時(shí)為止

/*
布線問(wèn)題：如圖1所示，印刷電路板將布線區(qū)域劃分成n*m個(gè)方格。
精確的電路布線問(wèn)題要求確定連接方格a的中點(diǎn)到b的中點(diǎn)的布線方案。
在布線時(shí)，電路只能沿直線或直角布線，
所示。為了避免線路相交，已經(jīng)布線的方格做了封鎖標(biāo)記（如圖1中陰影部分）
，其他線路不允許穿過(guò)被封鎖的方格。
*/#include <iostream>
#include <queue>
#include <list>
using namespace std;
typedef struct _Pos
{int x, y;struct _Pos* parent;
}Pos;int Move[4][2] = { 0,1,0,-1,-1,0,1,0 };
queue<Pos*> bound;void inBound(int x,int y,int rows,int cols, Pos * cur,bool *visited,int *map);Pos *Findpath(int *map,Pos start, Pos end,int rows,int cols)
{Pos *tmp = new Pos;tmp->x = start.x;tmp->y = start.y;tmp->parent = NULL;if (tmp->x == end.x && tmp->y == end.y &&tmp->y == end.y)return tmp;bool *visited = new bool[rows*cols];memset(visited, 0, rows*cols);visited[tmp->x*rows + tmp->y] = true;inBound(tmp->x, tmp->y, rows, cols,tmp,visited,map);while (!bound.empty()){Pos * cur = bound.front();if (cur->x == end.x && cur->y == end.y)return cur;bound.pop();inBound(cur->x, cur->y, rows, cols, cur,visited,map);}return NULL;//代表沒(méi)有路徑
}
void inBound(int x, int y, int rows, int cols,Pos*cur,bool *visited, int *map)
{for (int i = 0; i < 4; i++){Pos *tmp = new Pos;tmp->x = x + Move[i][0];tmp->y = y + Move[i][1];tmp->parent = cur;if (tmp->x >= 0 && tmp->x < rows && tmp->y >= 0 && tmp->y < cols && !visited[tmp->x*rows + tmp->y] && map[tmp->x*rows + tmp->y]!=1){bound.push(tmp);visited[tmp->x*rows + tmp->y] = true;}	elsedelete tmp;}
}list<Pos *> getPath(int *map, Pos start, Pos end, int rows, int cols)
{list<Pos*> tmp;Pos * result = Findpath(map, start, end, rows, cols);while (result!=NULL && result->parent!=NULL){tmp.push_front(result);result = result->parent;}return tmp;
}int main()
{int map[6][6] ={0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0 };Pos start = { 1,1,0 };Pos end = { 4,4,0 };list<Pos*> path = getPath(&map[0][0], start,end,6, 6);cout << "路徑為:" << endl;for (list<Pos*>::const_iterator it=path.begin();it!=path.end();it++){cout << "(" << (*it)->x << "," << (*it)->y << ")" << endl;}system("pause");}