布線問題

布線問題-分支限界法

問題描述
印刷電路板不限區域劃分成n*m個方格陣列。如下圖所示

分支限界法類似於回溯法，也是在問題的解空間上搜索問題的解的算法。分支限界法是找出滿足約束條件的一個解或者滿足某種條件的最優解。分支限界法則以廣度優先或者最小耗費優先的方式搜索解空間。

其搜索策略是：

1、在擴展結點處，先生成其所有的兒子結點，然後再從當前的活結點表中選擇下一個擴展結點。

2、為了加速搜索的進程，在每一個活結點處，計算一個函數值，並根據函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著最有利的分支推進。

分支限界的思想主要體現在第二點上。

從活結點表中選擇下一個擴展結點的不同方式導致不同的分支限界法，最常見的有以下兩種

隊列式分支限界法 優先隊列式分支限界法

算法描述

bool FindPath(Position start,Position finish,int& PathLen,Position * &path)
{
    //計算從起始位置start到目標位置finish的最短路線
    //找到最短布線路徑返回true，否則返回false
    if((start.row == finish.row)&&(start.col == finish.col))
    {
        PathLen = 0;
        return true;
    }
    //設置方格陣列的圍牆
    for(int i=0;i<=m+1;i++)
    {
        grid[0][i] = grid[n+1][i] = 1;//頂部和底部
    }
    for(int i=0;i<=n+1;i++)
    {
        grid[i][0] = grid[i][m+1] = 1;//左側和右側
    }
    Position offset[4];
    offset[0].row = 0;    offset[0].col = 1;//右
    offset[1].row = 1;    offset[1].col = 0;//下
    offset[2].row = 0;    offset[2].col = -1;//左
    offset[3].row = -1;    offset[3].col = 0;//上

    int NumOfNbs = 4;//相鄰方格數
    Position here,nbr;
    here.row = start.row;
    here.col = start.col;
    grid[start.row][start.col] = 2;
    //標記可達方格的位置
    LinkedQueue Q;
    do
    {
        for(int i=0;i=0 ; j--)
    {
        path[j] = here;
        //找前驅位置
        for(int 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 true;
}

下面結合布線問題來體會分支限界的思想：代碼
李超的參考

---

---

算法實現

#include
#include
using namespace std;

//表示方格上位置的結構體
struct Position
{
    int row;
    int col;
};

//分支限界算法
bool FindPath(Position start,Position finish,int& PathLen,Position *&path,int **grid,int m,int n)
{
    //找到最短布線路徑，則返回真，否則返回假

    //起點和終點想同，不用布線
    if((start.row==finish.row) && start.col==finish.col)
    {
        PathLen=0;
        return true;
    }


    //設置方向移動坐標值：東、南、西、北
    Position offset[4];
    offset[0].row=0;
    offset[0].col=1;    //右
    offset[1].row=1;
    offset[1].col=0;    //下
    offset[2].row=0;
    offset[2].col=-1;   //左
    offset[3].row=-1;
    offset[3].col=0;    //上

    //相鄰的方格數
    int NumNeighBlo=4;
    Position here,nbr;
    //設置當前方格，即搜索單位
    here.row=start.row;
    here.col=start.col;
    //由於0和1用於表示方格的開放和封鎖，故距離：2-0 3-1
    grid[start.row][start.col]=0;

    //隊列式搜索，標記可達相鄰方格
    queue q_FindPath;

    do
    {
        for(int i=0; i=0; j--)
    {
        path[j]=here;
        //找前驅位置
        for (int i = 0; i <=NumNeighBlo; 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 true;
}

int main()
{
    cout<<"---------分支限界法之布線問題--------"<>m>>n;

    //創建棋盤格
    int **grid = new int*[m+2];
    for(int i=0; i < m+2; i++)
    {
        grid[i] = new int[n+2];
    }
//初始化棋盤格
    for(int i=1; i <= m; i++)
    {
        for(int j=1; j <=n; j++)
        {
            grid[i][j]=-1;
        }
    }
       //設置方格陣列的圍牆
    for(int i=0; i<=n+1; i++)
        grid[0][i]=grid[m+1][i]=-2;//上下的圍牆

    for(int i=0; i<=m+1; i++)
        grid[i][0]=grid[i][n+1]=-2;//左右的圍牆

    cout<<"初始化棋盤格和加圍牆"<>ci>>cj;
        if(ci>m||cj>n)
        {
            cout<<"輸入非法！！！！！";
            cout<<"行坐標 < "<