实验6子集和问题的回溯算法设计与实现(报告).doc资源-CSDN文库

版权申诉

49 浏览量 2022-05-29 22:37:07 上传评论收藏 98KB DOC 举报

资源推荐

资源详情

资源评论

1

湖南大学算法分析与设计实验报告实验 6 子集和问题的回溯算法设计与实现

实验 6 子集和问题的回溯算法设计与实现

一、实验目的

1、掌握回溯法解题的基本思想；

2、掌握回溯算法的设计方法；

3、针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。

二、实验内容

1、认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；

2、了解子集和数问题及解向量的定长和变长状态空间表示；

3、针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；

4、分析深度优先扩展状态空间树节点或回溯的条件；

5、分析和设计生成解向量各分量可选值的实现方法；

6、设计和编制回溯算法的递归和迭代程序。

【实验题】：

组合数问题：找出从自然数 1，2，…，n 中任取 r 个数的所有组合。

三、算法的原理方法

回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题

的候选解按某种顺序逐一枚举和检验。

当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还

不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续

试探。

如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解

的规模，以继续试探的过程称为向前试探。

可以采用回溯法找问题的解，将找到的组合以从小到大顺序存于 a[0]，a[1]，

…，a[r-1]中，组合的元素满足以下性质：

（1）¿¿a[i+1]>a[i]，后一个数字比前一个大；

（2）¿¿a[i]-i<=n-r+1。

按回溯法的思想，找解过程可以叙述如下：

2015 06 19

剩余13页未读，继续阅读

内容反馈

版权申诉

oligaga

粉丝: 50
资源: 2万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip