张晨旭　SA20010055

问题描述

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。设计一个优先队列分支限界法，给出总价格不超过d的最小重量机器设计。

问题分析

本题要求使用优先队列式分支限界法解决最小重量机器设计问题。
算法思路
对于在某一个供应商是否购买某一零件，可以将这个过程抽象化为子集树模型。该树的第i层则代表第i个零件的购买情况，每个商家j对应一棵子树。从根节点开始，对于当前讨论的节点我们将之当作扩展节点，遍历该扩展节点的所有子节点，将其中符合条件的子节点全部插入优先队列中（判断条件运用剪枝函数）。当遍历完后，从优先队列中取出在当前情况下重量最小的节点继续向下进行迭代，直到到达某叶子节点后，记录下当前情况下的最小重量，然后继续将优先队列中的活节点依次出队，直到优先队列为空，整个子集树只剩下一条最优路径。

优先队列：使用最小堆实现优先队列。
约束函数：对于该节点到最终叶子节点中所有节点价格的最小值的和超过了要求的节点（即总价超过d），直接置剪去，不再考虑其子树。
限界函数：对于该节点到最终叶子节点中所有节点重量最小值的和大于目前得到的最小重量，直接剪去以该节点为根的子树。

代码实现

  1. void MinWeightMachine()
  2. {
  3.     int i,j;
  4.     bestw = INT_MAX;
  6.     Node initial;
  7.     initial=createNode(0,NULL,0,0,0);
  8.     QueuePriority(initial);      //计算优先级
  9.     priority_queue<Node> heap;   //用优先队列，建立一个最小堆。加入进去就会自动排好序的。
  10.     heap.push(initial);
  12.     while(!heap.empty())
  13.     {
  14.         Node *pNode = new Node(heap.top());
  15.         heap.pop();//队首元素作为父节点出队，即优先级值小的活结点先扩展
  16.         if(pNode->level == n)//到达叶节点，不能扩展 ,得到一个解
  17.         {
  18.             if(pNode->weight <bestw)   //更新
  19.             {
  20.                 bestw = pNode -> weight;
  21.                 //MinValue  = pNode ->val;
  22.                 leaf = pNode;   //记录是最后是哪个结点数据,便于回溯找最优解
  23.             }
  24.         }
  25.         else
  26.         {
  27.             for(i=1;i<=m;i++)//扩展结点，依次选择每个售货商，每次都是m叉树
  28.             {
  29.                 //可行性剪枝和限界剪枝
  30.                 if(constraint(pNode,i))
  31.                 {
  32.                     Node newNode;//生儿子结点
  33.                     newNode=createNode(pNode->level +1,pNode,i,pNode->val + c[pNode->level +1][i],pNode->weight + w[pNode->level +1][i]);
  34.                     QueuePriority(newNode);     //计算优先值
  35.                     heap.push(newNode);//儿子入队
  36.                 }
  37.             }
  38.         }
  39.     }
  40. }

实验结果

按照题目中的输入文件，实验测试结果如下，可以正确计算出最小重量机器设计的结果。
hw6-4.png