目錄
一导俘、分治法
思想原理
具體步驟
例題1
算法結(jié)語(yǔ)
二、動(dòng)態(tài)規(guī)劃算法
思想原理
具體步驟
算法實(shí)現(xiàn)
算法結(jié)語(yǔ)
三葛超、回溯算法
? ? ? ? 算法思想
? ? ? ? 基本步驟
? ? ? ? 例題2
? ? ? ? 算法實(shí)現(xiàn)
算法結(jié)語(yǔ)
四驳遵、貪心算法
? ? ? ? 思想原理
基本步驟
例題3
算法實(shí)現(xiàn)
算法結(jié)語(yǔ)
五厅贪、分支定界法
? ? ? ? 算法原理
算法步驟
例題
算法實(shí)現(xiàn)
算法結(jié)語(yǔ)
寫(xiě)在前面：
很多人在刷了很多題之后依然無(wú)法解決陌生題型或解題十分困難，有很大一部分原因是沒(méi)有擁有核心算法思維伺通。在此本人將自己的學(xué)習(xí)成果分享給大家箍土，文章將由淺入深講解五大核心算法原理以及應(yīng)用，對(duì)于初級(jí)程序員罐监，閱讀此文吴藻，不論對(duì)解題或者開(kāi)發(fā)都有很大幫助。本人代碼功力可能稍淺弓柱，望諸君大牛多一分包容與理解沟堡。
一、分治法
思想原理
分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問(wèn)題矢空，分割成一些規(guī)模較小的相同問(wèn)題航罗，以便各個(gè)擊破，分而治之屁药。
分治策略是：對(duì)于一個(gè)規(guī)模為n的問(wèn)題粥血，若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模n較小）則直接解決酿箭，否則將其分解為k個(gè)規(guī)模較小的子問(wèn)題立莉，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題七问，然后將各子問(wèn)題的解合并得到原問(wèn)題的解蜓耻。這種算法設(shè)計(jì)策略叫做分治法。
簡(jiǎn)單來(lái)講械巡，分治法就是把大問(wèn)題化解成小問(wèn)題刹淌。
下面通過(guò)一個(gè)生活中的例子來(lái)理解該思想
問(wèn)：一個(gè)裝有 16 枚硬幣的袋子饶氏，16 枚硬幣中有一個(gè)是偽造的，偽造的硬幣和普通硬幣從表面上看不出有任何差別有勾，但是那 個(gè)偽造的硬幣比真的硬幣要輕≌钇簦現(xiàn)有給你一臺(tái)天平，請(qǐng)你在盡可能最短的時(shí)間內(nèi)找出那枚偽造的硬幣
常規(guī)解決辦法可能是每次拿出兩枚硬幣比重量蔼卡，只到遇到兩枚硬幣重量不等時(shí)喊崖，重量更輕的那枚就是假幣。這題這樣比最多需要比8次雇逞。時(shí)間復(fù)雜度:O(n/2)
分治思維解題：我們先將 16 枚硬幣分為左右兩個(gè)部分荤懂，各為 8 個(gè)硬幣，分別稱(chēng)重塘砸，必然會(huì)有一半輕一半重节仿，而我們要的就是輕的那組,重的舍去。接下來(lái)我們繼續(xù)對(duì)輕的進(jìn)行五五分掉蔬，直至每組剩下一枚或者兩枚硬幣廊宪，這時(shí)我們的問(wèn)題自然就解決了
使用分治法此題需要比4次。時(shí)間復(fù)雜度:O(log2 n)? 女轿，分治法的效率是可見(jiàn)的箭启，如果基數(shù)加大效率提升將會(huì)大大提高。
具體步驟
兩部分組成
分（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)題的解。
可用分治法解決的經(jīng)典問(wèn)題之一就是二分查找了
二分查找算法實(shí)現(xiàn)
#include <iostream>
using namespace std;
/*
功能:遞歸實(shí)現(xiàn)二分查找
參數(shù):
@arr - 有序數(shù)組地址
@minSub - 查找范圍的最小下標(biāo)
@maxSub - 查找范圍的最大下標(biāo)
@num - 帶查找數(shù)字
返回:找到則返回所在數(shù)組下標(biāo)膛壹，找不到則返回-1
*/
int BinarySearch(int *arr, int minSub, int maxSub, int num)
{
if (minSub > maxSub) return -1;
int mid = (maxSub + minSub) / 2;
if (arr[mid] == num) return mid;
else if (arr[mid] < num) return BinarySearch(arr, mid + 1, maxSub, num);
else return? BinarySearch(arr, minSub, mid - 1, num);
}
int main()
{
int arr[] = { 1,9,11,22,69,99,100,111,999,8888 };
cout << "輸入你要查找的數(shù)：" << endl;
int num;
cin >> num;
int index = BinarySearch(arr, 0, 9, num);
if (index == -1)
{
cout << "Not found!";
}
else
{
cout << "數(shù)的下標(biāo)：" << index << ", 值：" << arr[index] << endl;
}
}
例題1
例題一：
如果機(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è)情況：
1祟蚀、 機(jī)器人最后一次走了兩級(jí)臺(tái)階工窍，問(wèn)題變成了“走上一個(gè) 3 級(jí)臺(tái)階割卖，有多少種走法？”
2患雏、 機(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)
/*遞歸實(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é)語(yǔ)
總體來(lái)講，分治法思維較為簡(jiǎn)單怀吻，因?yàn)榉纸馑季S存在瞬浓，常常需要使用遞歸初婆、循環(huán)等蓬坡，常見(jiàn)的使用分治法思維的問(wèn)題有：合并排序、快速排序磅叛、漢諾塔問(wèn)題屑咳、大整數(shù)乘法等。
二弊琴、動(dòng)態(tài)規(guī)劃算法
思想原理
問(wèn)題的最優(yōu)解如果可以由子問(wèn)題的最優(yōu)解推導(dǎo)得到兆龙，則可以先求解子問(wèn)題的最優(yōu)解，在構(gòu)造原問(wèn)題的最優(yōu)解敲董；若子問(wèn)題有較多的重復(fù)出現(xiàn)紫皇，則可以自底向上從最終子問(wèn)題向原問(wèn)題逐步求解。
具體步驟
分析優(yōu)化解的結(jié)構(gòu)
遞歸地定義最優(yōu)解的代價(jià)
自底向上地計(jì)算優(yōu)化解的代價(jià)保存之腋寨，并獲取構(gòu)造最優(yōu)解的信息
根據(jù)構(gòu)造最優(yōu)解的信息構(gòu)造優(yōu)化解
動(dòng)態(tài)規(guī)劃特點(diǎn)
把原始問(wè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)題稱(chēng)為狀態(tài)键兜，最終狀態(tài)的求解歸結(jié)為其他狀態(tài)的求解）
現(xiàn)在請(qǐng)大家回頭看一下例題一，上面的代碼中存在很多重復(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ì)算的一部分普气！
下面使用動(dòng)態(tài)規(guī)劃與分治法實(shí)現(xiàn)
算法實(shí)現(xiàn)
#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);
int *values=new int[steps+1];
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;
}
算法結(jié)語(yǔ)
動(dòng)態(tài)規(guī)劃和分治法思想較為相似茎截，都涉及將問(wèn)題化解為子問(wèn)題求解，但動(dòng)態(tài)規(guī)范強(qiáng)調(diào)的是重復(fù)赶盔，當(dāng)你看到或意識(shí)到可分為多個(gè)相關(guān)子問(wèn)題企锌，子問(wèn)題的解被重復(fù)使用時(shí)，就要考慮使用動(dòng)態(tài)規(guī)劃了于未。
三撕攒、回溯算法
算法思想
回溯算法實(shí)際上一個(gè)類(lèi)似枚舉的搜索嘗試過(guò)程，主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解烘浦，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)抖坪，就“回溯”返回，嘗試別的路徑闷叉。
如果嘗試求解的空間是一棵樹(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é)束衍菱。
基本步驟
1. 定義問(wèn)題的解空間
2. 確定易于搜索的解空間結(jié)構(gòu)
3. 以深度優(yōu)先搜索的策略搜索解空間赶么，并在搜索過(guò)程中盡可能避免無(wú)效搜索
例題2
例題2：
請(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è)問(wèn)題相當(dāng)經(jīng)典恰力，難度適中，建議先獨(dú)立思考旗吁。
解題思路：
首先踩萎，在矩陣中任選一個(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è)癣丧，然后重新定位槽畔。
算法實(shí)現(xiàn)?
#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;
else
cout << "matrix中不存在 " << str << " 字符串的路徑" << endl;
}
算法結(jié)語(yǔ)
回溯算法常常用在包含問(wèn)題的所有解的解空間樹(shù)中雀扶，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹(shù)肆汹。
四愚墓、貪心算法
思想原理
貪心算法（又稱(chēng)貪婪算法）是指予权，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇浪册。也就是說(shuō)扫腺，不從整體最優(yōu)上加以考慮，算法得到的是在某種意義上的局部最優(yōu)解 [1]? 村象。
貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解斧账，關(guān)鍵是貪心策略的選擇（百度百科）
基本步驟
? 建立數(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)解
例題3
假設(shè) 1元煞肾、2元咧织、5元、10元籍救、50元习绢、100元的紙幣分別有c0，c1蝙昙，c2闪萄，c3，c4奇颠，c5败去，c6張
現(xiàn)在要用這些錢(qián)來(lái)支付K元，至少要用多少?gòu)埣垘牛?/p>
這是一個(gè)貪心算法最最經(jīng)典例題烈拒，用貪心算法思想每次都找最好的結(jié)果圆裕，顯然每次都要選面值最大的紙幣
算法實(shí)現(xiàn)
#include<iostream>
using namespace std;
/*
假設(shè) 1元、2元荆几、5元吓妆、10元、50元吨铸、100元的紙幣分別有c0行拢，c1，c2诞吱，c3舟奠，c4，c5房维，c6張
現(xiàn)在要用這些錢(qián)來(lái)支付K元沼瘫，至少要用多少?gòu)埣垘?/p>
*/
int money_Type_Count[6][2] = { {1,20},{2,5},{5,10},{10,2},{50,2},{100,3} };
/*
功能:獲取支付這些錢(qián)需要紙幣的張數(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 << "抱歉握巢，你的錢(qián)不夠" << endl;
}
else
{
cout << "一共給了 " << num << " 張紙幣" << endl;
}
}
算法結(jié)語(yǔ)
貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解晕鹊。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解溅话。
五晓锻、分支定界法
算法原理
分支定界法（branch and bound）是一種求解整數(shù)規(guī)劃問(wèn)題的最常用算法。這種方法不但可以求解純整數(shù)規(guī)劃飞几，還可以求解混合整數(shù)規(guī)劃問(wèn)題砚哆。分支定界法是一種搜索與迭代的方法，選擇不同的分支變量和子問(wèn)題進(jìn)行分支屑墨。(百度百科)
分支定界 (branch and bound) 算法是一種在問(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)槐秧；
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)表為空膀懈。
例題
布線問(wèn)題：
如圖所示，印刷電路板將布線區(qū)域劃分成n*m個(gè)方格谨垃。精確的電路布線問(wèn)題要求確定連接方格a的中點(diǎn)到b的中點(diǎn)的布線方案启搂。在布線時(shí)，電路只能沿直線或直角布線乘客，如圖1所示狐血。為了避免線路相交淀歇，已經(jīng)布線的方格做了封鎖標(biāo)記（如圖1中陰影部分）易核，其他線路不允許穿過(guò)被封鎖的方格。
解題思路：
題目的要求是找到最短的布線方案浪默，從圖的情況看牡直，可以用貪婪算法解決問(wèn)題，也就是從a開(kāi)始朝著b的方向垂直布線即可纳决。實(shí)際上碰逸，貪婪算法策略是行不通的。因?yàn)橐巡季€的放個(gè)沒(méi)有規(guī)律的所以直觀上說(shuō)只能用搜索方法去找問(wèn)題的解阔加。
根據(jù)布線方法的要求饵史，除邊界或已布線處进宝，每個(gè)結(jié)點(diǎn)分支擴(kuò)充的方向有4個(gè)：上、下眯勾、左席吴、右，也就是說(shuō)吭露，一個(gè)結(jié)點(diǎn)擴(kuò)充后最多產(chǎn)生4個(gè)活結(jié)點(diǎn)吠撮。
搜索以a為第一個(gè)結(jié)點(diǎn)，以后不斷擴(kuò)充新的活結(jié)點(diǎn)讲竿，直到b結(jié)束（當(dāng)然反之也可以）泥兰。反過(guò)來(lái)從b到a，按序號(hào)8-7-6-5-4-3-2-1就可以找到最短的布線方案题禀。從圖3中也可以發(fā)現(xiàn)最短的布線方案是不唯一的鞋诗。且由此可以看出，此問(wèn)題適合用分支限界搜索迈嘹。
算法實(shí)現(xiàn)?
注：代碼有內(nèi)存泄露师脂，本人已注意到這點(diǎn)，為了很好地展示算法邏輯江锨，并沒(méi)有處理吃警。
/*
布線問(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;
}
else
delete 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");
}
則代表了路徑
算法結(jié)語(yǔ)
算法按照先進(jìn)先出原則選擇下一個(gè)活結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，即從活結(jié)點(diǎn)表中取出結(jié)點(diǎn)的順序與加入結(jié)點(diǎn)的順序相同铝阐。
從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)址貌，根據(jù)選擇方式的不同，分支定界算法還有? 最小耗費(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)。
博文結(jié)語(yǔ)
五大核心算法對(duì)于面試它呀、解題螺男、開(kāi)發(fā)過(guò)程中的作用是巨大的棒厘，然而這種思維影響往往是很直觀體現(xiàn)。本文旨在拋磚引玉下隧。程序員大牛們勢(shì)必掌握更多算法思維绊谭，核心算法早已爛熟于心，因此在常規(guī)開(kāi)發(fā)和創(chuàng)新開(kāi)發(fā)上效率往往很高汪拥。如果此文對(duì)你有所幫助达传，請(qǐng)一鍵三連支持一下吧！博主與將你共同進(jìn)步迫筑！
https://blog.csdn.net/weixin_40582034/article/details/119287571?utm_source=app&app_version=4.8.1
