卜东波老师算法分析与设计作业答案2015版

《卜东波老师算法分析与设计作业答案2015版》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1/51HintsofAssignment1-7AlgorithmDesignandAnalysisDatumor1,20151niujinghao@outlook.com2/51Assignment13/514/515/516/517/51下面是解法2：8/519/51注：满足O(n)的原因是T(n)=1*T(n/2)+O(n)，后边的f(n)=O(n)是每步求最小值算法的复杂度。10/51注：上边这个做法有点问题仅供参考，实际上是katalan数通项从n-2开始11/5112/51Assignment213/5114/5115/5116/51

2、17/5118/5119/5120/51Assignment321/51注：上边最后一个应该是大于号，最终是O(n^2logn)复杂度，如果只开始排序一次，每步不另外排序，则可得到O(n^2)的复杂度。22/51注：上边那个(a)有点小问题，其实就是固定首尾相接的p1p2比较可变的p_i+f_i与p_j的长度关系，读者自己验证一下吧。23/5124/5125/51Assignment426/5127/5128/51P.S.第二问TA也不会啊~~历史遗留问题*_*29/5130/51注：这里之所以约束3中为3，是p和q同时满足时，<=1,可以有(1

3、,0)(0,0)(0,1)出现，因为不排除某个w或m与四个人之外有极强的联系，这样与之建立关系之后，相互喜欢的w和m剩下的那个可以与单恋的异性建立稳定关系。31/5132/51Assignment533/5134/5135/5136/51其实还有一个更简单的办法：第一层全部的狗，第二层全部的狗舍，前后加上s和t，s到狗c=1，狗到狗舍c=1，cost=到对应狗舍的距离，狗舍到t，c=1。求最小cost流。因为是最小割，所以一定有边的权重更大，C=1化权重为边数37/51补充方法2：另一种理解的思路，只是部分摘选，详情可自己Google38/513

4、9/5140/51Assignment641/51注：最下边的y_n1,y_n2可以理解为填充完xi和–xi之后添补的变量，保证3的存在有意义。42/511，冗余变量、冗余子句补全成方针2，每一行一个变量，对、错或者不用3，每一列一个子句，至少用一个变量43/5144/51注：s1–sn每个代表一个变量，sn+1–sn+m每个代表一个子句。1，两个序列，一个由依次x_i设定为1所导致的正确子句在前，0在后+间断排列而成，另一个由x_i设定为0所导致的正确句子在前，1在后+间断排列而成。45/51一个正确的指派会分别从A1和A2中分别选择对应向量，

5、满足总子句数量的那个正是最长的子集链。注：这个摘录存在不全的问题，不太容易理解，Google上有LCS问题3SAT处理的论文，可以具体参考。46/51Assignment7注：另一种解释，考虑每两个相邻的箱子，相加的和一定大于两个1/2的和，否则可以合并，则有k/2*(1/2+1/2)<(∑???)/1=OPT所以有k<2OPTi=147/5148/51注：核心思想是对于T中点形成的完全树中任意两个点，若用T之外的G之中的点用两条边分别相连首尾，有两边之和大于第三边（两倍情况下可对所有树中的边进行不等式讨论）49/5150/51----之后利用确

6、定算法可以求出具体的7/8证明。----此题可以有一个简单的两倍近似算法：每次随机选择一个变量，如xi，将得到正确的子句和错误的子句选出来，选择其中更多的一部分（该部分对应的那个变量的0/1取值）。对于剩下的子句，再选择另一个变量，重复该操作，直到全部的子句都被这样选择完。我们得到了一组赋值和一组对应的子句，这个子句集的大小就是我们输出的最大满足数。证明2倍：对于OPT有一个明显的上界，就是全部的子句数量。而我们的近似算法有一个下界，就是1/2的子句数量：因为每次的划分都取了子集中更大的部分，同时加起来是原始子句集，及总子句数量。所以全部加起来也

7、一定大于1/2总子句数量。51/51ACKNOWLEDGMENTAlgorithmDesignandAnalysisissuchagreatclasstaughtbyProf.DongboBu2thatIwouldvoteforitofoneofthebestclassesinUCASwithouthesitating.Thiseditionofhintislackofrevising,whichisjustoneroughcollectionofsolvingideas.Idonotguaranteeanysolutionofproblemis

8、absolutelycorrect.Theauthorofthishintthanksforpredecessorsandpeerguy