部分解空间树-华为认证数通工程师培训教材hcip-datacom-advanced routing switching technology v1.0 培训教材

图 1.33 部分解空间树 8. 答：（1）n=3 时的解搜索空间如图 1.34 所示，不能得到任何叶子结点，所有无 解。 （2）剪枝操作是任何两个皇后不能同行、同列和同两条对角线。 （3）最坏情况下每个结点扩展 n 个结点，共有 nn个结点，算法的时间复杂度为 O(nn)。 (*,*,*) (1,*,*) (1,3,*) (2,*,*) (3,*,*) (3,1,*) 图 1.34 3 皇后问题的解搜索空间 9. 解：用数组 w[0..n-1]存放 n 个集装箱的重量，采用类似判断子集和是否存在解的 方法求解。对应完整的求解程序如下： #include #define MAXN 20 //最多集装箱个数 //问题表示 int n=5,W; int w[]={2,9,5,6,3}; int count; //全局变量，累计解个数 void dfs(int tw,int rw,int i) //求解简单装载问题 { if (i>=n) //找到一个叶子结点 { if (tw==W) //找到一个满足条件的解,输出它 count++; } else //尚未找完 { rw-=w[i]; //求剩余的集装箱重量和 if (tw+w[i]=W) //右孩子结点剪枝：剪除不可能存在解的结点 dfs(tw,rw,i+1); //不选取第i个集装箱,回溯 } } bool solve() //判断简单装载问题是否存在解