算法詳解之分支限界法的具體實現(xiàn)
首先我們來關注一個問題：
問題描述：
布線問題：印刷電路板將布線區(qū)域劃分成n×m個方格陣列，要求確定連接方格陣列中的方格a的中點到方格b的中點的最短布線方案。在布線時，電路只能沿直線或直角布線，為了避免線路相交，已布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的方格。如下圖所示：
算法思路：
布線問題的解空間是一個圖，則從起始位置a開始將它作為第一個擴展結(jié)點。與該擴展結(jié)點相鄰并可達的方格成為可行結(jié)點被加入到活結(jié)點隊列中，并且將這些方格標記為1，即從起始方格a到這些方格的距離為1。接著，從活結(jié)點隊列中取出隊首結(jié)點作為下一個擴展結(jié)點，并將與當前擴展結(jié)點相鄰且未標記過的方格標記為2，并存入活結(jié)點隊列。這個過程一直繼續(xù)到算法搜索到目標方格b或活結(jié)點隊列為空時為止。
在實現(xiàn)上述算法時，
（1） 定義一個表示電路板上方格位置的類Position。
它的2個成員row和col分別表示方格所在的行和列。在方格處，布線可沿右、下、左、上4個方向進行。沿這4個方向的移動分別記為0，1，2，3。下表中，offset[i].row和offset[i].col(i= 0,1,2,3)分別給出沿這4個方向前進1步相對于當前方格的相對位移。
（2） 用二維數(shù)組grid表示所給的方格陣列。
初始時，grid[i][j] = 0, 表示該方格允許布線，而grid[i][j] = 1表示該方格被封鎖，不允許布線。
算法圖解：
代碼貼出來：
#include <stdio.h>
typedef struct {
int row;
int col;
}Position;
int FindPath (Position start, Position finish, int &PathLen, Position *&path)
{ //計算從起始位置start到目標位置finish的最短布線路徑，找到返回1，否則，返回0
int i;
if ((start.row = = finish.row) && (start.col = = finish.col)) {
PathLen = 0; return 0; } //start = finish
//設置方格陣列”圍墻”
for (i = 0; i <= m+1; i++)
grid[0][i] = grid[n+1][i] = 1; //頂部和底部
for (i = 0; i <= n+1; i++)
grid[i][0] = grid[i][m+1] = 1; //左翼和右翼
//初始化相對位移
int NumOfNbrs = 4; //相鄰方格數(shù)
Position offset[4], here, nbr;
offset[0].row = 0; offset[0].col = 1; //右
offset[0].row = 1; offset[0].col = 0; //下
offset[0].row = 0; offset[0].col = -1; //左
offset[0].row = -1; offset[0].row = 0; //上
here.row = start.row;
here.col = start.col;
LinkedQueue <Position> Q; //標記可達方格位置
do {
for (i = 0; i< NumOfNbrs; i++) { //標記可達相鄰方格
nbr.row = here.row + offset[i].row ;
nbr.col = here.col + offset[i].col;
if (grid[nbr.row][nbr.col] = = 0) { //該方格未標記
grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;
if ((nbr.row = = finish.row) && (nbr.col = = finish.col)) break;//完成布線
Q.Add(nbr);
}
}
if ((nbr.row = = finishi.row) && (nbr.col = = finish.col)) break;//完成布線
if (Q.IsEmpty()) //活隊列是否為空
return 0; //無解
Q.delete(here); //取下一個擴展結(jié)點
}while (1);
//構(gòu)造最短布線路徑
PathLen = grid[finish.row][finish.col] － 2;
path = new Position[PathLen];
here = finish;
for (int j = PathLen – 1; j >= 0; j--) { //找前驅(qū)位置
path[j] = here;
for (i = 0; i< NumOfNbrs; i++) {
nbr.row = here.row + offset[i].row ;
nbr.col = here.col + offset[i].col;
if (grid[nbr.row][nbr.col] = = j+2) break;
}
here = nbr; //向前移動
}
return 1;
}
void main ()
{
int grid[8][8];
int PathLen, *path;
Position start, finish;
start.row = 3; start.col = 2;
finish.row = 4; finish.col = 6;
FindPath (start, finish, PathLen, path);
}
代碼貼出來：
#include <stdio.h>
typedef struct {
int row;
int col;
}Position;
int FindPath (Position start, Position finish, int &PathLen, Position *&path)
{ //計算從起始位置start到目標位置finish的最短布線路徑，找到返回1，否則，返回0
int i;
if ((start.row = = finish.row) && (start.col = = finish.col)) {
PathLen = 0; return 0; } //start = finish
//設置方格陣列”圍墻”
for (i = 0; i <= m+1; i++)
grid[0][i] = grid[n+1][i] = 1; //頂部和底部
for (i = 0; i <= n+1; i++)
grid[i][0] = grid[i][m+1] = 1; //左翼和右翼
//初始化相對位移
int NumOfNbrs = 4; //相鄰方格數(shù)
Position offset[4], here, nbr;
offset[0].row = 0; offset[0].col = 1; //右
offset[0].row = 1; offset[0].col = 0; //下
offset[0].row = 0; offset[0].col = -1; //左
offset[0].row = -1; offset[0].row = 0; //上
here.row = start.row;
here.col = start.col;
LinkedQueue <Position> Q; //標記可達方格位置
do {
for (i = 0; i< NumOfNbrs; i++) { //標記可達相鄰方格
nbr.row = here.row + offset[i].row ;
nbr.col = here.col + offset[i].col;
if (grid[nbr.row][nbr.col] = = 0) { //該方格未標記
grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;
if ((nbr.row = = finish.row) && (nbr.col = = finish.col)) break;//完成布線
Q.Add(nbr);
}
}
if ((nbr.row = = finishi.row) && (nbr.col = = finish.col)) break;//完成布線
if (Q.IsEmpty()) //活隊列是否為空
return 0; //無解
Q.delete(here); //取下一個擴展結(jié)點
}while (1);
//構(gòu)造最短布線路徑
PathLen = grid[finish.row][finish.col] － 2;
path = new Position[PathLen];
here = finish;
for (int j = PathLen – 1; j >= 0; j--) { //找前驅(qū)位置
path[j] = here;
for (i = 0; i< NumOfNbrs; i++) {
nbr.row = here.row + offset[i].row ;
nbr.col = here.col + offset[i].col;
if (grid[nbr.row][nbr.col] = = j+2) break;
}
here = nbr; //向前移動
}
return 1;
}
void main ()
{
int grid[8][8];
int PathLen, *path;
Position start, finish;
start.row = 3; start.col = 2;
finish.row = 4; finish.col = 6;
FindPath (start, finish, PathLen, path);
}
好了，問題解出來了。咦，我們用的是什么方法呢？呵呵，對，這就是分支限界算法。
算法總結(jié)：
分支限界法基本思想：
• 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。
• 在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。
• 在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。
• 此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。
分支限界法與回溯法的不同：
（1）求解目標不同：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。
（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。
您可能感興趣的文章
- 01-10求子數(shù)組最大和的解決方法詳解
- 01-10深入二叉樹兩個結(jié)點的最低共同父結(jié)點的詳解
- 01-10數(shù)據(jù)結(jié)構(gòu)課程設計- 解析最少換車次數(shù)的問題詳解
- 01-10數(shù)據(jù)結(jié)構(gòu)課程設計-用棧實現(xiàn)表達式求值的方法詳解
- 01-10HDOJ 1443 約瑟夫環(huán)的最新應用分析詳解
- 01-10使用C++實現(xiàn)全排列算法的方法詳解
- 01-10如何查看進程實際的內(nèi)存占用情況詳解
- 01-10深入Main函數(shù)中的參數(shù)argc,argv的使用詳解
- 01-10APUE筆記之:進程環(huán)境詳解
- 01-10深入第K大數(shù)問題以及算法概要的詳解
閱讀排行
本欄相關
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機閱讀
- 01-10delphi制作wav文件的方法
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-10C#中split用法實例總結(jié)
- 08-05織夢dedecms什么時候用欄目交叉功能？
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-11ajax實現(xiàn)頁面的局部加載
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-10SublimeText編譯C開發(fā)環(huán)境設置
- 04-02jquery與jsp,用jquery