欢迎来到天天文库
浏览记录
ID:15895198
大小:796.50 KB
页数:9页
时间:2018-08-06
《算法设计与分析书中程序(第09章)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、【程序9-1】分枝限界算法templatestructNode{Tcost;Node*parent;//状态空间树采用树的双亲表示法,parent是指向其双亲的指针};templatevoidBranchBound(Node*t){//t是指向状态空间树的根结点指针LiveList*>lst(mSize);//lst为活结点表,表中元素为指针类型Node*x,*E=t;//E指向根结点tdo{//为方便起见,以下描述中不区分指针与其所指示的结点,用指针代表所指示的结点for(对结点E的每个不受
2、限的孩子){x=newNode;x->parent=E;//构造E的孩子结点xif(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
3、是指向状态树根指针,U的初值应大于最优解值,U返回最优解值//函数返回答案结点指针ansLiveList*>lst(mSize);//lst为FIFO队列Node*ans=NULL,*x,*E=t;//ans指向答案结点,E为扩展结点do{for(对结点E的每个孩子){//所有满足约束条件的孩子x=newNode;x->parent=E;//构造E的孩子结点xif((x)4、+eNode*LCBB(Node*t,T&U){LiveList5、*>lst(mSize);//lst为优先权队列Node*ans=NULL,*x,E=*t;do{for(对结点E的每个孩子){//所有满足约束函数的孩子x=newNode;x->parent=E;//构造E的孩子结点xif((x)6、if(!lst.IsEmpty()){lst.Serve(E);//从队列中取出活结点Eif((E)≥U)returnans;//若(E)≥U,则算法结束}elsereturnans;//若队列为空,则算法结束}while(1);}【程序9-4】带时限的作业排序structNode{//状态空间树结点结构Node(Node*par,intk){parent=par;j=k;}Node*parent;//指向该结点的双亲结点intj;//该结点代表的解分量x[i]=j};templatestructqNode{//活结点表中的活结点结构q7、Node(){}qNode(Tp,Tlos,intsd,intk,Node*pt){prof=p;loss=los;d=sd;ptr=pt;j=k;}Tprof,loss;//当前结点X的下界函数(X)=loss,上界函数u(X)=24-profintj,d;//当前活结点所代表的解的分量x[i]=j,d是迄今为止的时间Node*ptr;//指向状态空间树中相应的结点};templateclassJS{public:JS(T*prof,int*de,int*time,intsize);TJSFIFOBB();//求最优解值voidGen8、erateAns(int*x,int&k);//一维数组x为最优解向量,k中返回x的分量数·2
4、+eNode*LCBB(Node*t,T&U){LiveList
5、*>lst(mSize);//lst为优先权队列Node*ans=NULL,*x,E=*t;do{for(对结点E的每个孩子){//所有满足约束函数的孩子x=newNode;x->parent=E;//构造E的孩子结点xif((x)6、if(!lst.IsEmpty()){lst.Serve(E);//从队列中取出活结点Eif((E)≥U)returnans;//若(E)≥U,则算法结束}elsereturnans;//若队列为空,则算法结束}while(1);}【程序9-4】带时限的作业排序structNode{//状态空间树结点结构Node(Node*par,intk){parent=par;j=k;}Node*parent;//指向该结点的双亲结点intj;//该结点代表的解分量x[i]=j};templatestructqNode{//活结点表中的活结点结构q7、Node(){}qNode(Tp,Tlos,intsd,intk,Node*pt){prof=p;loss=los;d=sd;ptr=pt;j=k;}Tprof,loss;//当前结点X的下界函数(X)=loss,上界函数u(X)=24-profintj,d;//当前活结点所代表的解的分量x[i]=j,d是迄今为止的时间Node*ptr;//指向状态空间树中相应的结点};templateclassJS{public:JS(T*prof,int*de,int*time,intsize);TJSFIFOBB();//求最优解值voidGen8、erateAns(int*x,int&k);//一维数组x为最优解向量,k中返回x的分量数·2
6、if(!lst.IsEmpty()){lst.Serve(E);//从队列中取出活结点Eif((E)≥U)returnans;//若(E)≥U,则算法结束}elsereturnans;//若队列为空,则算法结束}while(1);}【程序9-4】带时限的作业排序structNode{//状态空间树结点结构Node(Node*par,intk){parent=par;j=k;}Node*parent;//指向该结点的双亲结点intj;//该结点代表的解分量x[i]=j};templatestructqNode{//活结点表中的活结点结构q
7、Node(){}qNode(Tp,Tlos,intsd,intk,Node*pt){prof=p;loss=los;d=sd;ptr=pt;j=k;}Tprof,loss;//当前结点X的下界函数(X)=loss,上界函数u(X)=24-profintj,d;//当前活结点所代表的解的分量x[i]=j,d是迄今为止的时间Node*ptr;//指向状态空间树中相应的结点};templateclassJS{public:JS(T*prof,int*de,int*time,intsize);TJSFIFOBB();//求最优解值voidGen
8、erateAns(int*x,int&k);//一维数组x为最优解向量,k中返回x的分量数·2
此文档下载收益归作者所有