北京大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽7課件

問題求解與程序設(shè)計(jì)

第七講

搜索2004.2–2004.6內(nèi)容提要搜索討論1011stick討論1054thetroublesomefrog參考王知昆的冬令營報(bào)告作業(yè)搜索的一般概念在解空間中嘗試所有可能，找出滿足條件的取值回顧填數(shù)游戲：1-9填在3*3的表格中，使得行、列、對(duì)角線的和均為15。方程組搜索–逐一嘗試+剪枝題目討論TheTroublesomeFrogIOI2002day1task1問題稻田問題青蛙從外面跳入稻田，踩過一些禾苗，后，跳出稻田。問題許多青蛙跳過稻田，形成多條蛙路，不同蛙路可以踩過同一作物。問題青蛙每天早上踩壞稻田，早上人們發(fā)現(xiàn)稻田有若干株作物被踩壞，但不知多少青蛙來過。也有不在蛙路上的被踩壞的作物。問題問，給定一塊被踩壞的稻田，求可能的最長的蛙路上被踩壞的作物的數(shù)目。輸出單個(gè)整數(shù) --表示最長可能蛙路上踩壞的作物數(shù)目樣例Figure-4問題的解這道題目也就是說，在給出的n個(gè)點(diǎn)中找出一些點(diǎn)的序列來，使得每一個(gè)點(diǎn)相對(duì)于上一個(gè)點(diǎn)的坐標(biāo)都是一個(gè)相同的向量，且第一個(gè)點(diǎn)減去這個(gè)向量和最后一個(gè)點(diǎn)加上這個(gè)向量后均落在方格的外面。

問題的解由于每個(gè)點(diǎn)的上一個(gè)點(diǎn)/下一個(gè)點(diǎn)最多只能有n種選擇，故一個(gè)點(diǎn)最多屬于n條不同的蛙路。這樣，對(duì)于某個(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)的表示Frog2–0 有冗余代碼Frog2–1 去掉冗余Frog2–2 compare判斷Frog2–3 改變表達(dá)式寫法Frog2–4 增加剪枝Frog2–5 不太好的剪枝順序Frog2–6 較好的剪枝順序測(cè)試數(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)Irregularlinearpoints10002550