算法设计与分析习题 - 图文

个人精品文档资料

5、利用FIFO分支限界算法,给出下列0－1背包最优装载的求解步骤？

背包载重：M＝10； 物品重量：w1＝6、w2＝5、w3＝5； 物品价值：p1＝42、p2＝25、p3＝30

解：1)解空间：

2）求解过程：

欢迎大家下载学习 21

个人精品文档资料

第8章 NP完全性理论

1、什么是易解问题？什么是难解问题？难解问题分为哪两类？

答：1）易解问题：人们将存在多项式时间 算法的问题称为易解问题;

2）难解问题：将需要在指数时间内解决的问题称为难解问题；

3）难解问题有两类： 1）不可判定问题 2）非决定的难处理问题 。

2、什么是不可判定问题？什么是非决定的难处理问题？

答：1）不可判定问题 ：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。

2）非决定的难处理问题： 这类问题是可判定的（即可解的）。 但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。

3、什么是P类问题？什么是NP完全问题？

答：1）P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。

2）NP完全问题：对于某问题，很难找到其多项式时间的算法(或许根本不存在)，但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。 这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。

4、列出几个典型的NP完全问题？ 答：（1）图着色问题COLORING （2）路径问题LONG-PATH

（3）顶点覆盖问题VERTEX-COVER （4）子集和问题SUBSET-SUM

（5）哈密尔顿回路问题HAM-CYCLE （6）旅行商问题TSP

（7）装箱问题BIN-PACKING ， 能否用k个箱子来装n个物品；

欢迎大家下载学习 22