算法分析与设计答案2023

第十三章测试

1.

给定问题p，若有算法A，存在一个常数K>=0，使得问题p的所有实例I，总有：|A(I)-OPT(I)|<=K,则称算法A为解答问题p的绝对近似算法。

A:错 B:对
答案:B
2.

NP-hard 问题属于NP

A:错 B:对 3.

当P不等于NP时，NP-hard优化问题存在多项式时间绝对近似算法。

A:对 B:错 4.

绝大多数NP-hard问题存在多项式时间绝对近似算法

A:对 B:错 5.

若P不等于NP，则最大独立集问题存在多项式时间绝对近似算法。

A:对 B:错 6.

最大优化问题的近似性能比小于1，越接近1越说明算法好

A:错 B:对 7.

多项式时间近似方案的近似性能比是1 + q，q>0.

A:对 B:错 8.

多项式时间近似方案的时间复杂度是P(n, 1/ q) ， P是多项式函数, q>0。

A:对 B:错 9.

近似算法的设计方法有（）

A:组合技术 B:线性规划和舍入 C:贪心 D:定价法 10.

下面说法错误的是（）

A:完全多项式时间近似方案的近似性能比是1+p，p>0 B:近似性能比不可能小于1 C:NP-hard与NPC区别在于是否属于NP D:旅行商问题的近似性能比不会小于2