梁淘-5.5.txt

这是很不错的计算机算法

#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>

class flowshop;//预先声明作业调度类

//堆结点生成类
class minheapnode
{  
	friend flowshop;//友元类  

	public:
		operator int() const {return bb;}
		int bb;//当前完成时间和下界
	private:
		void init(int);//最小堆结点初始化
		void newnode(minheapnode,int,int,int,int);//生成最小堆新结点的对象赋值函数
		int s;//已安排作业数
		int f1;//机器1上最后完成时间
		int f2;//机器2上最后完成时间
		int sf2;//当前机器2上的完成时间和
		int *x;//当前作业调度

 };


void minheapnode::init(int n)
{  //最小堆结点初始化
	x=new int[n];//分配x数组
	for(int i=0;i<n;i++)
		x[i]=i;//x数组初始化
	s=f1=f2=sf2=bb=0;//其他成员初始化
 }


 void minheapnode::newnode(minheapnode e,int ef1,int ef2,int ebb,int n)
 {  //最小堆新结点
	 x=new int[n];
	 for(int i=0;i<n;i++)
		 x[i]=e.x[i];
	 f1=ef1;
	 f2=ef2;
	 sf2=e.sf2+f2;
	 bb=ebb;
	 s=e.s+1;
 };


 //堆排序类
 class minheap
 {  
	private:
		minheapnode *heap;//堆数组
		int currentsize;//当前堆元素个数
		int heapsize;//堆大小
		void filterdown(int start,int endofheap);//向下调整
		void filterup(int start);//向上调整
	public:
	    minheap(int n);//构造函数
		~minheap();//析构函数
		int insert(minheapnode& x);//插入函数
		int removemin(minheapnode& x);//删除最小值函数
		int isempty();//判断空函数
		int isfull();//判断满函数
		void makeempty();//置空函数
 };
 
 minheap::minheap(int n)
 {  
	 heapsize=n;//设置堆大小
	 currentsize=0;//设置0表示堆中无结点
	 if(!(heap=new minheapnode[heapsize]))//分配heap数组
	 {    
		 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		 exit(-1);
	 }
 }

 minheap::~minheap()
 {  
	 delete[] heap;//释放heap数组所占内存
 }

 /*判断空函数的定义*/
 int minheap::isempty()
 {  
	 return currentsize==0;
 }
 
 /*判断满函数的定义*/
 int minheap::isfull()
 {  
	 return currentsize==heapsize;
 }
 
 /*置空函数的定义*/ 
 void minheap::makeempty()
 {  
	 currentsize=0;//设定0表示堆中无结点
 }
 
 /*向下调整函数的定义*/
 void minheap::filterdown(int start,int endofheap)
 {  
	 int i=start,j=2*i+1;//j是i的左子女
	 minheapnode temp=heap[i];//预先保存i位置的值
	 while(j<=endofheap)
	 {    
		 if(j<endofheap&&heap[j].bb>heap[j+1].bb) j++;//选出两子女中更小值位置
		 if(temp.bb<=heap[j].bb) break;//如果比最小值更小则不需调整
		 else     
		 {      
			 heap[i]=heap[j];//将最小值移动到根位置
			 i=j;//设置新的根位置
			 j=2*j+1;//新的左子女位置，继续向下调整
		 }
	 }  
	 heap[i]=temp;//将初始位置的结点移动到新位置
 }

 /*向上调整函数的定义*/ 
 void minheap::filterup(int start)
 {  
	 int j=start,i=(j-1)/2;//j是i的双亲
	 minheapnode temp=heap[j];//预先保存j位置的值
	 while(j>0)  
	 {    
		 if(heap[i].bb<temp.bb) break;//如果双亲更小则不需调整
		 else    
		 {      
			heap[j]=heap[i];//将最小值移动到双亲位置上
			j=i;//设置新的子女位置
			i=(i-1)/2;//新的双亲位置，继续向上调整
		 }  
	 }  
	 heap[j]=temp;//将初始位置的结点移动到新位置
 }
 
 /*插入函数的定义*/
 int minheap::insert(minheapnode& x)
 {  
	 if(currentsize==heapsize)//堆已满不能插入
	 {    
		 cout<<"堆已满"<<endl;
		 return 0;
	 }	  
	 heap[currentsize]=x;//在堆尾插入元素
	 filterup(currentsize);//向上调整为最小堆
	 currentsize++;//元素个数加1
	 return 1;
 }
 
 /*删除最小值函数的定义*/
 int minheap::removemin(minheapnode& x)
 {  
	 if(!currentsize)//堆空不能删除
	 {     
		 cout<<"堆已空"<<endl;
		 return 0;   
	 }  
	 x=heap[0];//堆首元素赋给x
	 heap[0]=heap[currentsize-1];//堆尾元素移动到堆首
	 currentsize--;//元素个数减1   
	 filterdown(0,currentsize-1);//向下调整为最小堆
	 return 1;
 }

 
/*交换函数的定义*/
void swap(int& a,int& b)
{  int temp;
  temp=a;  
  a=b;
  b=temp;
}
 
 /*调度类*/ 
 class flowshop
 {  
	public:    
		void bbflow(void);//优先队列式分支限界法求解
		flowshop();//构造函数    
		void outputtofile();//输出解信息
	private:
		 int bound(minheapnode,int&,int&,bool **);//计算完成时间和下界
		 void sort(void);//排序
	     int n;//批处理作业个数
	     int **m;//个作业所需的处理时间数组     
		 int **b;//个作业所需的处理时间排序后数组
	     int **a;//数组m和b的对应关系数组（a[i][j]=k表示作业i在数组b中的位置是k，即第k个处理）
	     int *bestx;//最优解
		 int bestc;//最小完成时间和
		 bool **y;//y[i][j]表示作业i在机器j上是否已完成
 };


 /*排序函数的定义*/
 void flowshop::sort()//按照在机器1和机器2上的完成时间进行递增排序
 {  
	 int i,j,k;//循环控制变量
	 int *c;  
	 if(!(c=new int[n]))//分配c数组
	 {    
		 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		 exit(-1);
	 }  
	 for(j=0;j<2;j++)//b和c数组初始化
	 {    
		 for(i=0;i<n;i++)
		 {  
			 b[i][j]=m[i][j];
			 c[i]=i;
		 }   
		 for(i=0;i<n-1;i++)//冒泡排序趟数
			 for(k=n-1;k>i;k--)
				 if(b[k][j]<b[k-1][j])
				 {   
					 swap(b[k][j],b[k-1][j]);//交换b两元素
					 swap(c[k],c[k-1]);//同时交换c
				 }    
				 for(i=0;i<n;i++) a[c[i]][j]=i;//设置m和b的关系数组a
	 }  
	 delete[] c;//释放c所占内存
 }
 
 /*计算下界函数的定义*/
 int flowshop::bound(minheapnode e,int& f1,int& f2,bool **y)
 {  
	 int j,k;//循环控制变量
	 for(k=0;k<n;k++)//y数组初始化
		 for(j=0;j<2;j++)
			 y[k][j]=false;
		 for(k=0;k<=e.s;k++)//设置已完成的作业标志
			 for(j=0;j<2;j++)
				 y[a[e.x[k]][j]][j]=true;
		 f1=e.f1+m[e.x[e.s]][0];//当前作业完成后机器1最后完成时间
		 f2=((f1>e.f2)?f1:e.f2)+m[e.x[e.s]][1];//当前作业完成后机器2最后完成时间
		 int sf2=e.sf2+f2;//当前作业完成后的完成时间和
		 int s1=0,s2=0,k1=n-e.s,k2=n-e.s,f3=f2;//初始化各变量
		 for(j=0;j<n;j++)//计算s1的值（机器1没有空闲的下界）
			 if(!y[j][0])
			 {     
				 k1--; 
				 if(k1==n-e.s-1) f3=(f2>f1+b[j][0])?f2:f1+b[j][0];
				 s1+=f1+k1*b[j][0];//累加每次作业的完成时间
			 }
		for(j=0;j<n;j++)//计算s2的值（机器2没有空闲的下界）
		 if(!y[j][1])   
		 {  
			 k2--;
			s1+=b[j][1];//s1的值
			s2+=f3+k2*b[j][1];//累加每次作业的完成时间 
		 }  
		return sf2+((s1>s2)?s1:s2);//返回完成时间和下界
 }

 
 void flowshop::bbflow(void)
 {  
	 int i;//循环控制变量
	 sort();//对各作业在每机器上的完成时间进行排序
	 minheap h(1000000);//创建大小为1000000的堆
	 minheapnode e;//创建堆结点对象
	 e.init(n);//初始化
	 
	 while(e.s<=n) //搜索排列空间树
	 {    
		 if(e.s==n)//已到叶结点结束
		 {       
			 if(e.sf2<bestc)//比当前最优值更小则更新
			 {        
				 bestc=e.sf2;//更新最优值
				 for(i=0;i<n;i++)//设置最优解
					 bestx[i]=e.x[i];
			 }
			 delete [] e.x;
		 }    
		 else{//否则继续扩展结点
			 for(i=e.s;i<n;i++)
				{        
				 swap(e.x[e.s],e.x[i]);//考虑各种排列情况
				 int f1,f2;
				 int bb=bound(e,f1,f2,y);//计算下界
				 if(bb<bestc)//下界未超过最优值，则子树可能含最优解
					{          
					 minheapnode N;//分配一个堆结点
					 N.newnode(e,f1,f2,bb,n);//给结点赋值
					 h.insert(N);//将结点插入堆
					}
				 swap(e.x[e.s],e.x[i]);//还原为原来的排列
				}
			 delete [] e.x;
		 }
			 if(!h.removemin(e)) break;//堆不为空，取下一扩展结点，否则退出循环
		}
 }


 flowshop::flowshop()
 {  
	 int i,j;//循环控制变量
	 ifstream fin("input.txt",ios::nocreate);//打开输入文件
	 fin>>n;//读入作业个数
	 if(!(m=new int*[n]))//分配二维数组m
	 {    
		 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		 exit(-1);
	 }  
		for(i=0;i<n;i++)    
			if(!(m[i]=new int[2]))//为每个一维数组分配空间
			{      
			 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
			 delete[] m;
			 exit(-1);
			}  
	if(!(b=new int*[n]))//分配二维数组b
	{    
		cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		exit(-1);
	}  
		for(i=0;i<n;i++)
			 if(!(b[i]=new int[2]))//为每个一维数组分配空间
			 {     
				 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
				 delete[] b;
				 exit(-1);
			 } 
	if(!(a=new int*[n]))//分配二维数组a
	{    
		cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		exit(-1);
	}  
		for(i=0;i<n;i++)
			if(!(a[i]=new int[2]))//为每个一维数组分配空间
			{      
				cerr<<"insufficient memory!"<<endl;//分配不成功，退出
				delete[] a;
				exit(-1);
			}  
	if(!(y=new bool *[n]))//分配二维数组y
		{    
			cerr<<"insufficient memory!"<<endl;//分配不成功，退出
			exit(-1);
		}  
		  for(i=0;i<n;i++)
			  if(!(y[i]=new bool[2]))//为每个一维数组分配空间
			  {      
				  cerr<<"insufficient memory!"<<endl;//分配不成功，退出
				  delete[] y;
				  exit(-1);
			  }  
	if(!(bestx=new int[n]))//分配bestx数组
		{    
			cerr<<"insufficient memory!"<<endl;//分配不成功，退出
			exit(-1);
		}  
	for(i=0;i<n;i++)
		for(j=0;j<2;j++)
			fin>>m[i][j];//读入各个作业处理时间
	fin.close();//关闭输入文件
	bestc=32767;//设定bestc初始值
 }

void flowshop::outputtofile()
	{
 	 int i;//循环控制变量	
	ofstream out("output.txt");//创建输出文件
	 out<<bestc<<endl;//输出最小完成时间和
	 for(i=0;i<n;i++)
	 {    
		 out<<bestx[i]+1<<" ";//输出最优解信息
	 }  
	 out.close();//关闭输出文件


	 delete[] bestx;//释放bestx所占内存
	 for(i=0;i<n;i++)//释放二维m数组所占内存
		 delete[] m[i];
	 delete[] m;
	 for(i=0;i<n;i++)//释放二维b数组所占内存
		 delete[] b[i];
	 delete[] b;
	 for(i=0;i<n;i++)//释放二维a数组所占内存
		 delete[] a[i];
	 delete[] a;
	 for(i=0;i<n;i++)//释放二维y数组所占内存
		 delete[] y[i];
	 delete[] y;
 }
 


void main(void)
{
	flowshop flow;//创建flowshop对象
	flow.bbflow();//进行调度求最优解
	flow.outputtofile();//输出最优解
}