【答案】《组合优化》(浙江大学)章节期末慕课答案

【答案】《组合优化》(浙江大学)章节期末慕课答案有些题目顺序不一致，下载后按键盘ctrl+F进行搜索组合优化概述第一单元测验1.单选题：考虑下面的批排序问题。若干个工件需在一台批处理机上加工，工件的大小为。大小之和不超过的若干个工件可作为一批同时加工，每批的加工时间均相等。工件的完工时间定义为它所在批的完工时间，目标为极小化工件最大完工时间。与该问题等价的问题是（）。

选项：

A、C台机器的平行机排序问题。

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

C、背包容量为C的背包问题。

D、以上都不对。

答案：【箱容量为C的一维装箱问题。】2.单选题：以下对背包问题最优解的描述，正确的是（）

选项：

A、对于离散形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。

B、对于连续形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。

C、对于离散形式的背包问题，放入背包的物品大小之和为背包容量的解必为最优解。

D、对于连续形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。

答案：【对于连续形式的背包问题，最优解中放入背包的物品大小之和为背包的容量。】3.多选题：考虑单台机排序问题，工件集依次在一机器上加工，机器在同一时间只能加工一个工件，工件的加工时间为，则所有工件的完工时间之和为（）。

选项：

A、

B、

C、

D、

答案：【;】4.多选题：以下字符集，不能作为字母表的是（）。

选项：

A、{0,01,01,1}

B、{0,01,10}

C、{0,1,01,10}

D、{0,00,11}

答案：【{0,01,10};{0,1,01,10};{0,00,11}】5.单选题：设是欧氏平面上三个点，连接这三个点的最小Steiner树长度必小于这三个点形成的赋权完全图的最小生成树长度。（）

选项：

A、正确

B、错误

答案：【错误】第一单元作业1.考虑下面的最大围栏问题（MaximumFenceProblem）。在x轴上有n个固定点，点的横坐标为，。现欲求n个给定正数的一个排列，使得多边形的面积尽可能大，这里的坐标为。（1）试写出F的面积的表达式；（2）试给出求解最大围栏问题的算法。

答案：【】2.对日常生活和学习中遇到的某个组合优化问题进行调研，并建模为描述清楚、目标明确的数学问题。

答案：【本题为开放性问题，所提问题基本符合以下三项要求的，均可视为正确：（1）用数学语言严格、清晰地表述，（2）已抽象为一般问题，而不是一个具体实例，（3）属于组合优化范畴，面向离散对象，有明确的优化目标。】计算复杂性初步第二单元测验1.单选题：若，以下能说明是NP-C问题的是（）。

选项：

A、对任意。

B、存在。

C、对任意。

D、存在。

答案：【对任意。】2.单选题：设为阶方阵。现用以下算法求。算法:Fori=1tondoForj=1tondoFork=1tondo输出c该算法的时间复杂度为（）。

选项：

A、

B、

C、

D、

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

选项：

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

B、若在该问题中，机器数是一个固定常数，该算法是一个指数时间算法。

C、若在该问题中，机器数可能随实例不同而变化，该算法是一个多项式时间算法。

D、若在该问题中，机器数可能随实例不同而变化，该算法是一个指数时间算法。

答案：【若在该问题中，机器数是一个固定常数，该算法是一个多项式时间算法。;若在该问题中，机器数可能随实例不同而变化，该算法是一个指数时间算法。】4.多选题：设有个城市的问题实例,城市之间距离为,以下是该实例规模合理表达式的有（）。

选项：

A、

B、

C、

D、

答案：【;;】5.单选题：若，则。（）

选项：

A、正确

B、错误

答案：【错误】第二单元作业（新）1.现有m家商店与n种图书。若商店销售图书，则记，且其销售价格记为。记为图书的最低销售价格。若顾客在商店购买的图书总价格至少为，则实付金额为在该商店购买图书的总价格减去。现要求选择每种图书购买的商店，使购买种图书的实付总金额最小。（1）试举例说明，顾客选择每种图书价格最低的商店购买该书未必是最优解；（2）证明：即使商店数为2，问题仍是NP-难的；

答案：【】2.证明：以极小化工件最大完工时间为目标的平行机排序问题和一维装箱问题都是NP-难问题。

答案：【】组合优化问题求解方法第三单元作业1.现有两个字母表上的字符串X,Y，通过在字符串中插入空格将它们变为长度相等的字符串，并比较和中位于相同位置的字符。若相同位置两个字符不同，则称为一类误差；若两个字符一个为空格，另一个为非空格，则称为二类误差。若两个字符串所有位置出现的一类误差与二类误差总数分别为和，两个字符串的Needleman-Wunsch误差定义为。例如对AGGGCT和AGGCA两个字符串，若在第二个字符串中插入空格使之成为AGG—CA，Needleman-Wunsch误差为。序列比对问题（sequencealignment）希望给出一种空格插入方案，使两个字符串的Needleman-Wunsch误差最小。试给出求解该问题的动态规划，并估计其时间复杂度。

答案：【】2.现有n个居民小区需提供某项服务，有m处地点可用于开设服务点。在地点i开设服务点所需开设费用为，。设置在地点的服务点为小区j提供服务所需的运营费用为，，。现需选择若干地点开设服务点，并确定每个服务点的服务对象，使每个小区至少有一个服务点为其提供服务，并且总费用最小。试写出该问题的数学规划。

答案：【】第三单元测验1.单选题：某员工的购物车内有件商品,其中商品的价格为。定义为员工使用不超过的资金,仅考虑购买购物车中前件商品时所能购买的商品价格之和的最大值,则满足的递推关系为（）

选项：

A、

B、

C、

D、

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

选项：

A、将物品按价值从大到小的顺序排列。

B、将物品按大小从大到小的顺序排列。

C、将物品按价值密度从大到小的顺序排列。

D、以上都不是。

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

选项：

A、可能存在,使得对任意实例。

B、可能存在,使得对任意实例。

C、用上述方法，不可能证得算法的最坏情况比小于。

D、算法的最坏情况比可能小于。

答案：【可能存在,使得对任意实例。;用上述方法，不可能证得算法的最坏情况比小于。;算法的最坏情况比可能小于。】4.多选题：考虑下面的排序问题,现有两台机器和以及个工件。每个工件需先在上加工再在上加工后才能完工。工件在和上加工所需的时间分别为和一台机器在同一时刻只能加工一个工件。目标为最大工件完工时间尽可能小。该问题最优值的下界有（）。

选项：

A、

B、

C、

D、

答案：【;】5.单选题：设x是取值在中的整变量，y为0-1变量，“y取值为1当且仅当x>0”可用来表示。（）

选项：

A、正确

B、错误

答案：【错误】组合优化新发展第四单元作业1.某项联赛共有n支球队。每支球队可从m个备选城市i，i=1,...,m中选择一个作为自己的主场。城市i的潜在收益为，若有k支球队选择城市i作为其主场，则每支球队的收益为。假设联赛的整体收益为所有球队的收益之和，每支球队均希望本队的收益尽可能大。证明该博弈的混乱代价不超过2。

答案：【】2.某航班经济舱共有N=150个舱位，航空公司为其确定了两种票价，高价位元和低价位元。顾客向航空公司提出其中一种价位的购票意愿，航空公司可以按顾客希望的价位售出机票，也可以拒绝顾客的购票要求。当所有舱位全部售出后，之后顾客的购票请求全被拒绝。假设顾客的购票需求在线到达，航空公司在决定是否售票给当前顾客时不知道以后顾客的购票意愿。现航空公司需制定一种策略（算法），目标为使航空公司的实际票款收益尽可能大。试给出该问题的最好算法。

答案：【】第四单元测验1.单选题：虑背包问题的在线形式。背包容量事先已知，物品一个个相继出现，物品出现后方知其价值和大小。具体地，第j个物品在第j-1个物品是否放入背包已被确定后才出现，且此前已作出的前j-1个物品是否被放入背包的决定不可更改。该在线问题的下界为（）。

选项：

A、2

B、3

C、4

D、

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

选项：

A、

B、

C、

D、

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

选项：

A、四名同学参加活动。

B、任一名同学参加活动或任一名同学不参加活动。

C、两名同学参加活动。

D、四名同学均不参加活动。

答案：【两名同学参加活动。;四名同学均不参加活动。】4.多选题：设是一个在线问题，以下说法准确的有（BC）。

选项：

A、若存在的竞争比为的在线算法,则问题的下界至少为。

B、若存在的竞争比为的在线算法,则问题的下界至多为。

C、若是的一个下界,则可能存在竞争比大于的在线算法。

D、若是的一个下界,则可能存在竞争比小于的在线算法。

答案：【若存在的竞争比为的在线算法,则问题的下界至多为。;若是的一个下界,则可能存在竞争比大于的在线算法。】5.单选题：若博弈的某个策略组合不是Nash均衡，则每位参与者均可通过单方面改变自身的策略使其费用减少。（）

选项：

A、正确

B、错误

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

选项：

A、两人合坐、两人站立；

B、两人站立、两人站立；

C、两人合坐、纯策略Nash均衡不存在；

D、两人站立、纯策略Nash均衡不存在。

答案：【两人合坐、两人站立；】2.单选题：设为一赋权图，边e的权为，是的最小生成树，P是从到的最短路，考虑图，其中边e的权为，则（）

选项：

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

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

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

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

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

选项：

A、按持续时间从小到大的顺序排列。

B、按开始时间从小到大的顺序排列。

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

D、以上都不对。

答案：【按结束时间从小到大的顺序排列】4.单选题：考虑单台机排序问题，工件集中工件需在一台机器上加工，每台机器在同一时间只能加工一个工件，工件的权为，加工时间为，完工时间为，。可使最小的工件加工顺序是（）

选项：

A、将工件按加工时间从小到大顺序排列

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

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

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

答案：【将工件按权从大到小顺序排列】5.单选题：若，以下关于确定性图灵机和非确定性图灵机的论述，错误的有（）

选项：

A、确定性图灵机能求解的问题，非确定性图灵机也能求解。

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

C、非确定性图灵机能求解的问题，确定性图灵机也能求解。

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

答案：【非确定性图灵机多项式时间内能求解的问题，确定性图灵机多项式时间内也能求解。】6.单选题：设均为0-1变量，表示“仅当y的取值为1时，中任一变量可取值1的约束条件”是（）

选项：

A、

B、

C、

D、

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

选项：

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

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

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

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

答案：【以展厅为图的顶点，门为图的边。寻找从某个顶点出发，经过所有顶点恰好一次，最后回到出发顶点的路线。】8.单选题：以下叙述结论和逻辑均正确的是（）

选项：

A、最小生成树问题是P问题，因为图的生成树的数量是顶点数和边数的多项式函数。

B、最小生成树问题是P问题，因为图的生成树的所有可能长度种类不超过边数。

C、TSP问题是NP-难问题，因为所有环游的数量是城市数量的指数函数。

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

答案：【穷举不能在多项式时间内解决TSP问题，因为所有环游的数量是城市数量的指数函数。】9.单选题：现有一双人博弈，甲有m个可选策略，乙有n个可选策略。若策略组合是Nash均衡，以下说法正确的是（）

选项：

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

B、不论乙选择何种策略，甲选择策略收益最大；

C、甲选择策略，乙选择策略时双方收益之和最大；

D、不存在局势，使得甲选择策略，乙选择策略时各自的收益分别比甲选择策略，乙选择策略时的收益大。

答案：【乙选择策略时，甲选择策略收益最大；】10.单选题：图中边最多的匹配称为最大基数匹配，非负权图中总权和最大的匹配称为最大权匹配。以下说法准确的是（）

选项：

A、完美匹配必为最大权匹配，最大权匹配必为最大基数匹配。

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

C、最大基数匹配必为完美匹配，最大权匹配必为最大基数匹配。

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

答案：【完美匹配必为最大基数匹配，最大权匹配未必是最大基数匹配。】11.单选题：设是极小化目标在线问题，A是它的一个在线算法，对实例I，。以下说法准确的是

选项：

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

B、算法A的竞争比至多为r。

C、问题的下界至少为r。

D、问题的下界至多为r。

答案：【算法A的竞争比至少为r。】12.单选题：给定正整数序列，下面的算法可判断中是否至少有两个数相同：算法：FORi=1tonFORj=i+1tonIF=THEN输出“是”输出“否”该算法的时间复杂度为（）

选项：

A、O(1)

B、O(logn)

C、O(n)

D、

答案：【】13.单选题：若，以下描述准确

选项：

A、存在常数c，对任意n。

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

C、对任意,存在数。

D、存在正整数，对任意，存在数。

答案：【存在常数c和正整数，对任意。】14.单选题：设A是一个极大化目标优化问题的近似算法，最坏情况比为4.设对实例I，算法值为，则最优值（）

选项：

A、

B、

C、

D、

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

选项：

A、求，使得最大；

B、求，使得;

C、求，使得；

D、求满足的，使得最大。

答案：【求满足的，使得最大。】16.多选题：若问题A可多项式时间归约到问题B，则以下叙述错误的是（）

选项：

A、若A多项式时间可解，则B也多项式时间可解。

B、若B是NP-难问题，则A也是NP-难问题

C、B必能多项式时间归约到A

D、B不能多项式时间归约到A

答案：【若A多项式时间可解，则B也多项式时间可解。;若B是NP-难问题，则A也是NP-难问题;B必能多项式时间归约到A;B不能多项式时间归约到A】17.多选题：若P=NP，以下叙述正确的有（）

选项：

A、P=NP-C

B、NP=NP-C

C、NP-C=NP-hard

D、NP=NP-hard

答案：【P=NP-C;NP=NP-C】18.多选题：以下每个选项中的两个函数是多项式相关的有（）

选项：

A、与

B、loglogn与logn

C、nlogn与n

D、与

答案：【与;nlogn与n】19.多选题：以下每对问题，由一个问题的最优解可在多项式时间内得到另一个问题的最优解的有（）

选项：

A、图的最短路与最长路

B、图的最小生成树与最大生成树

C、2n个顶点的完全图的最小权完美匹配与最大权完美匹配

D、在放入物品的大小之和不超过背包容量的前提下使放入背包物品价值之和尽可能大的极大化背包问题与在放入物品的大小之和不小于背包容量的前提下使放入背包物品价值之和尽可能小的极小化背包问题

答案：【图的最小生成树与最大生成树;2n个顶点的完全图的最小权完美匹配与最大权完美匹配;在放入物品的大小之和不超过背包容量的前提下使放入背包物品价值之和尽可能大的极大化背包问题与在放入物品的大小之和不小于背包容量的前提下使放入背包物品价值之和尽可能小的极小化背包问题】20.多选题：假设，以下对含个物品的背包问题实例，叙述正确的有（）

选项：

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

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

C、若所有物品大小为至少为的整数，实例必不是多项式时间可解的。

D、若所有物品价值为至少为的整数，实例必不是多项式时间可解的。

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