算法设计与分析——分支限界法——布线问题

傷城~ 2022-10-07 06:53 165阅读 0赞

印刷电路板将布线区域划分成n×m个方格如图a所示。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图b所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。  
![在这里插入图片描述][20210616195325503.png]

一个布线的例子：图中包含障碍。起始点为a，目标点为b。  
![在这里插入图片描述][20210616195338214.png]

算法思想：

解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。

接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索  
使用的c++普通队列解决问题

#include<iostream>
    using namespace std;
    #include<queue> 
    #include<bits/stdc++.h>
    class Position{
        
    	public:
    		int row;//行 
    		int col;//列 
    };
    const int m=7;//列数 
    const int n=7;
    int gird[n+2][m+2];
    bool FindPath(Position start,Position finish,int &PathLen,Position *&path)
    {
        
    	if((start.col == finish.col)&&(start.row == finish.row ))//起点和终点是同一个点时 
    	{
        
    		PathLen = 0;
    		return true;
    	}
    
    	  //初始化相对位移
    	  Position offset[4];
    	  //右 
    	  offset[0].col =0;
    	  offset[0].row =1; 
    	  //下
    	  offset[1].col =1;
    	  offset[1].row =0;
    	  
    	  //左
    	  offset[2].col =0;
    	  offset[2].row =-1;
    	  
    	  //上 
    	  offset[3].col =-1;
    	  offset[3].row =0;
    	  
    	  int NumofNbrs =4;
    	  Position here,nbr;//nbr为扩展节点 
    	  here.col = start.col ;//here为每次移动的中心位置点 
    	  here.row = start.row ;
    	  
    	  //标记可达方格的位置
    	  gird[start.col][start.row]=1;
    	  
    	  queue<Position> Q;
    	  do{
        
    	  	for(int i=0;i<NumofNbrs;i++)
    	  	{
        
    	  		nbr.col = here.col + offset[i].col;
    			nbr.row = here.row + offset[i].row;
    			
    			if(gird[nbr.col][nbr.row] ==0)//该位置还未被标记 
    			{
        
    				gird[nbr.col][nbr.row] = gird[here.col][here.row]+1;
    				
    				if((nbr.col ==finish.col )&&(nbr.row == finish.row))
    				{
        
    					break;//退出for循环 
    				}
    				Q.push(nbr);
    			 }	  
    		  }
    		  //判断是否到达了目标位置finish 
    		  if((nbr.col ==finish.col )&&(nbr.row == finish.row))
    				{
        
    					break;//退出while循环 
    				}
    			if(Q.empty())
    			{
        
    				return false;//此时无解 
    			}
    			here=Q.front();
    			Q.pop();
    			
    		  
    		  
    	  } while(true);
    	  PathLen = gird[finish.col][finish.row]-1;
    	  path = new Position[PathLen];
    	  here = finish;
    	  for(int j=PathLen-1;j>=0;j--)
    	  {
        
    	  	path[j]=here;
    	  	//找到前驱节点
    		  for(int i=0;i<NumofNbrs;i++)
    		  {
        
    		  	nbr.col = here.col + offset[i].col;
    			nbr.row = here.row + offset[i].row;
    			
    			if(gird[nbr.col][nbr.row]==j+1)
    			{
        
    				break;
    			}
    		  }
    		  
    		  here = nbr; 
    	  }
    	  return true;
    	  
    }
    int main()
    {
        
    	int PathLen;
    	Position start,finish,*path;
    	start.col=3;
    	start.row=2;
    	
    	finish.col=4;
    	finish.row=6;
    	
    	cout<<"布线的起点："<<start.col<<","<<start.row<<endl;
    	
    	cout<<"布线的终点："<<finish.col<<","<<finish.row<<endl;
    	
    
    	 
    	 //设置方格阵列“围墙”
    	for(int i=0;i<=m+1;i++)
    	{
        
    		gird[0][i]=gird[m+1][i]=-1;
    	 } 
    	 //设置方格行“围墙”
    	 for(int i=0;i<=n+1;i++)
    	 {
        
    	 	gird[i][0]=gird[i][n+1]=-1;
    	  } 
    	  
    	  gird[1][3]=-1;
    	  gird[2][3]=-1;
    	  gird[2][4]=-1;
    	  gird[3][5]=-1;
    	  gird[4][4]=-1;
    	  gird[4][5]=-1;
    	  gird[5][1]=-1;
    	  gird[5][5]=-1;
    	  gird[6][1]=-1;
    	  gird[6][2]=-1;
    	  gird[6][3]=-1;
    	  gird[7][1]=-1;
    	  gird[7][2]=-1;
    	  gird[7][3]=-1;
    	  	cout<<"布线方格阵如下(0表示允许布线，-1表示不允许布线)"<<endl;
    	for(int i=0;i<=m+1;i++)
    	{
        
    		for(int j=0;j<=n+1;j++)
    		{
        
    			cout<<setw(2)<<gird[i][j]<<" ";
    		}
    		cout<<endl;
    	 } 
    	 FindPath(start,finish,PathLen,path);
    	   	cout<<"布线后方格阵如下(0表示允许布线，-1表示不允许布线)"<<endl;
    	for(int i=0;i<=m+1;i++)
    	{
        
    		for(int j=0;j<=n+1;j++)
    		{
        
    			cout<<setw(2)<<gird[i][j]<<" ";
    		}
    		cout<<endl;
    	 } 
    	 cout<<"布线长度为："<<PathLen<<endl;
    	 cout<<"布线路径如下"<<endl;
    	 for(int i=0;i<PathLen;i++)
    	 {
        
    	 	cout<<"("<<path[i].col<<","<<path[i].row<<")"<<"→";
    	  } 
    	  return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

[20210616195325503.png]: /images/20221005/e8b3fc5508c54ce4a332fcfa24c95efb.png
[20210616195338214.png]: /images/20221005/741edfda54a84e18a7a1a4d4d19ec20b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221005/96c4d29bf329498bb1e64c6431938b1a.png