带期限的作业排序问题

《带期限的作业排序问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、带期限的作业排序问题(1)答：c`(x)的设计思路:当x=1时，c`(x)为所有作业的罚款金额总和,某节点m的估计值为c`(x)，并对其进行扩展时，其有效的子节点a的c`(x)为m的c`(x)-a的罚款金额。对于u(x)初始时为作业罚款金额总和。之后，若队列中的某一节点b的c`(x)最小且小于u(x),则使u(x)=b.c`(x)(2)(3)当某节点的已经被罚款项即c(x)>U，则封杀此节点。(4)当从根开始到当前要加入的节点这条路径中，共花费时间costtime,最大截止期限为maxdeadtime，若maxdeadtime

2、，否则可行.(5)主要结构及类型说明nodequeue[1000];//存放状态空间树中的节点Node结构在构造状态空间树时使用structnode{intnumber;//所代表的作业在source[]的下标intmayfine;//可能的罚款的金额即罚款金额的上限intcurrentfine;//到此节点止已罚款的金额booliskilled;//是否被杀死inttimecost;//从根节点到此节点为止已花费的时间intparent;//父节点在queue[]的下标};Tast结构在输入作业信息时使用structtask{intnumber;//作业的

3、序号intfine;//罚款金额intdeadline;//截止期限inttime;//完成此作业所需的时间};intans=0;//最小上界值在queue的下标intminmayfine;//队列中活结点的罚款上限的最小值即Uintactivenumber=1;//活结点的数目constintN=?;//N表示作业数intsize=1;//当前队列中的元素个数(6)程序代码思想：//使作业按截至期限的非降序排列，则对一个父节点s，要加入一个节点m，只要m的截至期限大于等于s.timecost+m所代表的作业的time#include#i

4、ncludeusingnamespacestd;structnode{intnumber;//选择的节点在source[]的下标intmayfine;//可能的罚款的金额即罚款金额的上限intcurrentfine;//到此节点止已罚款的金额booliskilled;//是否被杀死inttimecost;//从根节点到此节点为止已花费的时间intparent;//父节点在queue[]的下标};structtask{intnumber;//作业的序号intfine;//罚款金额intdeadline;//截止期限inttime;//完成

5、此作业所需的时间};//节点被杀死的条件是已罚款的金额超过了最小罚款金额即currentfine>mayfinenodequeue[1000];//存放状态空间树constintN=4;//N表示作业数tasksource[N+1]={{0,0,0,0},{1,5,1,1},{2,10,3,2},{3,6,2,1},{4,3,1,1}};//作业集合intans=0;//最小上界值在queue的下标intminmayfine;//队列中活结点的罚款上限的最小值intactivenumber=1;//活结点的数目voidinit()//初始化队列{for(in

6、ti=1;i<=N;i++){minmayfine+=source[i].fine;}queue[0].mayfine=minmayfine;queue[0].currentfine=0;queue[0].iskilled=0;queue[0].number=0;//作业的序号queue[0].parent=-1;queue[0].timecost=0;}boolgreater(taskx,tasky){if(x.deadline<=y.deadline)return1;elsereturn0;}//aloca为节点m在queue[]的下标,b为m的子节点x

7、的作业在source[]的下标，获取x到目前为止已罚款数intgetfine(intaloca,intb){inta=queue[aloca].number;//a为节点m在source[]中的下标intfine=queue[aloca].currentfine;for(inti=a+1;i

8、=0;//正在扩展的活结点的下标inta;intco