脚本宝典收集整理的这篇文章主要介绍了算法第五章作业报告,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
算法第五章作业报告
题目:
设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j 处购得的部件i的重量,cij是相应的价格。 试设计一个算法,给出总价格不超过d的最小重量机器设计。
第一行有3 个正整数n ,m和d, 0<n<30, 0<m<30, 接下来的2n 行,每行n个数。前n行是c,后n行是w。
输出计算出的最小重量,以及每个部件的供应商
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2
在这里给出相应的输出。例如:
4 1 3 1 题目分析:先输入n,m,w.n代表机器的部件数量,前n行代表部件的价格c,后n行代表部件的重量w。给出总价格不超过d的最小重量机器设计。我们需要保存好选择结点的总重量与总价格,我们需要用约束函数在扩展结点处不满足约束的子树,价格不能超过d。
再用限界函数减去得不到最优解的子树,从而得到最小重量设计。
1.1“最小重量机器设计问题"的解空间说明
解空间为每个部件选择的供应商,解空间的长度为n的向量组成,即每个部件都可从m个供应商中选。解空间应该为mn
为了能方便用回溯法对整个解空间进行搜索,我们通常把解空间组织成树的形式。对于“最小重量机器设计问题",也可以用树来表示其解空间。
第i层代表第i件物品,每个节点有m个分支,代表不同的供应商。
t :第t个物品的选择
nw:用于记录前t个部件选择供应商后的部件总重量
nc:前t个部件的总价值(均要判断是否满足小于d的条件是否成立)
回溯法就是按照深度优先策略搜索,是带有系统性与穷举所有可能性得出最优解的算法,回溯算法可以判断当前状态是否符合问题的条件,可以跳过不符合要求结点为根的子树搜索适合解组合数较大的问题。并且回溯法可以利用约束函数和限界函数在搜索过程中进行剪枝,剪去不符合要求的子树来避免无效搜索,提高搜索效率。
以上是脚本宝典为你收集整理的算法第五章作业报告全部内容,希望文章能够帮你解决算法第五章作业报告所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。