图 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() //判断简单装载问题是否存在解
2021-12-12 14:28:26
7.27MB
答案
1