《算法设计与分析书中程序(第09章).doc》由会员分享，可在线阅读，更多相关《算法设计与分析书中程序(第09章).doc（9页珍藏版）》请在金锄头文库上搜索。
1、【程序9-1】 分枝限界算法template struct Node T cost; Node* parent;/状态空间树采用树的双亲表示法，parent是指向其双亲的指针;templatevoid BranchBound(Node* t)/ t是指向状态空间树的根结点指针 LiveListNode* lst(mSize);/lst为活结点表，表中元素为指针类型 Node *x,*E=t;/E指向根结点t do /为方便起见，以下描述中不区分指针与其所指示的结点，用指针代表所指示的结点 for( 对结点E的每个不受限的孩子) x=new Node;x-parent=E;/构造E的孩子结点x
2、if ( x是一个答案结点 ) 输出从x到t的一条路径；return;/输出一个解后算法终止 lst.Append(x);/指向活结点的指针x进活结点表 if(lst.IsEmpty() cout没有答案结点；return；/搜索失败终止 lst.Serve(E);/从lst输出一个活结点为E-结点 while（1）；【程序9-2】 基于上下界函数的FIFO分枝限界法templateNode* FIFOBB(Node* t,T& U)/t是指向状态树根指针，U的初值应大于最优解值，U返回最优解值/函数返回答案结点指针ans LiveListNode* lst(mSize);/lst为FIFO队
3、列 Node *ans=NULL, *x, *E=t;/ans指向答案结点，E为扩展结点 do for(对结点E的每个孩子)/所有满足约束条件的孩子 x=new Node;x-parent=E;/构造E的孩子结点x if (x)U)/未被限界函数剪枝的子树根x lst.Append(x);/x进队列 if ( x是一个答案结点 & cost(x)U)/x为答案结点时修正U if (u(x)+e cost(x) U=u(x)+e; else U=cost(x);ans=x; else if(u(x)+eU) U=u(x)+e;/x为非答案结点时修正U do if(lst.IsEmpty() re
4、turn ans;/若队列为空，则返回指针ans lst.Serve(E);/从队列中取出活结点 while (E)U );/当(E)U时，E成为扩展结点 while（1）；【程序9-3】 基于上下界的LC分枝限界法templateNode* LCBB(Node* t,T& U) LiveListNode* lst(mSize);/lst为优先权队列 Node *ans=NULL,*x,E=*t; do for( 对结点E的每个孩子)/所有满足约束函数的孩子 x=new Node;x-parent=E;/构造E的孩子结点x if (x)U)/x子树未被限界函数剪枝 lst.Append(x);
5、 if ( x是一个答案结点 & cost(x)U)/x为答案结点时修正U if (u(x)+e cost(x) U=u(x)+e; else U=coxt(x);ans=x; else if(u(x)+eU) U=u(x)+e;/x为非答案结点时修正U if(!lst.IsEmpty() lst.Serve(E);/从队列中取出活结点E if (E)U) return ans;/若(E)U，则算法结束 else return ans;/若队列为空，则算法结束 while（1）；【程序9-4】 带时限的作业排序struct Node/状态空间树结点结构Node(Node* par,int k)
6、parent=par;j=k;Node* parent;/指向该结点的双亲结点int j;/该结点代表的解分量xij;templatestruct qNode/活结点表中的活结点结构qNode()qNode(T p,T los,int sd,int k,Node* pt) prof=p;loss=los;d=sd;ptr=pt;j=k;T prof,loss;/当前结点X的下界函数(X)=loss，上界函数u(X)=24-profint j,d;/当前活结点所代表的解的分量xi=j，d是迄今为止的时间Node* ptr;/指向状态空间树中相应的结点;templateclass JSpublic
7、:JS(T *prof,int *de,int *time,int size);T JSFIFOBB();/求最优解值void GenerateAns(int *x,int &k);/一维数组x为最优解向量，k中返回x的分量数private:T *p,total;/p为收益数组，total初值为n个作业收益之和int *t,*d,n;/t为作业处理时间数组，d为按非减次序排列的作业时限数组Node *ans,*root;/root指向状态空间树的根，ans指向最优解答案结点;templateT JS:JSFIFOBB () Node *E,*child;QueueqNode q(mSize);
8、/生成一个FIFO队列实例qE=root=new Node(NULL,-1);/构造状态空间树的根结点root qNode ep(0,0,0,-1,root),ec;/ep为扩展结点T U=total+epsilon/上界变量U赋初值，total为作业收益和，epsilon为小量while(1)T loss=ep.loss,prof=ep.prof; E=ep.ptr;/loss为已造成的损失，prof为已获收益for (int j=ep.j+1;jn;j+)/考察所有孩子 if(ep.d+tj=dj & lossU) child=new Node(E,j);/构造E的孩子结点ec.prof=
9、prof+pj;ec.d=ep.d+tj;ec.ptr=child;ec.loss=loss;ec.j=j;q.Append(ec);/活结点进队列T cost=total-ec.prof;/计算上界函数值if(cost=U);【程序9-5】 类声明struct Node/状态空间树结点Node(Node* par,bool lft)parent=par;left=lft;Node* parent;/指向双亲结点的指针bool left;/若当前结点是双亲的左孩子，则left为true，否则为false;templatestruct pqNode/活结点结构operator T()const
10、return UBB;pqNode()pqNode(float cap,T prof,T ub,int lev,Node* p)cu=cap;profit=prof;level=lev;UBB=ub;ptr=p;float cu;/背包的剩余载重T profit,UBB;/已获收益profit和上界函数值UBBint level;/当前结点的level，根结点为0Node *ptr;/指向状态空间树上相应的结点;templateclass Knapsackpublic: Knapsack(T* prof,float* wei,float mm,int len);/对象初始化事项 T LCBB();/求最优解值 void GenerateAns(int *x);/产生最优解private:void LUBound(T cp,float cw,int k,T& LBB,T& UBB);/计算结点的上下界UBB和LBBT* p; /一维数组p保存n个物品收益float* w,m;/一维数组w保存n个物品重量，m为背包载重量int n;/物品数目Node* ans,* root;/指向状态空间树的根和最优解结点;【程序9-6】 上下界函数template void Knapsack:LUBound(T cp,float cw,int k,T& LBB,T& UBB)
