实验六分支限界法
//6-1、6-6项目VC++6.0测试通过
//6-15项目VC2005测试通过
//6-1 最小长度电路板排列问题
//头文件stdafx.h
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
#pragma once
#define WIN32_LEAN_AND_MEAN // Exclude rarely-used stuff from Windows headers #include
#include
// TODO: reference additional headers your program requires here
// sy61.cpp : Defines the entry point for the console application.
//
//Description:
//分支限界法6_1 最小长度电路板排列问题
//#include "my.h"
#include "stdafx.h"
#include
#include
using namespace std;
int n,m;
//#include "OutOfBounds.h"
//定义节点类
class BoardNode{
friend int FIFOBoards(int **,int ,int,int *&);//非类成员，可以访问私有成员的函数，最优序列查找
public:
operator int() const{return cd;}//返回常数cd
int len();
public:
int *x,s,cd,*low,*high;//x表示当前节点的电路板排列，s表示当前节点排列好的电路板的数
//表示当前节点的最大长度，low，high分别表当前节点表示每一个连接块的第一个，和最后一个电路板
//的位置
};
//编写类的len()函数,求出当前节点的连接块长度的最大值
int BoardNode::len()
{
int tmp=0;
for(int k=1;k<=m;k++)
if(low[k]<=n && high[k]>0 && tmptmp=high[k]-low[k];
return tmp;
}
int FIFIOBoards(int **B,int n,int m,int *&bestx)//n为电路板的数量，m为连接块的数量
{
// int bestd;
queue q;//声明BoardNode类的节点队列q
BoardNode E;
E.x=new int[n+1];//为数组指针x分配n+1个动态空间，存储当前的排列
E.s=0;//最初时，排列好的电路板的数目为0
E.cd=0;
E.low=new int[m+1];//存储每个连接块的第一个电路板的位置
E.high=new int[m+1];//存储每个连接块的最后一个电路板的位置
for(int i=1;i<=m;i++)
{
E.high[i]=0;//初始化开始时的每个连接块的最后一个电路板的位置为0，表示连接块i还没有电路板放入E.x的排列中
E.low[i]=n+1;//初始化开始时的每个连接块的第一个电路板的位置为n+1，表示连接块i还没有电路板放入E.x的排列中
}
for(i=1;i<=n;i++)
E.x[i]=i;//初始化E.x的排列为1，2,3.....n
int bestd=n+1;//最优距离
bestx=0;//记录当前最优排列
do{
if(E.s==n-1)//当已排列了n-1个时
{
//判断是否改变每个连接块的最后一个电路板的位置
for(int j=1;j<=m;j++)
if(B[E.x[n]][j] && n>E.high[j])
E.high[j]=n;
int ld=E.len();//存储当前节点的各连接块长度中的最大长度
//如果当前的最大长度小于了n+1
if(ld{
delete[] bestx;
bestx=E.x;
bestd=ld;//最优距离
}
else delete[] E.x;//删除分配给E.x的数组空间
delete[] E.low;//删除分配给E.low的数组空间
delete[] E.high;//删除分配给E.high的数组空间
}
else
{
int curr=E.s+1;//rr记录现在应该排列第几个电路板
for(int i=E.s+1;i<=n;i++)//处理扩展节点下一层所有子节点
{
BoardNode N;
N.low=new int[m+1];//与if中的意思相同
N.high=new int[m+1];
for(int j=1;j<=m;j++)
{
N.low[j]=E.low[j];//将E.low[]中的值赋给N.low[]
N.high[j]=E.high[j];
if(B[E.x[i]][j])
{
if(currN.low[j]=curr;//若当前节点连接块j的第一个电路板的位置比现在正在排列的电路板的位置还小
if(curr>N.high[j])
N.high[j]=curr;
}
}
N.cd=N.len();
//如果，当前节点的最大长度小于了最优长度则：
if(N.cd{
N.x=new int[n+1];
N.s=E.s+1;
