子集树与排列树 | 您所在的位置:网站首页 › 日本人财富 › 子集树与排列树 |
在前面的利用回溯法求解01背包问题的时候,我们提到了这个问题的解空间树是子集树,那么什么是子集树呢?与子集树对应的还有一个排列树!它们又有什么区别呢? 概念说明为了说明这两个概念的区别,我们首先假定有一个集合 S 当我们求解的结果是集合S的某一子集的时候,其对应的解空间是子集树。时间复杂度 O(2n) 当我们求解的结果是集合 S 的元素的某一种排列的时候,其对应的解空间就是排列树。时间复杂度O(n!) 解空间为排列树的典型问题就是旅行售货员问题。 简要说明啥是旅行售货员问题,用图论的术语来说就是: 在一个正权的完全图中寻找一个具有最小权的哈密顿回路(由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次。)。 这样就很明确了,我们要寻找的就是所有点集的一个排列(所有点都需要经过且只经过一次)。 算法描述子集树: void Backtrack(int t) { //t 表示当前是树的第t层,即对集合 S 中的第 t 个元素进行判断 if (t > n) output(x); //大于S中总的元素个数 ,遍历完成 else for (int i = 0; i < = l; i++) { // 两种可能 加入或者不加入到解集合 x[t] = i; if (Constraint(t) && Bound(t)){ //满足约数条件 Backtrack(t + 1); //对 t+1 层进行判断 } } }排列树: void Backtrack(int t) { //t 表示集合 S 的第 t 个元素 if (t > n) output(x); else for (int i = t; i |
CopyRight 2018-2019 实验室设备网 版权所有 |