优先队列最小重量机器设计问题

最小重量机器设计问题1.问题描述：设某机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设𝑤𝑖𝑗是从供应商j处购得的部件i的重量，𝑐ij是相应的价格。设计一个优先队列式分支限界法，给出总价格不超过d的最小重量机器设计。2.算法设计问题的解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计。开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故level=0，source=0，value=0，weight=0。MinLeaf记录满足条件的节点即供应商的选择。while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过d并加以扩展，队列为空时则结束循环。当fartherNode-level等于n时，此时扩展结点是叶节点，判断是否最优，若最优则记录节点。当fartherNode-leveln时，算法依次产生当前扩展结点的所有儿子节点。对于当前扩展结点的一个儿子结点，计算出当前的重量，当小于当前的最小重量时，将儿子结点插入到活结点优先队列中，而当不下于当前最小重量时，以当前这个结点为根的子树中不可能有比当前最小重量部件选择更好的解，故可将此结点舍去。若在一结点所计算的花费大于所给的最小花费，则剪去以此节点为根的子树。3.实现效果4.代码：最小重量机器设计问题.txt