2. 计算机
  3. 阅读下列说明和C代码，将应填入 (n) 处的字句。 [说明] 设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。

阅读下列说明和C代码，将应填入 (n) 处的字句。 [说明] 设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。

admin2012-03-21  35
问题 阅读下列说明和C代码，将应填入  (n)  处的字句。
   [说明]
   设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。
   采用回溯法来求解该问题：
   首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1，2，…，m)，将解空间用树形结构表示。
   接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活结点，同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。判断当前的机器价格(c11)是否超过上限(cc)，重量(w11)是否比当前已知的解(最小重量)大，若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断当前的机器价格(c11+c21)是否超过上限(cc)，重量(w11+w21)是否比当前已知的解(最小重量)大。若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活结点为止。
   [C代码]
   下面是该算法的C语言实现。
   (1)变量说明
   n：机器的部件数
   m：供应商数
   cc：价格上限
   w[][]：二维数组，w[j]表示第j个供应商供应的第i个部件的重量
   c[][]：二维数组，cD]表示第j个供应商供应的第i个部件的价格
   bestW：满足价格上限约束条件的最小机器重量
   bestC：最小重量机器的价格
   bestX[]：最优解，一维数组，bestX表示第i个部件来自哪个供应商
   cw：搜索过程中机器的重量
   cp：搜索过程中机器的价格
   x[]：搜索过程中产生的解，x表示第i个部件来自哪个供应商
   i：当前考虑的部件，从0到n-1
   j：循环变量
   (2)函数backtrack
   int n=3;
   int m=3;
   int cc=4;
   int w[3][3]={{1,2,3},{3,2,1},{2,2,2}};
   int c[3][3]={{1,2,3},{3,2,1},{2,2,2}};
   int bestW=8;
   int bestC=0;
   int bestX[3]={0，0，0};
   int cw=0;
   int cp=0;
   int x[3]={0，0，0};
   int backtrack (int i){
   int j=0;
   int found=0;
   if(i＞n-1){  /*得到问题解*/
       bestW=cw;
       bestC=cp;
       for(j=0; j＜n;  j++){
         (1)  ;
       }
   return 1;
     }
     if (cp＜=cc)(/*有解*/
       found=1;
     }
   for(j=0;  (2)  ;  j++){
     /*第i个部件从第j个供应商购买*/
     (3)  ;
       cw=cw+w [j];
       cp=cp+c [j];
   if (cp＜=cc&&  (4)   ){/*深度搜索，扩展当前结点*/
       if (backtrack(i+1)){    found -1;  )
     }
     /*回溯*/
     cw=cw - w [j];
       (5)  ;
     }
     return found;
   }

(5)
选项
答案cp=cp-c[i][j]
解析 本题考查算法的设计和分析技术中的回溯法。
   回溯法是一种系统搜索问题解的方法，在包含问题所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法在到达解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。若肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则进入该子树，继续按深度优先的策略进行搜索。回溯法在求问题的最优解时，要回溯到根，且根结点的所有子树都已经被搜索遍才结束。
   根据上述思想和题干说明，对实例：部件数n=3，厂商数m=3，具体的重量和价格如表4-1所示。

构造该实例的解空间树如图4-1所示。

图4-1中结点编号表示生成该结点的顺序。边上的编号表示哪个部件选择哪个厂商，如x(2)=1，表示第2个部件来自厂商1。结点旁边的两个数字表示当前解或部分解对应的重量和价格，如2:2表示重量为2，价格为2。从图4-1可以看出，最优解是结点20表示的解，即x(1)=1，x(2)=3，x(3)=1，即第1个部件来自厂商1，第2个部件来自厂商3，第3个部件来自厂商1，总的价格和重量分别为4和4。当然，本实例的最优解还可以是x(1)=1，x(2)=3，x(3)=2和x(1)=1，x(2)=3，x(3)=3，分别对应解空间树上的21号和22号结点。
   代码中的空(1)处是得到问题解之后，将搜索过程中产生的重量cw、价格cp和解x放到最终重量bestW、价格bestC和解bestX中，因此空格(1)处填写bestX[j]=x[j]。空(2)处的for循环是考虑第i个部件选择哪个厂商，因此j从0到m-1依次检查，此处应填j＜m。对搜索过程中产生的重量cw、价格cp和解x的值进行设置，因此空(3)处应填x=j，表示第i个部件选择厂商j。空(4)是判断当前结点是否要扩展，若当前获得的价格比目前最优解更优，且重量没有超过当前得到的最优重量，即cp＜=cc且cw＜bestW，则扩展当前结点，否则回溯。在回溯过程中，需要把原来选择的部件的价格和重量从搜索过程中产生的重量cw和价格cp中去掉，因此空(5)应填cp=cp=c[j]。
转载请注明原文地址:https://kaotiyun.com/show/HeDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)