余新华-5.5.txt

这是很不错的计算机算法

/*批处理作业调度问题求解程序*/
/*本程序运行前提：
  在源程序目录下存在input.txt文件，并且该文件已经按一定格式存储若干值
/*本程序在tc++3.0和vc++6.0上运行通过*/
#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<conio.h>

int size;//批处理作业个数 
class flowshop;//预先声明flowshop类 

/*交换函数的定义*/ 
void swap(int& a,int& b)
{
  int temp;
  temp=a;
  a=b;
  b=temp;
}

/*------------类minheapnode的定义开始(表示堆结点)-----------------*/ 
class minheapnode
{
  friend flowshop;//友元类 
  public:
    int bb;//当前完成时间和下界 
    minheapnode();//构造函数 
    minheapnode(minheapnode& temp);//拷贝构造函数 
    minheapnode& operator = (minheapnode& temp);//赋值运算符重载 
    ~minheapnode();//析构函数 
  private:
    int s;//已安排作业数 
    int f1;//机器1上最后完成时间 
    int f2;//机器2上最后完成时间 
    int sf2;//当前机器2上的完成时间和 
    int *x;//当前作业调度 
    void newnode(minheapnode,int,int,int,int);//对象赋值函数 
};

/*构造函数的定义*/ 
minheapnode::minheapnode()
{
  x=new int[size];//分配x数组 
  for(int i=0;i<size;i++) x[i]=i;//x数组初始化 
  s=f1=f2=sf2=bb=0;//其他成员初始化 
}

/*拷贝构造函数的定义*/ 
minheapnode::minheapnode(minheapnode& temp)
{
  s=temp.s;
  f1=temp.f1;
  f2=temp.f2;
  sf2=temp.sf2;
  bb=temp.bb;//各个成员赋值拷贝 
  x=new int[size];//分配x数组 
  for(int i=0;i<size;i++) x[i]=temp.x[i];//拷贝x数组 
}

/*赋值运算符重载函数的定义*/ 
minheapnode& minheapnode::operator = (minheapnode& temp)
{
  s=temp.s;
  f1=temp.f1;
  f2=temp.f2;
  sf2=temp.sf2;
  bb=temp.bb;//各个成员赋值 
  for(int i=0;i<size;i++) x[i]=temp.x[i];//x数组赋值 
  return *this;//返回对象 
}

/*析构函数的定义*/ 
minheapnode::~minheapnode()
{
  delete[] x;//释放x数组所占内存 
}

/*对象赋值函数的定义*/ 
void minheapnode::newnode(minheapnode e,int ef1,int ef2,int ebb,int n)
{
  x=new int[n];//分配x数组 
  for(int i=0;i<n;i++) x[i]=e.x[i];//x数组赋值 
  f1=ef1;
  f2=ef2;
  sf2=e.sf2+f2;
  bb=ebb;
  s=e.s+1;//其他成员赋值 
}
/*------------类minheapnode的定义结束-----------------*/


/*------------类minheap的定义开始(表示最小堆)-----------------*/
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;
}
/*------------类minheap的定义结束-----------------*/


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

/*构造函数的定义*/ 
flowshop::flowshop()
{
  int i,j;//循环控制变量 
  ifstream fin("input.txt",ios::nocreate);//打开输入文件
  fin>>n;//读入作业个数 
  size=n;//设置size值 
  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 int*[n]))//分配二维数组y 
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  for(i=0;i<n;i++)
    if(!(y[i]=new int[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=100000;//设定bestc初始值 
}

/*析构函数*/ 
flowshop::~flowshop()
{
  int i;//循环控制变量 
  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 flowshop::outputtofile()
{
  ofstream out("output.txt");//创建输出文件
  out<<bestc<<endl;//输出最小完成时间和 
  for(int i=0;i<n;i++)
  {
    out<<bestx[i]+1<<" ";//输出最优解信息 
  }
  out.close();//关闭输出文件 
}     

/*排序函数的定义*/      
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,int **y)
{
  int j,k;//循环控制变量 
  for(k=0;k<n;k++)//y数组初始化 
    for(j=0;j<2;j++)
      y[k][j]=0;
  for(k=0;k<=e.s;k++)//设置已完成的作业标志为1 
    for(j=0;j<2;j++)
      y[a[e.x[k]][j]][j]=1;
  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()
{
  int i;//循环控制变量 
  sort();//对各作业在每机器上的完成时间进行排序 
  minheap h(100000);//创建大小为100000的堆 
  minheapnode e;//创建堆结点对象 
  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];
      }
    }
    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]);//还原为原来的排列 
      }
    }
    if(!h.removemin(e)) break;//堆不为空，取下一扩展结点，否则退出循环 
  }
}
/*------------类flowshop的定义结束----------------*/ 


   
//主程序 
void main()
{
  flowshop flow;//创建flowshop对象 
  flow.bbflow();//进行调度求最优解 
  flow.outputtofile();//输出最优解 
}
  
/*排序对求解s1和s2的作用：
  如果不排序，则对于不同的调度情况s1和s2的值是不同的
  排序后，t从小到大排列，则对于（n-k+1）*t（k从r+1到n）这个和来说，越大的数乘的系数
  越小，保证了求得的s1和s2在剩余未执行的作业排列中是最小情况*/