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

题目

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

相似考题

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

2.问题的状态空间包含以下集合,即()。A.B.所有可能的问题初始状态集合SC.操作符集合FD.目标状态集合GE.描述谓词集合P

3.【说明】下图是某商场购物系统的一个类图，图中属性和方法前的"+"、"#"和"- " 分别表示公有成员、保护成员和私有成员。其中：（1） 类Manager重新实现了类Customer的方法 calMoney( );（2） 方法calMoney( )，根据每位顾客的购买情况（buyNum）、浏览商品的情况（scanNum）计算商品的热度。（3）类Admin中的方法statMoney（）中首先调用了该类的方法load( )，获取顾客列表，然后调用了类Customer中的方法calMoney( )。现拟采用面向对象的方法进行测试。 【问题1】(4分)图4-1 所示的类图中，类Manager和类Customer之间是什么关系?该关系对测试的影响是什么?【问题2】(6分)（1） 类Manager重新实现了类Customer的方法calMoney( )，这是面向对象的什么机制？是否需要重新测试该方法？（2） 类Manager中的方法getMoney ( )继承了其父类 Customer 的方法getMoney ( )，是否需要重新测试该方法? 【问题3】（6分）（1）请结合题干中说明的描述，给出测试类Customer方法calMoney（）时的测试序列；（2）请给出类图中各个类的测试顺序。【问题4】(4分)从面向对象多态特性考虑，测试方法statMoney( )时应注意什么？

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

更多“什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的”相关问题

  • 第1题：

    阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】下图是某商场购物系统的一个类图，图中属性和方法前的"+"、"#"和"- " 分别表示公有成员、保护成员和私有成员。其中：



    （1） 类Manager重新实现了类Customer的方法 calMoney( );（2） 方法calMoney( )，根据每位顾客的购买情况（buyNum）、浏览商品的情况（scanNum）计算商品的热度。（3）类Admin中的方法statMoney（）中首先调用了该类的方法load( )，获取顾客列表，然后调用了类Customer中的方法calMoney( )。现拟采用面向对象的方法进行测试。 【问题1】(4分)图4-1 所示的类图中，类Manager和类Customer之间是什么关系?该关系对测试的影响是什么?【问题2】(6分)（1） 类Manager重新实现了类Customer的方法calMoney( )，这是面向对象的什么机制？是否需要重新测试该方法？（2） 类Manager中的方法getMoney ( )继承了其父类 Customer 的方法getMoney ( )，是否需要重新测试该方法?【问题3】（6分）（1）请结合题干中说明的描述，给出测试类Customer方法calMoney（）时的测试序列；（2）请给出类图中各个类的测试顺序。【问题4】(4分)从面向对象多态特性考虑，测试方法statMoney( )时应注意什么？


    答案：
    解析：
    【问题1】（1） 泛化关系；（2） 继承的成员函数是否需要测试；对父类的测试是否能用到子类上。【问题2】
    （1）、多态机制；需要重新测试，因为在子类中重新进行了定义，所以需要重新测试；（2）、不需要重新测试，因为子类继承了父类的方法，只要父类的该方法通过测试了即可。【问题3】
    （1） 测试序列：setBuyNum( )——setScanNum( )——calMoney( ) ——getMoney( ) ；（2）先测试Customer类，然后Manager类，最后测试Admin类。【问题4】
    只需要在原有的测试分析基础上增加对测试用例中输入数据的类型的考虑即可。先测试基类，然后再分别依据输入数据设计不同的测试用例。
    【解析】
    【问题1】
    考察类图的泛化关系。泛化关系也就是继承关系，也称为“is-a-kind-of”关系，泛化关系用于描述父类与子类之间的关系，父类又称作基类或超类，子类又称作派生类，泛化关系通常用带空心三角形的直线来表示。对泛化关系有三个要求：1、子类与父类应该完全一致，父类所具有的属性、操作，子类应该都有；2、子类中除了与父类一致的信息以外，还包括额外的信息；3、可以使用父类的实例的地方，也可以使用子类的实例；【问题2】
    该题考察面向对象的多态机制和继承机制。多态就是在使用父类的引用调用方法的时候，不是使用父类中的方法，而是父类指向的对象的方法，这样就实现了多态。继承是指在一个类基础上定义一个新类，原有的类叫做父类，新生成的类叫子类，继承的过程是一个从一般到特殊的过程。【问题3】
    根据题干提示，方法calMoney( )，根据每位顾客的购买情况（buyNum）、浏览商品的情况（scanNum）计算商品的热度。类之间测试的先后关系可以参考各种关系的强弱顺序：泛化 = 实现 > 组合 > 聚合 > 关联 > 依赖。【问题4】
    题干描述，方法statMoney（）需要调用Customer中的calMoney（）。而该方法在Customer和Manager中有不同的实现，因此需要同时考虑Customer和Manager中的calMoney（）。

  • 第2题：

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

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

    正确答案:B

  • 第3题：

    请解释什么是P问题，NP问题。


    正确答案: 如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。
    NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

  • 第4题：

    邮递员问题，或者叫做最短路径问题是（）。

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

    正确答案:B

  • 第5题：

    排序问题是属于（）。

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

    正确答案:A

  • 第6题：

    计划类文书的写作要注意什么问题？


    正确答案: （1）分析情况要认真细致
    （2）确定目标要实事求是
    （3）措施步骤要切实可行
    （4）条目要分明，语言要简洁

  • 第7题：

    NP完全问题指的是什么？请举例。


    正确答案: NP完全问题指的是：用目前知道的最好的方法求解，问题求解需要花费的时间（或称为问题求解的复杂性）随问题规模增大以指数关系增长。推销员旅行问题就是一个NP完全问题，我们至今还不知道对NP完全问题是否有花费时间较少的求解方法。例如，可使求解时间随问题规模按多项式关系增长。组合调度问题的求解方法已经应用于交通运输调度、列车编组、空中交通管制和军事指挥自动化等系统。

  • 第8题：

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

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

  • 第9题：

    问答题
    请解释什么是P问题，NP问题。

    正确答案： 如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。
    NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
    解析： 暂无解析

  • 第10题：

    问答题
    集合论原理用于聚类问题的思想是什么？

    正确答案： 聚类问题描述为：给定数据集合D，把它划分成一组聚类：{C1，C2，…Ck}，Ci∈D，使得不同类中的数据尽可能的不相似（或距离较远），而同一类中的数据尽可能的相似（或举例较近）。集合论原理用于解决聚类问题时，主要是按数据集中元素间的距离远近或相似度打消，聚成多个类别集合。
    解析： 暂无解析

  • 第11题：

    问答题
    NP完全问题指的是什么？请举例。

    正确答案： NP完全问题指的是：用目前知道的最好的方法求解，问题求解需要花费的时间（或称为问题求解的复杂性）随问题规模增大以指数关系增长。推销员旅行问题就是一个NP完全问题，我们至今还不知道对NP完全问题是否有花费时间较少的求解方法。例如，可使求解时间随问题规模按多项式关系增长。组合调度问题的求解方法已经应用于交通运输调度、列车编组、空中交通管制和军事指挥自动化等系统。
    解析： 暂无解析

  • 第12题：

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

    P类问题

    B

    NP难问题

    C

    NP完全问题

    D

    P类语言


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

  • 第13题：

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

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

    正确答案:A

  • 第14题：

    请列举几个常见的NP完全问题。


    正确答案: 1）合取范式的可满足性问题；
    2）三元合取范式的可满足性问题；
    3）团问题；
    4）顶点覆盖问题；
    5）子集和问题；
    6）哈密顿回路问题；
    7）旅行售货员问题。

  • 第15题：

    什么是道口A类违纪问题？


    正确答案: （1）不执行班前休息制度。
    （2）当班离岗、串岗。
    （3）当班带酒气上岗。
    （4）当班饮酒。
    （5）当班做与工作无关事项。
    （6）当班进行赌博、打扑克、打麻将、下象棋等娱乐活动。
    （7）当班睡觉（三班半、四班制，其它班制未按规定休息）。
    （8）不按规定正确着装和使用劳动保护用品。
    （9）当班用无线电台谈与工作无关的事情。
    （10）行车主要场所有闲杂人员逗留。
    （11）未经领导批准私自串班。
    （12）无故擅自关闭或随意挪动、拆卸报（预）警设备。

  • 第16题：

    P问题是可计算问题，NP问题也是可计算问题


    正确答案:正确

  • 第17题：

    计算学科的根本问题是（）。

    • A、什么能被有效地自动进行
    • B、NP问题
    • C、工程设计
    • D、理论研究实验方法

    正确答案:A

  • 第18题：

    何谓P、NP、NPC问题？


    正确答案: 1.P（Polynomial问题）：也即是多项式复杂程度的问题。
    2.NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
    3.NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。

  • 第19题：

    请简述无类域间路由（CIDR）的概念，无类域间路由和传统路由（Classical route）的区别是什么？它的好处和使用时需要注意的问题是什么？


    正确答案: CIDR不使用传统的有类网络地址分配原则，即不再区分A、B、C类网络地址。在分配IP地址段时也不再按照有类网络地址的类别进行分配，而是将IP网络地址空间看成是一个整体，并划分成连续的地址块。然后采用分块的方法进行分配。
    CIDR的好处是可以缓解IPV4地址空间快速被耗尽的问题。
    在使用时应当注意路由汇总的问题，由于不再区分ABC类网络地址，网络路由器内含有的IP地址条目快速增加。这将导致城域网内核心路由器中的路由条目非常庞大。在进行地址规划时可以将连续的地址空间块总结成一条路由条目。路由器不再需要对外声明内部网络的所有IP地址空间段。这样，就大大减小了路由表中路由条目的数量。

  • 第20题：

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

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

    B

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

    C

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

    D

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


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

  • 第21题：

    问答题
    什么是道口A类违章问题？

    正确答案： （1）擅自使用不允许使用的电热器具。
    （2）间休时间虽然已关闭栏杆或栏门，但未加锁。
    （3）道口员不出场接车或接车出场晚（列车接近500m时仍未出场）。
    （4）道口员擅自关闭电铃及报警设备。
    （5）多线地段有人看守道口，在未确认其它线有无列车开来时，盲目开放道口栏木。
    （6）不拿信号旗（灯）、对讲机出场接车。
    （7）栏杆或栏门发生故障停用时，未使用防护绳封闭道口。
    （8）列车接近或通过道口时不按规定关闭栏杆或栏门。
    （9）多线道口当列车尾部刚驶离道口未经了望或未与其他道口员相互对号志便盲目开启栏杆或栏门。
    （10）列车接近或通过道口时，道口员虽然站立在指定位置，但未关闭或晚关闭栏杆或栏门。
    （11）在列车已发出接近报警通知后，将已关闭的栏杆或栏门又重新开启放行车辆。
    （12）道口备品工具不全、失效响墩、火炬、信号灯等设备过期、失效、破损。
    解析： 暂无解析

  • 第22题：

    问答题
    何谓P、NP、NPC问题？

    正确答案： 1.P（Polynomial问题）：也即是多项式复杂程度的问题。
    2.NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
    3.NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。
    解析： 暂无解析

  • 第23题：

    判断题
    P问题是可计算问题，NP问题也是可计算问题
    A

    对

    B

    错


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

相关内容