计算机算法分析与设计(第四版)习题算法分析部分详解(实验六).doc

参考代码实验六 分支限界法/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 BoardNodefriend int FIFOBoards(int *,int ,int,int *&);/非类成员，可以访问私有成员的函数，最优序列查找 public: operator int() constreturn 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(lowk0 & tmphighk-lowk)tmp=highk-lowk;return tmp;int FIFIOBoards(int *B,int n,int m,int *&bestx)/n为电路板的数量，m为连接块的数量/int bestd;queue q;/声明BoardNode类的节点队列qBoardNode E;E.x=new intn+1;/为数组指针x分配n+1个动态空间，存储当前的排列E.s=0;/最初时，排列好的电路板的数目为0E.cd=0;E.low=new intm+1;/存储每个连接块的第一个电路板的位置E.high=new intm+1;/存储每个连接块的最后一个电路板的位置for(int i=1;i=m;i+)E.highi=0;/初始化开始时的每个连接块的最后一个电路板的位置为0，表示连接块i还没有电路板放入E.x的排列中E.lowi=n+1;/初始化开始时的每个连接块的第一个电路板的位置为n+1，表示连接块i还没有电路板放入E.x的排列中for(i=1;i=n;i+)E.xi=i;/初始化E.x的排列为1，2,3.nint bestd=n+1;/最优距离bestx=0;/记录当前最优排列doif(E.s=n-1)/当已排列了n-1个时/判断是否改变每个连接块的最后一个电路板的位置for(int j=1;jE.highj)E.highj=n; int ld=E.len();/存储当前节点的各连接块长度中的最大长度/如果当前的最大长度小于了n+1if(ldbestd)delete bestx;bestx=E.x;bestd=ld;/最优距离else delete E.x;/删除分配给E.x的数组空间delete E.low;/删除分配给E.low的数组空间delete E.high;/删除分配给E.high的数组空间elseint curr=E.s+1;/rr记录现在应该排列第几个电路板for(int i=E.s+1;i=n;i+)/处理扩展节点下一层所有子节点BoardNode N;N.low=new intm+1;/与if中的意思相同N.high=new intm+1;for(int j=1;j=m;j+)N.lowj=E.lowj;/将E.low中的值赋给N.lowN.highj=E.highj;if(BE.xij)if(currN.highj)N.highj=curr;N.cd=N.len();/如果，当前节点的最大长度小于了最优长度则：if(N.cdbestd)N.x=new intn+1;N.s=E.s+1;for(int j=1;jnm;int *B=new int*n+1;for (int t=0; t=n; t+) Bt = new intm+1;for(int i=1;i=n;i+)for(int j=1;jBij;/scanf(%d,&Bij);int *bestx=new intn+1;int bestd=0;bestd=FIFIOBoards(B,n,m,bestx);printf(%dn,bestd);for(i=1;i=n;i+)coutbestxi ;coutendl;/6-6 经典n皇后问题/Description:经典n皇后问题 广度优先 建议n=14 解空间为子集树/参考答案说排列树是不正确的，本例打印n*n棋盘的所有解，即放置方法#include #include #include #include #include using namespace std; /本例子直接输入棋盘大小，不用文件/ifstream in(input.txt); /请在项目文件夹下新建一个input.txt/ofstream out(output.txt); class Node public: Node(int n) t = 0; this-n = n; loc = new intn + 1; for (int i = 0; it = other.t; this-n = other.n; this-loc = new int n + 1; for (int i = 0; i loci = other.loci; int t;/已放置t个皇后 int *loc;/loc1:t int n;/共放置n个皇后 bool checkNext(int next); void printQ(); ; bool Node:checkNext(int next) int i; for (i = 1; i = t; +i) if (loci = next)/检测同列 return false; if (loci - next = t + 1 - i)/检测反斜线 行差=列差 return false; if (loci - next = i - t - 1)/检测正斜线 return false; return true; void Node:printQ() for (int i = 1; i = n; +i) coutloci ; coutn = n; ansNum = 0; void ArrangQueen(); ; void Queen:ArrangQueen() queue Q; Node ini(n); /初始化 Q.push(ini); while(!Q.empty() Node father = Q.front(); /取队列下一个节点 Q.pop(); if (father.t = n) father.printQ(); +ansNum; for (int i = 1; i = n; +i) /一次性将当前扩展节点所有子节点考虑完，符合条件的插入队列 if (father.checkNext(i) Node Child(father); +Child.t; Child.locChild.t = i; Q.push(Child); int main() /#define in cin /#define out cout coutn; /从文件中读入一个整数 /for(int Case = 1; Case n; Queen Q(n); Q.ArrangQueen(); /outCase #Case: Q.ansNumendl; cout共Q.ansNum种放置皇后方法，如上所示。endl; / return 0; /6-15 排列空间树问题 VC2005测试通过/ 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/头文件MinHeap2.h；最小堆实现#include template class Graph; template class MinHeap template friend class Graph; public: MinHeap(int maxheapsize = 10); MinHeap()delete heap; int Size() constreturn currentsize; T Max()if(currentsize) return heap1; MinHeap& Insert(const T& x); MinHeap& DeleteMin(T &x); void Initialize(T x, int size, int ArraySize); void Deactivate(); void output(T a,int n); private: int currentsize, maxsize; T *heap; ; template void MinHeap:output(T a,int n) for(int i = 1; i = n; i+) cout ai ; cout endl; template MinHeap:MinHeap(int maxheapsize) maxsize = maxheapsize; heap = new Tmaxsize + 1; currentsize = 0; template MinHeap& MinHeap:Insert(const T& x) if(currentsize = maxsize) return *this; int i = +currentsize; while(i != 1 & x heapi/2) heapi = heapi/2; i /= 2; heapi = x; return *this; template MinHeap& MinHeap:DeleteMin(T& x) if(currentsize = 0) coutEmpty heap!endl; return *this; x = heap1; T y = heapcurrentsize-; int i = 1, ci = 2; while(ci = currentsize) if(ci heapci + 1) ci+; if(y = heapci) break; heapi = heapci; i = ci; ci *= 2; heapi = y; return *this; template void MinHeap:Initialize(T x, int size, int ArraySize) delete heap; heap = x; currentsize = size; maxsize = ArraySize; for(int i = currentsize / 2; i = 1; i-) T y = heapi; int c = 2 * i; while(c = currentsize) if(c heapc + 1) c+; if(y = heapc) break; heapc / 2 = heapc; c *= 2; heapc / 2 = y; template void MinHeap:Deactivate() heap = 0; /批作业调度问题 优先队列分支限界法求解 /算法编码与教材一致#include stdafx.h #include MinHeap2.h #include using namespace std; class Flowshop; class MinHeapNode friend Flowshop; public: operator int() const return bb; private: void Init(int); void NewNode(MinHeapNode,int,int,int,int); int s, /已安排作业数 f1, /机器1上最后完成时间 f2, /机器2上最后完成时间 sf2, /当前机器2上完成时间和 bb, /当前完成时间和下界 *x; /当前作业调度 ; class Flowshop friend int main(void); public: int BBFlow(void); private: int Bound(MinHeapNode E,int &f1,int &f2,bool *y); void Sort(void); int n, /作业数 * M, /各作业所需的处理时间数组 *b, /各作业所需的处理时间排序数组 *a, /数组M和b的对应关系数组 *bestx, /最优解 bestc; /最小完成时间和 bool *y; /工作数组 ; template inline void Swap(Type &a, Type &b); int main() int n=3,bf; int M132=2,1,3,1,2,3; int *M = new int*n; int *b = new int*n; int *a = new int*n; bool *y = new bool*n; int *bestx = new intn; for(int i=0;i=n;i+) Mi = new int2; bi = new int2; ai = new int2; yi = new bool2; cout各作业所需要的时间处理数组M(i,j)值如下：endl; for(int i=0;in;i+) for(int j=0;j2;j+) Mij=M1ij; for(int i=0;in;i+) cout(; for(int j=0;j2;j+) coutMij ; cout); coutendl; Flowshop flow; flow.n = n; flow.M = M; flow.b = b; flow.a = a; flow.y = y; flow.bestx = bestx; flow.bestc = 1000;/给初值 flow.BBFlow(); cout最优值是：flow.bestcendl; cout最优调度是：; for(int i=0;in;i+) cout(flow.bestxi+1) ; coutendl; for(int i=0;in;i+) delete Mi; delete bi; delete ai; delete yi; return 0; /最小堆节点初始化 void MinHeapNode:Init(int n) x = new intn; for(int i=0; in; i+) xi = i; s = 0; f1 = 0; f2 = 0; sf2 = 0; bb = 0; /最小堆新节点 void MinHeapNode:NewNode(MinHeapNode E,int Ef1,int Ef2,int Ebb,int n) x = new intn; for(int i=0; in; i+) xi = E.xi; f1 = Ef1; f2 = Ef2; sf2 = E.sf2 + f2; bb = Ebb; s = E.s + 1; /对各作业在机器1和2上所需时间排序 void Flowshop:Sort(void) int *c = new intn; for(int j=0; j2; j+) for(int i=0; in; i+) bij = Mij; ci = i; for(int i=0; ii; k-) if(bkjbk-1j) Swap(bkj,bk-1j); Swap(ck,ck-1); for(int i=0; in; i+) acij = i; delete c; /计算完成时间和下界 int Flowshop:Bound(MinHeapNode E,int &f1,int &f2,bool *y) for(int k=0; kn; k+) for(int j=0; j2; j+) ykj = false