设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部..

2024年下半年下午试卷案例

第 2 题

知识点

回溯法

设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量W_ij和价格C_ij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。
采用回溯法来求解该问题：
首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1，2，···，m} 将解空间用树形结构表示。
接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活结点，同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。判断当前的机器价格(c₁₁)是否超过上限(cc)，重量(w₁₁) 是否比当前已知的解（最小重量）大，若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断当前的机器价格(c₁₁+c₂₁)是否超过上限(cc)，重量(w₁₁+w₂₁)是否比当前已知的解(最小重量)大。若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活结点为止。

问题：2.1 【C代码】

知识点讲解

· 回溯法

回溯法

1）基本思想

回溯法也称试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；如果当前候选解除了不满足问题规模要求外，满足所有其他要求，继续扩大当前候选解的规模，并继续试探；如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

在回溯法中，放弃当前候选解、寻找下一个候选解的过程称为回溯；扩大当前候选解的规模并继续试探的过程称为向前试探。

2）典型应用：n皇后问题

n皇后问题是源于国际象棋的一个问题，n皇后问题要求在一个n×n格的棋盘上放置n个皇后，使得它们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之在同一行或同一列或同一条斜线上的其他任何棋子。因此n皇后问题等价于要求在一个n×n格的棋盘上放置n个皇后，使得任何两个皇后不能被放在同一行或同一列或同一条斜线上。

求解算法如下：

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5