北京大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽.ppt

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