分支限界法

分支限界法之布线问题

 

一、要求：

    1、输入电路板区域n*m以及布线的起始位置和结束位置；

    2、输出布线方案；

    3、可以使用c或者vc实现

    二、问题分析及实验原理：

    在n*m的方格阵列中存在封锁区域（布线时必须绕开的区域），找到起始位置到目标位置的最短路径。从目标位置开始向起始位置回溯，逐步构造最优解。每次向标记距离比当前方格标记距离少1的相邻方格移动，直到到达起始方格为止。

    三、算法程序源代码：

    #include <iostream>

    #include<stdio.h>

    using namespace std;

    typedef struct

    {

    int row ;

    int col ;

    }Position;

    typedef struct

    {

    //struct Position;

    int row[10000] ;

    int col[10000] ;

    int end;

    int begin ;

    }Queue;

    int grid[100][100];

    Position start, finish;

    int PathLen = 0;

    Position * path;

    int n , m , a , b , x ;

    bool FindPath(Position start,Position finish)

    {//计算从起点位置start到目标位置finish的最短布线路径，找到最短布线路//径则返回true，否则返回false

    if((start.row==finish.row) && (start.col==finish.col))

    {

    PathLen=0;

    return true;

    } //start=finish

    //设置方格阵列“围墙”

    int i ;

    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 j ;

    //初始化相对位移

    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]=2;

    //标记可达方格位置

    //LinkedQueue<Position> Q;

    Queue Q ;

    Q.end = 0 ;

    Q.begin = 0 ;

    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);

    Q.col[Q.end] = nbr.col;

    Q.row[Q.end] = nbr.row;

    Q.end++;

    }

    }

    //是否到达目标位置finish？

    if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布线

    //活结点队列是否非空？

    if(Q.begin==Q.end) return false;//无解

    else

    {

    here.row=Q.row[Q.begin];

    here.col=Q.col[Q.begin];

    Q.begin++;//取下一个扩展结点

    }

    }while(true);

    //构造最短布线路径

    PathLen=grid[finish.row][finish.col]-2;

    path=new Position[PathLen];

    //从目标位置finish开始向起始位置回溯

    here=finish;

    for( j = PathLen-1; j>=0; j--){

    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 true;

    }

    int main()

    {

    int j ;

    printf("输入电路板区域n*m和封锁的格数x:\n");

    cin>>n>>m>>x;

    printf("输入封锁的坐标:\n");

    for( a = 0 ; a < n+2 ; a ++ )

    for( b = 0 ; b < m +2 ; b ++ )

    grid[a][b] = 0 ;

    for( x = x ; x >= 1 ; x -- )

    {

    cin >> a >> b ;

    grid[a][b]= 1;

    }

    printf("输入起始位置和结束位置:\n");

    cin>>start.row>>start.col>>finish.row>>finish.col;

    if(FindPath(start,finish))

    {

    printf("输出路径长度及途中坐标:");

    cout<<PathLen<<endl;

    cout<<start.row<<" "<< start.col<<endl;

    for( j = 0 ; j < PathLen ; j++ )

    cout<<path[j].row<<" "<<path[j].col<<endl;

    }

    else cout<<"No Solution!"<<endl;

    delete []path;

    return 0 ;

    }

 

来自：http://c.chinaitlab.com/example/794375.html