如何創(chuàng)辦視頻網(wǎng)站媒體平臺(tái)
文章目錄
- 🚀一、分治法
- ?(一)算法思想
- ?(二)相關(guān)代碼
- 🚀二、動(dòng)態(tài)規(guī)劃算法
- ?(一)算法思想
- ?(二)相關(guān)代碼
- 🚀三、回溯算法
- ?(一)算法思想
- ?(二)相關(guān)代碼
- 🚀四、貪心算法
- ?(一)算法思想
- ?(二)相關(guān)代碼
- 🚀五、分支定界法
- ?(一)算法思想
- ?(二)相關(guān)代碼
🚀一、分治法
?(一)算法思想
精煉:將一個(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)找出那枚偽造的硬幣
常規(guī)解決辦法:
每次拿出兩枚硬幣比重量,只到遇到兩枚硬幣重量不等時(shí),重量更輕的那枚就是假幣。這題這樣比最多需要比8次,更多硬幣就更耗時(shí),時(shí)間復(fù)雜度位:O(n)
分治思維解題:
我們先將 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ì)算,從而提高算法效率。
具體步驟:
- 判題題意是否為找出一個(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)的求解)
什么時(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、算法步驟:
- 產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有孩子結(jié)點(diǎn);
- 在產(chǎn)生的孩子結(jié)點(diǎn)中,拋棄那些不可能產(chǎn)生可行解(或最優(yōu)解)的結(jié)點(diǎn);
- 將其余的孩子結(jié)點(diǎn)加入活結(jié)點(diǎn)表;
- 從活結(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");}