关于NP类问题求解，下列说法正确的是_____。A．NP类问题求精确解，可能找不到多项式时间复杂性算法；但NP类问题求近似解，则一定能够找到多项式时间复杂性算法B．NP类问题求精确解，可能找不到多项式时间复杂性算法；但NP类问题求近似解，则也可能找不到多项式时间复杂性算法C．虽然能够找到求NP类问题近似解的多项式时间复杂性算法，但所求得的解一定不是满意解D．既然能够找到求NP类问题近似解的多项式时间复杂性算法，则所求得的解就一定是满意解

题目

关于NP类问题求解，下列说法正确的是_____。

A．NP类问题求精确解，可能找不到多项式时间复杂性算法；但NP类问题求近似解，则一定能够找到多项式时间复杂性算法

B．NP类问题求精确解，可能找不到多项式时间复杂性算法；但NP类问题求近似解，则也可能找不到多项式时间复杂性算法

C．虽然能够找到求NP类问题近似解的多项式时间复杂性算法，但所求得的解一定不是满意解

D．既然能够找到求NP类问题近似解的多项式时间复杂性算法，则所求得的解就一定是满意解

相似考题

1.下面关于NP问题说法正确的是()A.NP问题都是不可能解决的问题B.P类问题包含在NP类问题中C.NP完全问题是P类问题的子集D.NP类问题包含在P类问题中

2.下列关于用Excel求解整数规划的说法正确的是()A. 基本步骤与求解一般线性规划问题相同B. 需在约束条件中添加一个“整数”约束C. 在Excel规划求解的“添加约束”对话框中，用“int”表示整数D. 以上说法均不正确

3.关于指派问题下列说法错误的是()。A、任何指派问题一定有最优解B、任何指派问题都可以转化为求最小值、效率非负的指派问题C、匈牙利算法可以求解任何形式的指派问题D、指派问题也可以用表上作业法求解

4.NP类问题包含在P类问题中。()此题为判断题(对，错)。

参考答案和解析
NP类问题求精确解,可能找不到多项式时间复杂性算法;但NP类问题求近似解,则一定能够找到多项式时间复杂性算法 ·
更多“关于NP类问题求解，下列说法正确的是_____。”相关问题

  • 第1题：

    下列关于脂类的说法，不正确的是（ ）。


    正确答案：C
    现有资料表明，满足人体需要的脂肪量是很低的，即使为了供给脂溶性维生素、必需脂肪酸以及保证脂溶性维生素的吸收等作用，所需脂肪亦不多，一般成人每日膳食中有509脂肪即能满足。并不是膳食中脂肪越少越好。

  • 第2题：

    若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是（）

    • A、P类问题
    • B、NP难问题
    • C、NP完全问题
    • D、P类语言

    正确答案:A

  • 第3题：

    下面关于NP问题说法正确的是（）

    • A、NP问题都是不可能解决的问题
    • B、P类问题包含在NP类问题中
    • C、NP完全问题是P类问题的子集
    • D、NP类问题包含在P类问题中

    正确答案:B

  • 第4题：

    关于算法，以下表述正确的是（）。

    • A、算法就是指解决问题的方法和步骤
    • B、算法就是计算方法
    • C、算法的某些步骤具有不确定性
    • D、求解某一类问题的算法是唯一的

    正确答案:A

  • 第5题：

    下列关于运输问题与线性规划问题的关系，（）是正确的。

    • A、运输问题和线性规划问题是两类不同的优化问题
    • B、运输问题和线性规划问题是两类相同的优化问题，但不能用相同的方法求解
    • C、运输问题是一类特殊的线性规划问题
    • D、该两类问题的关系无法确定

    正确答案:C

  • 第6题：

    排序问题是属于（）。

    • A、P问题
    • B、NP问题
    • C、P和NP问题
    • D、以上都不是

    正确答案:A

  • 第7题：

    关于数学模型和数学建模，下列说法正确的是（）。

    • A、数学模型是问题求解的逻辑模型，与时间变量无关
    • B、每一个问题都能建立相应的数学模型
    • C、同一问题只能建立一个数学模型
    • D、数学建模是对实际问题进行抽象、提炼出数学模型的过程

    正确答案:D

  • 第8题：

    问答题
    什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。

    正确答案： 用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。
    用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。
    集合覆盖问题的近似算法采用贪心思想：对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。
    解析： 暂无解析

  • 第9题：

    单选题
    关于算法，正确的说法是（）。
    A

    算法就是程序

    B

    算法就是流程图

    C

    算法就是计算方法

    D

    算法就是对于一个特定问题确定的有限的求解步骤


    正确答案： D
    解析： D项是算法的概念。

  • 第10题：

    单选题
    关于运输问题的说法不正确的是（）。
    A

    它可用线性规划的单纯形表求解

    B

    它可用表上作业法求解

    C

    它的约束方程数等于基变量的数目

    D

    它一定有最优解


    正确答案： D
    解析： 暂无解析

  • 第11题：

    多选题
    下列关于用Excel求解整数规划的说法正确的是（）
    A

    基本步骤与求解一般线性规划问题相同

    B

    需在约束条件中添加一个“整数”约束

    C

    在Excel规划求解的“添加约束”对话框中，用“int”表示整数


    正确答案： B,A
    解析： 暂无解析

  • 第12题：

    单选题
    若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是（）
    A

    P类问题

    B

    NP难问题

    C

    NP完全问题

    D

    P类语言


    正确答案： A
    解析： 暂无解析

  • 第13题：

    关于分配问题的下列说法正确的是（）。

    • A、分配问题是一个高度退化的运输问题
    • B、可以用表上作业法求解分配问题
    • C、从分配问题的效益矩阵中逐行取其最小元素，可得到最优分配方案
    • D、匈牙利法所能求解的分配问题，要求规定一个人只能完成一件工作，同时一件工作也只给一个人做

    正确答案:A,B,D

  • 第14题：

    什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。


    正确答案:用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。
    用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。
    集合覆盖问题的近似算法采用贪心思想：对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。

  • 第15题：

    下列关于用Excel求解整数规划的说法正确的是（）

    • A、基本步骤与求解一般线性规划问题相同
    • B、需在约束条件中添加一个“整数”约束
    • C、在Excel规划求解的“添加约束”对话框中，用“int”表示整数

    正确答案:A,B,C

  • 第16题：

    关于运输问题的说法不正确的是（）。

    • A、它可用线性规划的单纯形表求解
    • B、它可用表上作业法求解
    • C、它的约束方程数等于基变量的数目
    • D、它一定有最优解

    正确答案:C

  • 第17题：

    关于泊松分布参数λ错误的说法是（）.

    • A、μ=λ
    • B、σ2=λ
    • C、σ=λ
    • D、λ=np

    正确答案:C

  • 第18题：

    关于算法，正确的说法是（）。

    • A、算法就是程序
    • B、算法就是流程图
    • C、算法就是计算方法
    • D、算法就是对于一个特定问题确定的有限的求解步骤

    正确答案:D

  • 第19题：

    下列关于质量报警流程的说法，正确的是（）

    • A、C类问题出现5次，启动一级报警
    • B、C类问题出现3次，启动一级报警
    • C、A类问题出现1次，启动一级报警
    • D、B类问题出现3次，启动一级报警

    正确答案:A,C,D

  • 第20题：

    问答题
    用大M法求解下列线性规划问题，并指出问题的解属于哪一类？

    正确答案： 用大M法求解结果：
    （1）无可行解；
    （2）最优解X *=（4  4） T，最优值为28；
    （3）有无界解；
    （4）最优解为X *=（4，0，0） T，最优值为8。
    解析： 暂无解析

  • 第21题：

    单选题
    下面关于NP问题说法正确的是（）
    A

    NP问题都是不可能解决的问题

    B

    P类问题包含在NP类问题中

    C

    NP完全问题是P类问题的子集

    D

    NP类问题包含在P类问题中


    正确答案： D
    解析： 暂无解析

  • 第22题：

    单选题
    关于泊松分布参数λ错误的说法是（）
    A

    μ=λ

    B

    σ2=λ

    C

    σ=λ

    D

    λ=np


    正确答案： B
    解析： 暂无解析

  • 第23题：

    单选题
    对于计算机求解问题，下列叙述正确的是（）。
    A

    利用计算机进行问题求解，是用机器代替人，属于人工智能应用

    B

    计算机求解问题主要适用于自然系统，社会系统无法建模

    C

    计算机进行问题求解是利用了计算机运行速度快、精度高、自动化和不知疲倦的特性

    D

    只有通过计算机执行求解算法才能得到问题的解


    正确答案： B
    解析： 暂无解析

  • 第24题：

    单选题
    下列关于运输问题与线性规划问题的关系，（）是正确的。
    A

    运输问题和线性规划问题是两类不同的优化问题

    B

    运输问题和线性规划问题是两类相同的优化问题，但不能用相同的方法求解

    C

    运输问题是一类特殊的线性规划问题

    D

    该两类问题的关系无法确定


    正确答案： A
    解析： 暂无解析

相关内容