组合优化-浙江大学中国大学mooc课后章节答案期末考试题库2023年

组合优化_浙江大学中国大学mooc课后章节答案期末考试题库2023年以下每个选项中的两个函数是多项式相关的有（）

参考答案:

与_nlogn与n

若P=NP，以下叙述正确的有（）

参考答案:

P=NP-C_NP=NP-C

若问题A可多项式时间归约到问题B，则以下叙述错误的是（）

参考答案:

若A多项式时间可解，则B也多项式时间可解。_若B是NP-难问题，则A也是NP-难问题_B必能多项式时间归约到A_B不能多项式时间归约到A

若，设A是求解NP-完全问题的最优算法，则A求解的任一实例都需要指数时间。

参考答案:

错误

以下每对问题，由一个问题的最优解可在多项式时间内得到另一个问题的最优解的有（）

参考答案:

图的最小生成树与最大生成树_2n个顶点的完全图的最小权完美匹配与最大权完美匹配_在放入物品的大小之和不超过背包容量的前提下使放入背包物品价值之和尽可能大的极大化背包问题与在放入物品的大小之和不小于背包容量的前提下使放入背包物品价值之和尽可能小的极小化背包问题

设是三个Boolean变量【图片】的Boolean表达式，【图片】，则可使F为真的变量取值种类有（）

参考答案:

4

一维装箱问题的一个算法称为NextFit，它将物品按原始顺序依次装箱。在任一时刻，仅有一个箱子开启可以放入物品。若有物品无法放入该箱子中，则该箱子此后不再放入任何物品。同时开启一个新的箱子并放入物品。NextFit算法的最坏情况比为（）

参考答案:

2

若，TSP问题存在最坏情况比为常数的多项式时间近似算法。

参考答案:

正确

某电视台办有价格竞猜节目。某物品的价格为一正整数，竞猜人逐次报价，直至某次所报价格不小于该物品的价格为止。竞猜人的损失为其历次所报的价格（包括最后一次不小于物品价格的报价在内）之和。要求给出报价方案，使竞猜人的损失尽可能小。若第i次报价为【图片】，该方案的竞争比为（）

参考答案:

4

某一省的每个城市都与该省的其他三个城市之间有直达高铁，该省的任意两个城市之间均可通过一次换乘到达，该省的城市数至多为（）

参考答案:

10

Hamilton圈问题和TSP问题的判定形式都是NP-完全问题，因此既存在从前者到后者的多项式时间归约，也存在从后者到前者的多项式时间归约。

参考答案:

正确

若一在线问题算法A的竞争比大于另一算法B的竞争比，则A不可能是该问题的最好算法。

参考答案:

正确

考虑单台机排序问题，工件集【图片】中工件需在一台机器上加工，每台机器在同一时间只能加工一个工件，工件【图片】的权为【图片】，加工时间为【图片】，完工时间为【图片】，【图片】。可使【图片】最小的工件加工顺序是（）

参考答案:

将工件按权从大到小顺序排列

设一平行机排序问题含个工件和台机器，所有工件加工时间均相同，该实例规模可表示为。

参考答案:

错误

一博物馆分为若干个展厅，部分展厅之间有门相连。一管理人员希望从某个展厅出发，巡察每个展厅恰好一次，最后回到他出发的展厅。运用图论建模和求解该问题，正确的是（）

参考答案:

以展厅为图的顶点，门为图的边。寻找从某个顶点出发，经过所有顶点恰好一次，最后回到出发顶点的路线。

公司给员工发放一张面值为的福利卡，某员工的购物车内有件商品，其中商品的价格为。福利卡只能一次性使用，并且不能和现金混合支付。员工能享受最多福利所对应的数学问题是（）

参考答案:

求满足的，使得最大。

若【图片】，以下描述准确

参考答案:

存在常数c和正整数，对任意。

设【图片】是极小化目标在线问题，A是它的一个在线算法，对实例I，【图片】。以下说法准确的是

参考答案:

算法A的竞争比至少为r。

图中边最多的匹配称为最大基数匹配，非负权图中总权和最大的匹配称为最大权匹配。以下说法准确的是（）

参考答案:

完美匹配必为最大基数匹配，最大权匹配未必是最大基数匹配。

现有一双人博弈，甲有m个可选策略【图片】，乙有n个可选策略【图片】。若策略组合【图片】是Nash均衡，以下说法正确的是（）

参考答案:

乙选择策略时，甲选择策略收益最大；

以下叙述结论和逻辑均正确的是（）

参考答案:

穷举不能在多项式时间内解决TSP问题，因为所有环游的数量是城市数量的指数函数。

假设【图片】，以下对含个物品的背包问题实例，叙述正确的有（）

参考答案:

若所有物品大小为不超过的整数，实例是多项式时间可解的。_若所有物品价值为不超过的整数，实例是多项式时间可解的。

若【图片】，以下关于确定性图灵机和非确定性图灵机的论述，错误的有（）

参考答案:

非确定性图灵机多项式时间内能求解的问题，确定性图灵机多项式时间内也能求解。

某场馆收到n项借用申请，第i项申请涉及的活动所需时段为【图片】，其中【图片】，【图片】，【图片】称为开始时间，【图片】称为结束时间，持续时间为【图片】。场馆在同一时刻只能进行一项活动，一项活动开始后必须连续进行直至结束。现希望选择接受部分申请，使得场馆能开展的活动数量尽可能多。场馆管理员试图用贪婪算法求解该问题。将所有申请按某种顺序排列，依次考虑各项申请。若当前申请涉及的活动所需时段未被已接受的申请涉及的活动占用，则接受该申请，否则拒绝该申请。能使该贪婪算法成为该问题的最优算法的申请排列顺序是（）

参考答案:

按结束时间从小到大的顺序排列

设【图片】为一赋权图，边e的权为【图片】，是的最小生成树，P是从【图片】到【图片】的最短路，考虑图【图片】，其中边e的权为【图片】，则（）

参考答案:

T仍是G'的最小生成树，P未必是G'中从s到t的最短路。

89路公交车上设有宽体单人座，可同时坐下两人但空间较普通双人座狭窄。乘车舒适度以单人就坐最佳，与人合坐次之，站立最差。现有两人上车后发现车厢中只余这一个座位。若每人均为自身考虑，自身舒适度愈大愈好。若每人均为对方考虑，对方舒适度愈大愈好，且当对方站立时，宁愿陪同站立而不独坐。对上述两种情形，博弈的纯策略Nash均衡分别为（）

参考答案:

两人合坐、两人站立；

某购书网站推出“满100送礼券”活动。凡单张订单购书全额达到或超过100元可获指定面额礼券一张。现欲购买一批图书，计划分拆若干张订单以使获得的礼券张数最多。若按任一顺序选择购买图书，当当前订单累计金额达到或超过100元后，立即新启一张订单。该方案的最坏情况比紧界为（）

参考答案:

2

设有【图片】个城市的【图片】问题实例,城市之间距离为【图片】,以下是该实例规模合理表达式的有（）。

参考答案:

__

若【图片】，以下能说明【图片】是NP-C问题的是（）。

参考答案:

对任意。

若【图片】，则【图片】。（）

参考答案:

错误

考虑单台机排序问题，工件集【图片】依次在一机器上加工，机器在同一时间只能加工一个工件，工件【图片】的加工时间为【图片】，则所有工件的完工时间之和为（）。

参考答案:

_

一寝室住有四名同学。一日学园举行某项活动，有至少两名同学参与该项活动的寝室将获得奖励。每位同学有参加或不参加两种选择。他们都希望寝室能获得奖励，同时倾向于自己不参加活动。当然在自己参加活动而寝室获得奖励与自己不参加活动而寝室未获奖励之间更偏好前种情况。该博弈的Nash均衡有（）。

参考答案:

两名同学参加活动。_四名同学均不参加活动。

设【图片】是一个在线问题，以下说法准确的有（BC）。

参考答案:

若存在的竞争比为的在线算法,则问题的下界至多为。_若是的一个下界,则可能存在竞争比大于的在线算法。

考虑下面的批排序问题。若干个工件需在一台批处理机上加工，工件【图片】的大小为【图片】。大小之和不超过【图片】的若干个工件可作为一批同时加工，每批的加工时间均相等。工件的完工时间定义为它所在批的完工时间，目标为极小化工件最大完工时间。与该问题等价的问题是（）。

参考答案:

箱容量为C的一维装箱问题。

设算法【图片】为一极小化目标优化问题的近似算法,现用比较算法【图片】给出的实例【图片】的可行解目标值【图片】和【图片】的方法证明算法【图片】的最坏情况比，其中【图片】是实例【图片】的最优值的下界,满足【图片】对任意实例【图片】成立。以下说法正确的有（）。

参考答案:

可能存在,使得对任意实例。_用上述方法，不可能证得算法的最坏情况比小于。_算法的最坏情况比可能小于。

考虑下面的排序问题,现有两台机器【图片】和【图片】以及【图片】个工件【图片】。每个工件需先在【图片】上加工再在【图片】上加工后才能完工。工件【图片】在【图片】和【图片】上加工所需的时间分别为【图片】和【图片】一台机器在同一时刻只能加工一个工件。目标为最大工件完工时间尽可能小。该问题最优值的下界有（）。

参考答案:

_

考虑背包问题的下述算法，首先将物品按某种顺序排列，随后逐个放入背包，直至有物品不能放入背包时，算法终止。以下物品排列顺序，可使该算法的最坏情况比为有限常数的是（）。

参考答案:

以上都不是。

设x是取值在【图片】中的整变量，y为0-1变量，“y取值为1当且仅当x>0”可用【图片】来表示。（）

参考答案:

错误

设【图片】是欧氏平面上三个点，连接这三个点的最小Steiner树长度必小于这三个点形成的赋权完全图的最小生成树长度。（）

参考答案:

错误

设一博恋的社会费用为极小化目标,记【图片】分别为实例【图片】的社会费用最大的Nash均衡的社会费用，社会费用最小的Nash均衡的社会费用和最优社会费用。以下说法准确的有（BCD）。

参考答案:

__

设一平行机排序问题算法的时间复杂度为【图片】，其中m,n分别为机器数和工件数，【图片】为一与实例无关的常数。以下说法准确的有（）。

参考答案:

若在该问题中，机器数是一个固定常数，该算法是一个多项式时间算法