算法第五章作业

1.你对回溯算法的理解

  回溯法是种以深度优先方式系统搜索问题解的算法。回溯法它遍历问题的所有解和所有情况。通过约束函数和限界函数来剪掉不符合要求或最优解的情况,以此来提高算法的搜索效率。

2.请说明“子集和”问题的解空间结构和约束函数

约束函数:若 现有的和now 加上下一个数,超过了所给的正整数,就不要这个数。

限界函数:要确保除去那些不要的数之后,剩余的数能够大于或等于所给的正整数。

3.请说明在本章学习过程中遇到的问题及结对编程的情况

回溯算法可以说是种很通用的算法,可以解决很多问题,套路都差不多。

在作业当中 算法的约束函数比较容易确定,就是用限界函数剪去得不到最优解的子树那里,如何确认它的上界 是比较困难的。

在子集和问题上,我很快就写出了约束函数,但一直想不出限界函数,最后是同伴提醒过后,才想起来还有那个情况。

原文地址:https://www.cnblogs.com/LuMinghao/p/10164597.html