算法第五章作业

1.你对回溯算法的理解

用回溯法可以系统地搜索一个问题的所有解或任一解,是既带有系统性又带有跳跃性得搜索算法。按深度优先策略,从根节点出发搜索解空间树,当搜索过程中发现已不满足已知条件时,则往回移动,知道找到所要求得解为止。

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

解空间结构:对于每个数有两种选择:放进子集或不放进子集。从而形成一颗解空间二叉树,树的结点表示放入子集的数的情况。

约束函数:(1)当前子集和加上待选数后要小于等于给定子集和; (2)当前子集和加入剩余数和要大于等于子集和。

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

回溯法本质上是一种枚举法,概念和思想好理解,在编写代码的时候一般是在给出模板的基础上修改,重点是找好约束函数。

原文地址:https://www.cnblogs.com/chengyi1102/p/12093877.html