一般解空间的队列式分支限界法对于给定的布线区域，编程计算最短布线方案。

一般解空间的队列式分支限界法 Description 试设计一个用队列式分支限界法搜索一般解空间的函数。该函数的参数包括结点可行性 判定函数和上界函数等必要的函数，并将此函数用于解布线问题。 印刷电路板将布线区域划分成n×m个方格阵列如图(a)所示。精确的电路布线问题要求 确定连接方格a的中点到方格b 的中点的最短布线方案。在布线时，电路只能沿直线或直角 布线，如图(b)所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允许 穿过被封锁的方格。对于给定的布线区域，编程计算最短布线方案。 Input 由文件input.txt给出输入数据。第一行有3 个正整数n，m，k，

#include 
#include 
#include 
#include 
using namespace std;
ifstream cin（“1.in“）;
ofstream cout（“1.out“）;

struct pos{
	int xy;
};

int mnk;
pos pspe;
vector < vector  > mv;
queue  Q;

bool FindPath（）
{
	if （ps.x == pe.x && ps.y == pe.y）
		return true;
	pos offset[4]={{01}{10}{0-1}{-10}};
	pos phpc;
	ph = ps;

	mv[ps.x][ps.y] = 2;
	do{
		for（int i = 0; i < 4; i++）
		{
			pc.x = ph.x + offset[i].x;
			pc.y = ph.y + offset[i].y;
			if （mv[pc.x][pc.y] == 0）
			{
				mv[pc.x][pc.y] = mv[ph.x][ph.y] + 1;
				if （pc.x == pe.x && pc.y == pe.y）
					break;
				Q.push（pc）;
			}
		}

		if（pc.x == pe.x && pc.y == pe.y）
			break;

		if （Q.empty（））
			return false;
		
		ph.x = Q.front（）.x;
		ph.y = Q.fr

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2055  2008-11-22 12:46  一般解空间的队列式分支限界法\1127.cpp

     文件      36864  2009-03-13 19:21  一般解空间的队列式分支限界法\一般解空间的队列式分支限界法.doc

     目录          0  2009-03-13 19:22  一般解空间的队列式分支限界法

----------- ---------  ---------- -----  ----

                38919                    3