首页 > 其他 > 详细

blog 14 | 回溯法总结

时间:2019-12-19 23:36:11      阅读:113      评论:0      收藏:0      [点我收藏+]

第五章 回溯法总结

一、对回溯算法的理解

 回溯法和贪心法相比,贪心法是从上到下只进行深度搜索,它的代价取决于子问题的数目,也就是树的高度,每次在当前问题的状态上作出的选择都是1,换言之,它不进行广度搜索,这也造成了它的一个缺点:它得出的解不一定是最优解,很有可能是近似最优解。回溯法是从上到下进行深度搜索,如果深度搜索没有进行到底而不满足决策函数,再通过for循环进行广度搜索。所以它是深度搜索和广度搜索并行。求出的解也一定是最优解。

 

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

子集和”问题的解空间结构是一棵集合树,约束函数是根据当前的扩展结点的值检测是否超过目标值。

 

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

1、一开始为了能够剪枝,选择先用快排把集合里的数排序,结果因为题目答案并非有序,导致错误。

2、结对编程步调一致,锻炼了我看并迅速解读他人代码的能力。

blog 14 | 回溯法总结

原文:https://www.cnblogs.com/gzq18/p/12070671.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!