1 对回溯算法的理解:回溯法适用于组合数较大的问题。首先对问题构造一棵解空间树,按深度优先策略,从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先策略搜索。
2 “子集和”问题的解空间结构和约束函数:
解空间:
约束函数:sum + a[t] <= c;表示当前数加上下一个数的和小于等于目标值才继续搜索子结点,否则,向祖先结点回溯。
3 在本章学习过程中遇到的问题及结对编程的情况:遇到的问题就是剪枝函数的选择以及构造解空间树。编程中,和队友的解题思想经常存在不同,互相交流可以i促进我们的学习。