第五章回溯法20秋人民大学测试答案
第五章回溯法1.[单选题]回溯法的效率不依赖于下列哪些因素（ ）。
A.满足显约束的值的个数
B.计算约束函数的时间
C.计算限界函数的时间
D.确定解空间的时间 ap5u.com q761296021
正确答案:——D——
2.[问答题]设有n件工作分配给n个人。将工作i分配给j个人所需的费用为Cij.现要求为每个人都分配1件不同的工作，并使总费用达到最小。<br>1）画出该问题的解空间树；<br>2）设计回溯算法求解该问题.<br> <br>
正确答案:——1）该问题的解空间树是一棵排列树，4件工作分配给4个人的排列树如下：<br> <br> <br> <br> <br> <br> <br> <br> <br><img width=279 height=211 src="http://learning.cmr.com.cn/Subject/admin/pic/0520/233490B1.gif"><br><img width=279 height=211 src="http://learning.cmr.com.cn/Subject/admin/pic/0520/233490B2.gif"><br>2）参考代码如下： <br>Voidbacktrack(int t)<br>{<br> if ( t＞n ) Compute();<br> else<br> for (int j=t; j＜=n; j++)<br> {<br> swap(r,r);<br> backtrack(t+1);<br> swap(r,r);<br> }<br>}<br>Void Compute()<br>{<br> for(int i=1, temp=0; i＜=n;i++)<br> temp+=p];<br> if(temp＜best)<br> {<br> best=temp;<br> for(i=1; i＜=n; i++)bestr=r;<br> }<br>}<br> <br>——
3.[问答题]在回溯法中，为了避免无效的搜索，通常采用哪两种剪枝策略？<br> <br>
正确答案:——约束剪枝，限界剪枝。<br>——
4.[判断题]回溯法是一种带有系统性，但是不带有跳跃性的搜索算法。
A.错误
B.正确
正确答案:————
5.[判断题]回溯法解旅行售货员问题是的解空间树是排列树。
A.错误
B.正确
正确答案:————
转载注明 无忧答案网
页:
[1]