搜索
第1页共6页一、PleaseanswerTorFforeachofthefollowingstatementstoindicatewhetherthestatementistrueorfalse1.Theknapsackproblemcanbesolvedinpolynomialtimebyusingdynamicprogramming.(F)2.SomeproblemsinNPcanbesolvedinpolynomialtime.(T)3.ToshowaproblemisNP-hard,wecanreduceittoawell-knownNP-Completeproblem.(F)4.Inanundirectedgraph,thevalueofthemaximumflowbetweentwoverticesisequivalenttothevalueoftheminimumcutbetweenthem.(T)5.log2(())nnOn.(F)二、Arrangethefollowingfunctionsinascendingasymptoticorderofgrowthrate:log1001()5lognfnnnn，logloglog2()2nnfn，3.53()fnn，24()2nfnn，5()(2log)nfnn.参考答案：f2，f3，f1，f4，f5三、Pleaseanswerthefollowingquestions:(a)Whatarethemainstepsofdesigningadynamicprogrammingalgorithm?参考答案：1.定义子问题；2根据子问题建立递归关系式；3用自底而上的方式求解（建立储存表）。(b)WhatarethemainstepsofprovingtheNP-Completenessofaproblem?参考答案：1.证明该问题属于NP；2.选一个已知的NPC问题B；3.将问题B归约到该问题上。四、TheTravelingsalesmanproblem(TSP)isdefinedasfollows:Givenagraph,thetaskistofindashortestpossibleroutethatvisitseachvertexexactlyonceandreturnstotheoriginvertex.第2页共6页Fig.1ForthegraphshowninFig.1,(a)findasolutiontoTSP((therouteisstartingfromAandbacktoA);(b)findalongestdirectedcyclethatcontainsvertexA.参考答案：|（a）A-D-C-B-A35+12+30+20=97（b）A-C-B-D-A42+30+34+35=141五、DesignanalgorithmforthefollowingIntervalSchedulingproblem:Therearenjobseachofwhichhasastartingtimesandafinishingtimef.Twojobsarecompatibleiftheydon’toverlap.Thegoaloftheproblemistofindamaximumsetofmutuallycompatiblejobs.参考答案及评分标准：将所有工作（Interval）按其完成时间的先后进行排序；在排好序的序列中用弹性法则，以此选取最小完成时间且和前面已选工作不冲突的工作。六、Findaminimums-tcutinthefollowinggraph(thenumberbesidetheedgeisthecapacityoftheedge).Youarerequiredtogivethecomputationstepsandshowthesizeofthecut.ABCD203534423012第3页共6页参考答案：35.有两个解：{S，4，3，8}和{S，1，2，3，4，5，6，7，8，9}评分标准：说明计算该图从s到t的最大流给出第一个增广连后面任意两个增广连（最后答案35和这个cut七、Provethatifwecancheckifagraphhasapathoflengthkinpolynomialtimethenwecanalsofindapathoflengthkinpolynomialtime.参考答案及评分标准：依次从图中删除一条边，然后检查是否还存在长度为k的路径，如果存在则直接删除，如果不存在则保留该边。如此下去，最后图只剩下k条边。以上思想正确给全分。八、AHamiltoniancycleinagraphisacyclethatcontainseachvertex.TheHamiltonianCycleproblemistofindaHamiltoniancycleinagraph.TheConstrainedHamiltonianCycleproblemistofindaHamiltoniancyclepassingthroughsomegivenedgesinthegraph.GiveapolynomialreductionfromtheConstrainedHamiltonianCycleproblemtotheHamiltonianCycleproblem.参考答案及评分标准：在每个给出的要求通过的边上添加一个顶点（度数945831S1T11111115152030530205178710105第4页共6页为2），这样Hamiltoncycle就必须通过这些边了。以上思想正确给全分。九、Answerthefollowingquestions.GivenagraphGwithnonnegativevertexweight,theWeightedVertexCoverproblemistofindaminimumvertexset(theweightofverticesinthesetisminimized)suchthateachedgeinthegraphhasatleastoneendpointintheset.(a)PleasegiveanintegerprogrammingformulationoftheWeightedVertexCoverproblem.(b)Givea2-approximationalgorithmbasedonlinearprogramming.(c)Provethatyouralgorithmguaranteestheapproximationratio2.参考答案及评分标准：（a）min..1foreachedge0or1foreachvertexiijijiixstxxxxxx（b）将以上整数规划改为线性规划：将约束条件0or1foreachvertexiixx改为01foreachvertexiixx，并且将解中x_i值大于等于0.5的选入点覆盖中。（c）证明在教材在有。大体思路对可以给全分。十、Therearemmachinesandn=2m+1jobs,wheretwoofjobshaslengthof(m+1,m+2,m+3,…,2m)respectively,andonejobhaslengthofm.Eachjobmustbeprocessedcontiguouslyonamachineandeachmachinecanprocessatmostonejobatatime.Youareaskedtoassignjobstomachinestominimizethemakespan(thelongestprocessingtimeonanymachine).(a)Giveanapproximationsolutionbyusingthelongestprocessingtimefirst第5页共6页(LPT)algorithm.(givethemainideaofLPTandthefinalsolution)(b)Trytofindanoptimalsolutionforthisproblem.参考答案及评分标准：（a）LPT算法基本思想是将任务按照处理时间长度降序排列，总是将处理时间最长的任务分配到目前负载最低的机器上。（b）Theoptimalsolutionoftheminimizingthemakespanis3m+2.因为所有任务长度之和是3m^2+2m,共有m个机器，每个机器都分配相同长度的任务（3m^2+2m）/m=3m+2.十一、Givenagraph,theVertexCoverproblemistofindaminimumsubsetofverticessuchthateachedgehasatleastoneendpointinit;theIndependentSetproblemistofindamaximumsubsetofverticessuchthatthereisnoedgebetweenanytwoverticesinit,andtheCliqueproblemistofindamaximumsubsetofverticessuchthatthereisanedgebetweenanytwoverticesinit.PleasegiveapolynomialreductionfromtheVertexCoverproblemtotheIndependentSetproblemandapolynomialreductionfromtheIndependentSetproblemtotheCliqueproblem.参考答案及评分标准：VC到IS的归约：图中除去vertexcover中的点剩下的点就是一个independentset。IS到Clique的归约：让G’为G的补图，则G中的independentset就是G’中的clique。十二、Usedynamicprogrammingtosolvethefollowingknapsackproblem:Therearendifferenttypesofitemsandeachtypehastwopieces(totallywehave2nitems).Itemihasweightof0iwkilogramsandvalueof0ivdollars.YouhaveaknapsackthatcancontainatmostWkilograms.Howtofillyourknapsackwiththeitemstomaximumthevalue?(a)Pleasedefineyoursubproblem;第6页共6页(b)Givetherecurrencerelationbasedonyoursubproblems;(c)SolvethefollowinginstanceshowedinTable1byusingthebottom-upmethod.Youarerequiredtogivethecomputationsteps(thetableusedtostorethesolutionstothesubporblems).ItemsWeightValue112223348432559Table1:Thereare5items,eachofwhichhastwopieces.Thecapacityoftheknapsackis10kilograms.参考答案及评分标准：（a）定义OPT（i，w）为只能选择前i种物品且背包容量为w的最优解；（b）建立递归关系式：i0ifi0(,)(1,)ifwwmax(1,),(1,),2(1,2)otherwiseiiiiOPTiwOPTiwOPTiwvOPTiwwvOPTiww