作者:hhh5460
时间:2017年6月3日
用回溯法子集树模板解决了这么多问题,这里总结一下使用回溯法子集树模板的步骤:
1、确定元素及其状态空间(精髓)
对每一个元素,遍历它的状态空间,其它的事情交给剪枝函数!!!(正是这一点,使得它无愧于“通用解题法”这个称号!)
2、确定解的编码及解的长度是否固定
若解的长度固定,那么x[k] = i
若解的长度不固定,那么x.append(i) ... x.pop(i)
3、确定是求最优解,任一解,还是全部解
如果是求最优解,额外增加两个全局变量:best_x, best_value
4、问题是否有其特殊性
是的话,想法解决之
最后强调一下:
精髓 —— 元素-状态空间分析大法
- 对每一个元素,遍历它的状态空间,其它的事情交给剪枝函数!