北京大學ACM國際大學生程序設計競賽.ppt

問題求解與程序設計第七講搜索,李文新2004.22004.6,內容提要,搜索討論1011stick討論1054thetroublesomefrog參考王知昆的冬令營報告作業(yè),搜索的一般概念,在解空間中嘗試所有可能，找出滿足條件的取值回顧填數游戲：1-9填在3*3的表格中，使得行、列、對角線的和均為15。方程組搜索逐一嘗試+剪枝,題目討論,1011stick,題目討論,TheTroublesomeFrogIOI2002day1task1,問題,稻田,問題,青蛙從外面跳入稻田，踩過一些禾苗，后，跳出稻田。,問題,蛙路：一個方向，等間距，大于等于3個點不同蛙路：可以方向不同，間距不同,問題,許多青蛙跳過稻田，形成多條蛙路，不同蛙路可以踩過同一作物。,問題,青蛙每天早上踩壞稻田，早上人們發(fā)現稻田有若干株作物被踩壞，但不知多少青蛙來過。也有不在蛙路上的被踩壞的作物。,問題,問，給定一塊被踩壞的稻田，求可能的最長的蛙路上被踩壞的作物的數目。,輸入,第一行整數R和C，稻田的行數和列數第二行整數N，表示被踩壞的作物總數。后續(xù)N行，每行兩個整數i,j為被踩壞的作物的行和列的位置:1<=i<=R,1，1<=j<=C。每個被踩壞的作物只出現一次。,輸出,單個整數-表示最長可能蛙路上踩壞的作物數目,樣例,Figure-4,問題的解,這道題目也就是說，在給出的n個點中找出一些點的序列來，使得每一個點相對于上一個點的坐標都是一個相同的向量，且第一個點減去這個向量和最后一個點加上這個向量后均落在方格的外面。,問題的解,我們先對這些點按照坐標排序。然后依次循環(huán)出要求的序列中的第一個和第二個點，這樣我們就知道后一個點相對于前一個點的坐標是多少了。然后我們依次用第二個點加上這個坐標的出第三個點，第三個點加上這個坐標得出第四個點等等。當然，我們還需要判斷一下這求出來的第三個、第四個點是否在給定的點內。,問題的解,由于每個點的上一個點/下一個點最多只能有n種選擇，故一個點最多屬于n條不同的蛙路。這樣，對于某個確定的點來說，它的所有可能的下一個需要判斷的點至多有n個。這樣因為判斷一個點在不在給定的點內只需要O(1)的復雜度，所以我們只需要O(n2)的時間就可以得出問題的解答。由于這個算法需要一個r*c的表來保存點在方格中的存在狀態(tài)，故空間復雜度為O(n2)。,問題的解,需要注意的是，蛙路中的點數少于3個的時候是不考慮的。所以這個時候的蛙路中的點數應該按照0來算。,實現細節(jié),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,參考資料,王知昆的冬令營報告,作業(yè),10111054選做,