算法设计与分析书中程序(第09章)

《算法设计与分析书中程序(第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的每个不受限的孩子){x=

2、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是指向状态树根指针，U的初值应大

3、于最优解值，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、{U=cost(x);ans=x;}·207·elseif(u(x)+eNode*LCBB(Node*t,T&U){LiveList*>lst(mSize);//lst为优先权队列Node*

5、ans=NULL,*x,E=*t;do{for(对结点E的每个孩子){//所有满足约束函数的孩子x=newNode;x->parent=E;//构造E的孩子结点xif((x)

6、活结点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{//活结点表中的活结点结构qNode(){}qNode(Tp,Tlos,intsd,intk,Node*pt){prof=p

7、;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();//求最优解值voidGenerateAns(int*x,int&k);//一维数组x为最优解向量，k中返回x的分量数·2