最小机器质量问题备课讲稿

1、最小机器质量问题精品文档课程设计说明书设计题目：最小重量机器设计问题专业：班级：设计人：山东科技大学2012年12月20日课程设计任务书学院：_专业：班级：姓名：一、 课程设计题目：最小重量机器设计问题二、课程设计主要参考资料(1)三、课程设计应解决的主要问题(2)(3)(4)四、课程设计相关附件(如：图纸、软件等)：(1)收集于网络，如有侵权请联系管理员删除五、任务发出日期:2013-11-21课程设计完成日期:2013-12-20指导教师签字:系主任签字：指导教师对课程设计的评语成绩:指导教师签字：年 月日二分查找程序的实现一、设计目的1、了解分支限界法的基本思想2、运用分支限界法解决最小

2、重量机器设计问题二、设计要求1、问题描述：设某一机器由n个部件组成，每一种部件都可以从 m个不同的供应商处购 得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格，给出 总价格不超过d的最小重量机器设计。三、设计说明（一）、需求分析1、分支限界法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题 的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦 成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可 行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复

3、上述结点扩展 过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2、常见的两种分支限界法（1）队列式（fifo）分支限界法按照队列先进先出（fifo）原则选取下一个节点为扩展节点。数据结构：队列（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。数据结构：堆最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小效益优先3、分支限界法与回溯法的不同(1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约 束条件的解中找出在某种意义下的最优解。(2)搜索

4、方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。4、优先队列式分支限界法程序框架设t为状态空间树的根结点：c(x)为消耗估计函数；初始化优先队列 q计算c(t),并将t入队；循环，直到队列q空(无解)；结点e出队；若e是回答结点，则输出解或求解路径，求解结束；否则，检查e的子结点x；若x满足约束条件，则计算c(x),并将x入队；记录搜索路径；(二)、概要设计1、设计思路：解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还 设有选定部件是哪个供应商提供的，

5、故 cv=0, cw=o, position=0 , peer=0, 1i n o x1:n记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展 结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当 peer=n时, 此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。2、优先级的设定：优先级的设定，当队列中有两个结点的重量是相同的时候，那么设定为，level大的优先级就更高一点，也就是说，更接近于叶子结点的那个结点更优 先。目的就是为了更快的刷新出最小的重量，方便后面的剪枝。如果说没有两 个结点重量相同，那就

6、重量更小的优先。优先级优化思路：类似于旅行售货商问题的优先级设定，记录剩余的未购 买原件中的，单个原件购买的最小价值之和。（三）、详细设计#include #include #define int_max 100using namespace std;int *c = null;int *w = null;int minvalue;/ 最小重量int n,m,d;/n表示供应商个数，m表示零件个数，d表示价格上限class node/优先队列的结点public:node();int weight;/ 质量int val;/ 价格int source;node *father;/ 父结点int

7、t;重写比较运算符bool operator other.t)return true;else if (t = other.t)if (weight other.weight)return true; elsereturn false;elsereturn false;；node *minleaf;void minmacwei()node initial;initial.father = null;initial.weight = 0;initial.val = 0;initial.t = 0;initial.source = 0;priority_queue heap;heap.push(i

8、nitial);while(!heap.empty()node *farthernode = new node(heap.top();heap.pop();if (farthernode-t = n)if (farthernode-val val;minleaf = farthernode;elsefor (int i = 1; i weight + wfarthernode-t +1i t = farthernode-t + 1;newnode-father = farthernode;newnode-source = i;newnode-weight = farthernode-weigh

9、t + wnewnode-ti;newnode-val = farthernode-val + cnewnode-ti;heap.push(*newnode););int main()coutn;coutm;coutd;c = new int *n + 1;w = new int *n + 1;minvalue = int_max;minleaf = null;for (int i = 0; i = n; +i)ci = new intm + 1;wi = new intm + 1;)for (int i = 1; i = n; +i)for (int j = 1; j = m; +j)cou

10、t第i个供应商的第jcij;)for (int i = 1; i = n; +i)(for (int j = 1; j = m; +j)(cout第i个供应商的第jwij;)minmacwei();cout最小重量为：minvalueendl;for (int i = 0; i = n; +i)(delete ci;delete wi;delete c;delete w;return 0;四、运行结果及分析c：u5enadministrsn：口日5ct口f# *e4 7 2 4 15 91123_7211量量二i至l-jyhfl-j a - u - - j - - .te - -l - - f

11、ahw j - - -fc - 丁江;41件止4,“一，”一 2才重裹重筌羲蓑t 攵 1211212器鱼:=g.erbg.en f&.nl工 r&.hs-手一 - - -3 .ich -13=3牛咎商商商商商一同商商也应督应应督豺万以叱二：)骞半ffilffil蜀和舟却皆发process returned idexecut ion t ime - 21. v42 sfness any key to continue.算法时间复杂度：程序中最大的循环出现在函数minmacwei()中，而此函数遍历排列树的时 间复杂度为o(n!),故该算法的时间复杂度为 o(n!)。五、总结通过这次实验我了解到分支限界法是一种在问题的解空间树上搜索问题解的算法。分支限界法的搜索策略是，