资源描述
问题求解与程序设计第七讲搜索,李文新2004.22004.6,内容提要,搜索讨论1011stick讨论1054thetroublesomefrog参考王知昆的冬令营报告作业,搜索的一般概念,在解空间中尝试所有可能，找出满足条件的取值回顾填数游戏：1-9填在3*3的表格中，使得行、列、对角线的和均为15。方程组搜索逐一尝试+剪枝,题目讨论,1011stick,题目讨论,TheTroublesomeFrogIOI2002day1task1,问题,稻田,问题,青蛙从外面跳入稻田，踩过一些禾苗，后，跳出稻田。,问题,蛙路：一个方向，等间距，大于等于3个点不同蛙路：可以方向不同，间距不同,问题,许多青蛙跳过稻田，形成多条蛙路，不同蛙路可以踩过同一作物。,问题,青蛙每天早上踩坏稻田，早上人们发现稻田有若干株作物被踩坏，但不知多少青蛙来过。也有不在蛙路上的被踩坏的作物。,问题,问，给定一块被踩坏的稻田，求可能的最长的蛙路上被踩坏的作物的数目。,输入,第一行整数R和C，稻田的行数和列数第二行整数N，表示被踩坏的作物总数。后续N行，每行两个整数i,j为被踩坏的作物的行和列的位置:1=i=R,1，1=j=C。每个被踩坏的作物只出现一次。,输出,单个整数-表示最长可能蛙路上踩坏的作物数目,样例,Figure-4,问题的解,这道题目也就是说，在给出的n个点中找出一些点的序列来，使得每一个点相对于上一个点的坐标都是一个相同的向量，且第一个点减去这个向量和最后一个点加上这个向量后均落在方格的外面。,问题的解,我们先对这些点按照坐标排序。然后依次循环出要求的序列中的第一个和第二个点，这样我们就知道后一个点相对于前一个点的坐标是多少了。然后我们依次用第二个点加上这个坐标的出第三个点，第三个点加上这个坐标得出第四个点等等。当然，我们还需要判断一下这求出来的第三个、第四个点是否在给定的点内。,问题的解,由于每个点的上一个点/下一个点最多只能有n种选择，故一个点最多属于n条不同的蛙路。这样，对于某个确定的点来说，它的所有可能的下一个需要判断的点至多有n个。这样因为判断一个点在不在给定的点内只需要O(1)的复杂度，所以我们只需要O(n2)的时间就可以得出问题的解答。由于这个算法需要一个r*c的表来保存点在方格中的存在状态，故空间复杂度为O(n2)。,问题的解,需要注意的是，蛙路中的点数少于3个的时候是不考虑的。所以这个时候的蛙路中的点数应该按照0来算。,实现细节,Frogvsfrog平面上点的表示Frog20有冗余代码Frog21去掉冗余Frog22compare判断Frog23改变表达式写法Frog24增加剪枝Frog25不太好的剪枝顺序Frog26较好的剪枝顺序,测试数据,No.N,(R*C)DescriptionSolution118,(6*7)Sampledatainthetaskdescription4210,(10*10)Manuallydesigned5325,(50*50)Manuallydesigned13450,(10*10)SeveralLines+randompoints105100,(20*20)modifiedrandompointset106300,(30*30)modifiedrandompointset157500,(55*55)SeveralLines+randompoints288500,(100*100)Specialcasefornosolution091000,(100*100)SeveralLines+randompoints34101000,(1000*1000)SeveralLines+randompoints250112000,(50*50)Random(uniform)points25122000,(100*200)SeveralLines+randompoints33132000,(1000*2000)SeveralLines+randompoints333,测试数据,143000,(60*60)Uniformlyrandompoints31153000,(500*500)Xshapesandrandompoints500163000,(5000*1)Horizontalline20173000,(5*1000)SeveralLines+randompoints17184000,(100*100)Randompoints(uniformly)34194000,(200*20)Verydensepointsset200204000,(1000*1000)SeveralLines+randompoints500214000,(5000*5000)SeveralLines+randompoints311225000,(100*100)Chessboardstyle100235000,(1000*1000)SeveralLines+randompoints334245000,(3000*3000)Irregularlinearpoints1000255000,(5000*5000)Modifiedrandompoints72,参考资料,王知昆的冬令营报告,作业,10111054选做,
展开阅读全文