分支队列法解电路布线问题.cpp

算法分析中

#include<iostream>
using namespace std;
/*
解布线问题：
布线问题的解空间是一个图。
从位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到
活结点队列中，并且将这些方格标记为1。接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与
当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b
或活结点队列为空时为止。
*/

class Position
{
public:
	Position()
	{
	}
	Position* operator=(const Position& a)
	{
		row = a.row;
		col = a.col;
		movedirection = a.movedirection;
		return this;
	}
public:
		int row;
		int col;
		int movedirection;
};

/*
用一个二维数组grid表示所给的方格阵列。初始时，grid[i][j]=0,表示该方格允许布线
，grid[i][j]=1表示方格被封锁，不允许布线。为了便于处理方格边界的情况，算法在所给方格
阵列四周设置一道“围墙”，即增设标记为“1”的附加方格。算法开始时测试初始方格与目标
方格是否相同。如果这两个方格相同则不必计算，直接返回最短距离0，否则算法设置方格阵列的
“围墙”，初始化位移矩阵offset,
*/
template<class Type>
class Queue
{
	public:
		Type *H;
		int Capacity;
		int Size;
		int Front;
		int Rear;
	public:
		Queue(int n)
		{
			H = NULL;
			H = new Type[n+1];
			Capacity = n;
			Size = 0;
			Front = 0;
			Rear = 0;
		};
		Queue( Queue& a )
		{
			//要排除自赋值的情况
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				this.Front = a.Front;
				this.Rear = a.Rear;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[i];
				}
			}
		};

		void Add( Type& node )
		{
			if ( Size == Capacity )
			{
				cout<<"capacity"<<endl;
				return;
			}
			else
			{
				if ( Rear + 1 == Capacity )
				{
					H[Rear] = node;
					Rear = 0;
					++Size;
				}
				else
				{
					H[Rear] = node;
					++Size;
					++Rear;
				}
			}
			
		};

		void Delete( Type& node )
		{
			if ( Size == 0 )
			{
				return;
			}
			else
			{	
				if ( Front == Capacity )
				{
					Front = 0;
				}
				node = H[Front];
				++Front;
				--Size;
			}
		};

		bool IsEmpty()
		{
			return ( 0 == Size );
		};
};

int m = 5;
int n = 6;
int grid[7][8] = { 0 };
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 ( 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 NumOfNbrs = 4;
	//相邻方格数
	Position here,nbr;
	here.row = start.row;
	here.col = start.col;
	grid[start.row][start.col] = 2;
	//标记可达方格的位置
	
	Queue< Position > Q(100);
	
	do
	{
		//标记可达相邻方格
		for ( int i = 0; i < NumOfNbrs; ++i )
		{
			nbr.row = here.row + offset[i].row;
			nbr.col = here.col + offset[i].col;

			cout<<"nbr.row "<<nbr.row<<endl;
			cout<<"nbr.col "<<nbr.col<<endl;
			if ( grid[nbr.row][nbr.col] == 0 )
			{
				cout<<"增加新结点:"<<endl;
				//该方格未标记
				grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;
				if ( ( nbr.row == finish.row )
					&& ( nbr.col == finish.col ) ) 
				{
					break;
				}
				Q.Add( nbr );
				//可达接点作为向下遍历的同层起点，图的每一层
			}
		}
		
		//是否到达目标位置finish
		if ( ( nbr.row == finish.row )
			 && ( nbr.col == finish.col ) )
		{
			break;
			//完成布线
		}
		//活结点队列是否非空
		if ( Q.IsEmpty() )
		{
			cout<<"start"<<endl;
			return false;
			//无解
		}
		Q.Delete( here );
		//取下一个扩展结点
	}while( true );
	//构造最短布线路径
	PathLen = grid[finish.row][finish.col] - 2;
	path = new Position[PathLen];
	//从目标位置finish开始向起始位置回溯
	//肯定是一共经过PathLen个点，第一个点的标记为2，其后每层都
	//依次加1

	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 + 2 )
			//凡是有此标记的就是符合要求的点
			{
				cout<<"行是: "<<nbr.row<<" "<<"列是: "<<nbr.col<<endl;
				break;
			}
		}
		here = nbr;
		//向前移动
	}
	return true;
}

int main()
{
	Position start;
	start.row = 1;
	start.col = 1;
	Position finish;
	finish.row = 5;
	finish.col = 5;
	int PathLen;
	Position* path;
	FindPath( start, finish, PathLen, path );
	cout<<"第二次搜索: "<<endl;
	start.row = 2;
	start.col = 1;
	finish.row = 5;
	finish.col = 3;
	for( int i = 0; i < 7; ++i )
	{
		for( int j = 0; j < 8; ++j )
		{
			grid[i][j] = 0;
		}
	}
	
	FindPath( start, finish, PathLen, path );

	return 0;
}