回溯法-简介
回溯法本质是，走不通就退回再走的技术。
优选搜索法：按照选优条件深度优先搜索，以达到目标。
（1）解空间：所有可能解组成的空间。
解的组织形式 -> n元组{x1，x2，...，xn}
3个物品的0-1背包问题 -> {x1，x2，x3}
显约束：对解分量的取值范围的限定。
（2）解空间的组织结构 -> 解空间树
（3）搜索解空间树
隐约束：对能否得到问题的可行解或最优解做出的约束。
剪枝函数：
约束函数：能否得到问题的可行解。
限界函数：能否得到问题的最优解。
决定搜索效率的因素：解空间大小、剪枝函数的好坏。
节点介绍：
扩展节点：正在生成孩子。
活节点：自己已生成，孩子没全部生成。
死结点：孩子全部生成完。
子孙：某结点E的子树的所有结点。
祖宗：从结点E到树根的所有结点。
解题秘籍：
（1）定义解空间：解的组织形式、显约束
（2）确定解空间的组织结构：子集树、排列树、m叉树
（3）搜索解空间：按照深度优先搜索策略，根据隐约束(约束函数和限界函数)，在解空间中，搜索问题的可行解或最优解。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！