算法设计--电路布线问题（分支限界法求解）

电路布线问题--分支限界法求解

一 问题描述：

布线问题：印刷电路板将布线区域划分成n×m个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。

二 算法应用：

用分支限界法解此布线问题。分支限界法类似回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但分支限界法只找出满足约束条件的一个最优解，并且以广度优先或最小耗费优先的方式搜索解空间树T。树T是一棵子集树或排列树。在搜索时，每个结点只有一次机会成为扩展结点，并且一次性产生其所有儿子结点。从活结点表中选择下一扩展结点有两种方式：（1）队列式（FIFO） （2）优先队列式。分支限界法广泛应用于单源最短路径问题，最大团问题，布线问题，电路板排列问题等。

三 求解思路：

用队列式分支限界法来考虑布线问题。布线问题的解空间是一个图，则从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。

四 算法思路：

在实现上述算法时，

（1）定义一个表示电路板上方格位置的类Position。

它的2个成员row和col分别表示方格所在的行和列。在方格处，布线可沿右、下、左、上4个方向进行。沿这4个方向的移动分别记为0，1，2，3。下表中，offset[i].row和offset[i].col(i= 0,1,2,3)分别给出沿这4个方向前进1步相对于当前方格的相对位移。

移动i	方向	offset[i].row	offset[i].col
0 1 2 3	右 下 左 上	0 1 0 -1	1 0 -1 0

（2）用二维数组grid表示所给的方格阵列。

初始时，grid[i][j]= 0, 表示该方格允许布线，而grid[i][j]= 1表示该方格被封锁，不允许布线。

五 举例说明：

一个7×7方格阵列布线如下：

起始位置是a =(3,2),目标位置是b =(4,6),阴影方格表示被封锁的方格。当算法搜索到目标方格b时，将目标方格b标记为从起始位置a到b的最短距离。此例中， a到b的最短距离是9。

代码转自http://blog.csdn.net/ei__nino/article/details/8195906

#include <iostream>
#include <queue>
using namespace std;
int m=8;
int n=8;
int grid[10][10];
int indexcount=0;

struct Position
{
    int row;
    int col;
};
void showPath()
{
    for(int i=0; i<10; i++)
    {

        for(int j=0; j<10; j++)
            cout<<grid[i][j]<<" ";
        cout<<endl;
    }
    cout<<"------------------"<<endl;
}
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;
        cout<<"start=finish"<<endl;
        return true;
    } //start=finish
//设置方格阵列“围墙”
//初始化图，-1为未访问
    for(int i=1; i<9; i++)
    {
        for(int j=1; j<9; j++)
            grid[i][j]=-1;

    }
    //添加阻挡点
     grid[2][3]=-2;
    for(int i=0; i<= m+1; i++)
        grid[0][i]=grid[n+1][i]=-2; //顶部和底部
    for(int i=0; i<= n+1; i++)
        grid[i][0]=grid[i][m+1]=-2; //左翼和右翼
//初始化相对位移
    cout<<"完整图"<<endl;
    showPath();
    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 NumOfNbrs=4;//相邻方格数
    Position here,nbr;
    here.row=start.row;
    here.col=start.col;
    grid[start.row][start.col]=0;
//标记可达方格位置
cout<<"布线前图"<<endl;
    showPath();

    queue<Position> Q;
    do  //标记相邻可达方格
    {
        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]==-1)
            {
//该方格未被标记
                //cout<<grid[nbr.row][nbr.col]<<endl;//显示路标值
                grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
                 //cout<<nbr.col<<"   "<<nbr.row<<endl;//显示坐标
            }
            if((nbr.row==finish.row) &&(nbr.col==finish.col)) break; //完成布线
            Q.push(nbr);


        }
//是否到达目标位置finish？
        if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布线
//活结点队列是否非空？
        if(Q.empty()) return false;//无解
        here = Q.front();
        //cout<<here.col<<" "<<here.row<<endl;
        Q.pop();//取下一个扩展结点


        indexcount++;
       // cout<<"下一节点"<<indexcount<<endl;
    }
    while(true);
//构造最短布线路径
    PathLen=grid[finish.row][finish.col];
    path=new Position[PathLen];
//从目标位置finish开始向起始位置回溯
    here=finish;
    for(int j=PathLen-1; j>=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)
            {
               // cout<<j<<endl;
                break;
            }
        }
        here=nbr;//向前移动
    }
    return PathLen;
}
int main()
{
    Position start;
    start.col=1;
    start.row=1;
 cout<<"布线起点"<<endl;
 cout<<start.col<<" "<<start.row<<endl;
    Position finish;
    finish.row=3;
    finish.col=4;
     cout<<"布线结束点"<<endl;
      cout<<finish.col<<" "<<finish.row<<endl;
    int PathLen=0;
    Position *path;

    FindPath(start,finish,PathLen,path);
    cout<<"布线后路径图"<<endl;
    showPath();
    cout<<"路径"<<endl;
    for(int i=0; i<PathLen; i++)
    {
        cout<<path[i].col<<" "<<path[i].row<<endl;
    }
    cout << "布线问题完毕!" << endl;

	system("pause");
    return 0;
}