搜索

求思路:编写一个递归函数用来输出n 个元素的所有子集

gecimao 发表于 2019-05-27 15:56 | 查看: | 回复:

  对于用回溯法求解的问题,首先要将问题进行适当的转化,得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树,枚举每种可能的解的情况;从而得出结果。但是,回溯法中通过构造约束函数,可以大大提升程序效率,因为在深度优先搜索的过程中,不断的将每个解(并不一定是完整的,事实上这也就是构造约束函数的意义所在)与约束函数进行对照从而删除一些不可能的解,这样就不必继续把解的剩余部分列出从而节省部分时间。

  (三)扩展节点、活结点、死结点:所谓扩展节点,就是当前正在求出它的子节点的节点,在DFS中,只允许有一个扩展节点。活结点就是通过与约束函数的对照,节点本身和其父节点均满足约束函数要求的节点;死结点反之。由此很容易知道死结点是不必求出其子节点的(没有意义)。

  在分支界限法中,一般用的是FIFO或最小耗费搜索;其思想是一次性将一个节点的所有子节点求出并将其放入一个待求子节点的队列。通过遍历这个队列(队列在遍历过程中不断增长)完成搜索。而DFS的作法则是将每一条合法路径求出后再转而向上求第二条合法路径。而在回溯法中,一般都用DFS。为什么呢?这是因为可以通过约束函数杀死一些节点从而节省时间,由于DFS是将路径逐一求出的,通过在求路径的过程中杀死节点即可省去求所有子节点所花费的时间。FIFO理论上也是可以做到这样的,但是通过对比不难发现,DFS在以这种方法解决问题时思路要清晰非常多。

  如果能确保全集中的元素不会相同,则对于包含n个元素的全集A={a1,a2,...an},其全排列可以描述为从数字从0到(2^n)-1的遍历,然后将这个数字表达成2进制描述,当某一位i为1时,填入响应的ai即可。

本文链接:http://windsorflowers.net/diguixiangliang/244.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部