云南城投总裁叫什么:分支限界法之布线问题
分支限界法之布线问题
做IT就要做精英,至少4000/月吧?JAVAV工程师权威认证
[上海央邦]学一送一,超值! 【安博亚威】CCIE考试通过率第一!
定向委培RHCA,通过考试年薪10W
Windows高级工程师的培训地
一、要求:
1、输入电路板区域n*m以及布线的起始位置和结束位置;
2、输出布线方案;
3、可以使用c或者vc实现
二、问题分析及实验原理:
在n*m的方格阵列中存在封锁区域(布线时必须绕开的区域),找到起始位置到目标位置的最短路径。从目标位置开始向起始位置回溯,逐步构造最优解。每次向标记距离比当前方格标记距离少1的相邻方格移动,直到到达起始方格为止。
三、算法程序源代码:
#include
#include
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
Queue Q ;
Q.end = 0 ;
Q.begin = 0 ;
do {//标记相邻可达方格
for( i=0; 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 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< cout< for( j = 0 ; j < PathLen ; j++ ) cout< } else cout<<"No Solution!"< delete []path; return 0 ; }