信息學(xué)集訓(xùn)隊(duì)作業(yè)center

1、IOI2003中國國家集訓(xùn)隊(duì)難活有一個大廳最近要召開一個很重要IOI2003中國國家集訓(xùn)隊(duì)難活有一個大廳最近要召開一個很重要的會議，因此會議的組織者請了一個清潔公司來給大廳機(jī)來完成清潔工作。機(jī)器是一個邊長為L形(2L=100)覆感【正文算法動以后至少能夠清掃面積為1 的方格，下同）時，選擇可清感【正文算法動以后至少能夠清掃面積為1 的方格，下同）時，選擇可清掃的面積最大的進(jìn)行移動。如圖1，黑色方表積為2的方格，向右可以清掃面積為3的方格，按照這種算法，此時向右移動BA當(dāng)機(jī)器走到一個方格A以后，周圍沒有任何區(qū)域可以移動，遞歸就進(jìn)行回溯，找到一個可以向周圍移動的方格B。然后用寬度優(yōu)先搜索找A到B的

2、路徑，途中0的區(qū)域。如圖2，箭頭代表利用BFS 找出的路徑。從A 走到B 以后，還是利用剛才的策略繼續(xù)尋找。但是，如果出現(xiàn)一個狹長通道有許多小分支的情況，在H較小的情況下，這種策略就可以產(chǎn)生比較差的答 針對這種缺點(diǎn)，可以設(shè)計一個對策：在讀入數(shù)據(jù)以后，先用BFS找出起點(diǎn)到所有能達(dá)到的方格的最短距離dist(rc)，并求出(rc)所在的最大矩形空地area(rc)。然后，找出一個dist(r,carea(r,c)最大的點(diǎn)M。在未達(dá)到M的時候，所有的移動都以能否更靠近M為評判的第一標(biāo)準(zhǔn)。達(dá)到M以后XX23利用這種方法，能夠在許多情況下都取得比較好的效果。不過，需要注意的是，4 個方向的優(yōu)先級有級關(guān)系

3、，否則利用這種方法，能夠在許多情況下都取得比較好的效果。不過，需要注意的是，4 個方向的優(yōu)先級有級關(guān)系，否則程序得出的解不一定能令人滿意。由此，我猜想，是否能有辦法，根據(jù)當(dāng)時的情況，動態(tài) 算法對于一個非?？諘绲牡貓D，算法1雖然能夠獲得較優(yōu)的解，但并不很令人滿意。針對這種地圖，我設(shè)計了算法2。但是有的時候這種方法其實(shí)效果很差，因?yàn)樗赡軙?dǎo)致機(jī)器“陷入泥潭而不能自拔如圖4，機(jī)器A，就無路可走了，接下來只能原地打轉(zhuǎn)，很浪費(fèi)。因此，可以再追加一個規(guī)定：機(jī)器一旦無路可走，就使用BFS 找到最近的一個未清掃的方格B，從A 移動到B 繼續(xù)清掃。數(shù)據(jù)C BEFA 向A進(jìn)發(fā)。如果走C、D分支中的任意一個，回頭

4、的時候都會造成巨大浪費(fèi)。如果走E、F，浪費(fèi)則會相對B 代價最少的覆蓋方案，因此最后僅將主干通道和B 的全部以及A BA算法2的方案，覆蓋了B、C、D的全部，以及主干通道和E的一算法2的方案，覆蓋了B、C、D的全部，以及主干通道和E的一部分。雖然在C、D通道浪費(fèi)了不少移動，但最后的面積卻是33737。這再次說明，算法1所得出的方案，雖然目標(biāo)完全正確，但是在遍歷的數(shù)據(jù)（圖太大，不好截，估計是出題者利用Test_creator隨便畫出來的，是一個很開闊、很空曠的地圖L也很大，L=35, 129638的方格數(shù)據(jù)3（L=15, A 個L形有一段比較窄，而機(jī)器就在L形較窄的一端，這就造成了浪費(fèi)。算2形成的

5、遍歷一般都是螺旋形這也是算法2 使用螺旋形遍歷的一個原因。相比之下，算法1卻完成得很出色，覆蓋了面積為6854的方格，把能覆蓋的地方都覆蓋了數(shù)據(jù)明顯，基本上與算法1相同。這個地圖，最主要的就是要尋找一個最長的路徑。算法12 到80000 以上。數(shù)據(jù)（和第4個數(shù)據(jù)的圖是一樣的，但是L 個人認(rèn)為，這個數(shù)據(jù)的H設(shè)得過于大了，不管怎么做，都只能得到4855的覆蓋面積數(shù)據(jù)6（L=2, BADEGFC這個數(shù)據(jù)的H較小，屬于那利用好每一步移動的數(shù)據(jù)。最大的忌諱，就是不能走進(jìn)A、B、C數(shù)據(jù)6（L=2, BADEGFC這個數(shù)據(jù)的H較小，屬于那利用好每一步移動的數(shù)據(jù)。最大的忌諱，就是不能走進(jìn)A、B、C最好的策略是

6、撇開ABCDG不管，用蛇行法遍歷頂部和右邊的區(qū)域，然后進(jìn)入F，如果在將F 的油水榨干以后還有剩余的移動次數(shù)，就進(jìn)入E區(qū)域。這種策略：算法1把“1046”下方的一塊正方形遍歷了下來，但是沒有很好地利用上頂端和右邊的空地，最后覆蓋了面積為2074 的方格。算法2則更是愚蠢地將ABCD都遍歷了一遍，形成了巨大的浪費(fèi)，最后只覆蓋了面積為1296的方格數(shù)據(jù)ECADB這幅地圖雖然很小，但是比其他地圖更難。地圖屬于浪費(fèi)分支較多的狹長通道型地圖。A區(qū)域看似面在左側(cè)的狹長通道和D、E。算法12 都不理想。算法1ED做到的最優(yōu)的 是 154，可以用搜索算法獲得。數(shù)據(jù)（L=2, EAF為主的地圖，但又以空地E為關(guān)鍵

7、點(diǎn)。在區(qū)域A，只要進(jìn)行必要的移動即可BCD EAF為主的地圖，但又以空地E為關(guān)鍵點(diǎn)。在區(qū)域A，只要進(jìn)行必要的移動即可BCD三個 1完全相同，因此算法1的到了最優(yōu)解2004。而算法2就差一些，機(jī)器先進(jìn)入了F，在F遍理結(jié)束，入E 的時候，在F 數(shù)據(jù)9（L=5, BA這個數(shù)據(jù)并不難。H A 區(qū)域和底部的彎曲通道，直接進(jìn)入B 好的結(jié)果。算法12覆蓋的面積分別是1252512456數(shù)據(jù)10（L=3, ECD AB這幅地圖中，區(qū)域A和B面積都很大，可惜無法到達(dá)。區(qū)域C要好好利用。區(qū)域D算法1 遍歷了D BCF 的小空地，最終的結(jié)果是21950。要好好利用。區(qū)域D算法1 遍歷了D BCF 的小空地，最終的結(jié)

8、果是21950。算法2 同樣 DCBAE 域不過，最優(yōu)的辦法并非一定要如此，可以繞著墻走一圈，好好利用B區(qū)域，然后再進(jìn)入A 區(qū)域。這種方案可以保證不重復(fù)走任何一個方格。C 區(qū)域不宜進(jìn)入，除非能夠保證進(jìn)去就不再回頭，一旦回頭就會在D、E造成浪費(fèi)。算法1沒有獲得最優(yōu)解，它遍歷A區(qū)域時產(chǎn)生了一些浪費(fèi)，最終的覆蓋區(qū)域是1937。算法2要差一些，它的策略是繞著地圖邊界走，但是并沒有好好利用B區(qū)域，且對C區(qū)域的處理方法不當(dāng)12自測數(shù)據(jù)這個數(shù)刁難的地方，主要就Test_creator 寫了幾個字。這個圖的特點(diǎn)是：空地 為什么不能覆蓋所有區(qū)域呢？因?yàn)榇蠖鄶?shù)難度較高的數(shù)據(jù)，都是H較小H較小的情況下，管它會造成浪

9、費(fèi)1、2的策略進(jìn)行移動13自測數(shù)據(jù)3（100*100L=5,這個數(shù)據(jù)也很簡單，地圖就是一個螺旋13自測數(shù)據(jù)3（100*100L=5,這個數(shù)據(jù)也很簡單，地圖就是一個螺旋形的“死胡同定的通路的寬度正好是 L+1,主要H 較小，所以，只要順著道路向螺旋的中 域。5，黑色箭頭代表機(jī)器移動方向域代表未清掃的區(qū)域。有的程受這個未清掃 圖 蓋了面積為469714自測數(shù)據(jù)4（500*500L=11 算法1發(fā)揮得還不錯，覆蓋了面積為107216 的方格；算法2 并沒有想象得那樣出色，覆蓋區(qū)域的總面只有105467。估計是由于散點(diǎn)分布不規(guī)則，致使機(jī)器經(jīng)常走進(jìn)死胡同所造成的。15自測數(shù)據(jù)5（300*300，L=2

10、同，要想回頭，就要付出巨大代價，但經(jīng)常又不得不回頭。主要的空地，就是A、B、C、D4 個區(qū)域，其中尤以C和D最為重要（C處于一個環(huán)形通路之中，走回頭路時浪費(fèi)??；通向D的通道則比較寬，也利理想，算法2的效果比算法1好一些，它們覆蓋的面積分別和。DABC16自測數(shù)據(jù)6（100*100，DABC16自測數(shù)據(jù)6（100*100，L=2A 小，算法2與正確移動方向的一個巧合而已，如果向下走能覆蓋的面積17自測數(shù)據(jù)7（100*100，L=5這個數(shù)據(jù)，主要用于考驗(yàn)程序是否能夠好好利17自測數(shù)據(jù)7（100*100，L=5這個數(shù)據(jù)，主要用于考驗(yàn)程序是否能夠好好利用第2、3行的城垛狀缺口。在許多情況下，如果H 較

11、小，利用這種缺口往往會造成浪費(fèi)。而這個數(shù)據(jù)恰恰相反，如果不利用缺口，一般都沒有走完H步，那時算法1 和算法2 4031 407218自測數(shù)據(jù)8（100*100，L=2（地圖與自測數(shù)據(jù)7相同這個數(shù)據(jù)將L變小，H變大。可以說，這時所有的城垛狀缺口都不再是浪費(fèi)性質(zhì)的分支，機(jī)器要做的 是4633。19自測數(shù)據(jù)9（100*100，L=3這個數(shù)據(jù)，關(guān)鍵就在于A 區(qū)域。B C ，需要的步數(shù)小于HC 域之前，能夠?qū) 區(qū)域形成較好的覆蓋，最終的結(jié)果就會比較好。如果沒有有效覆蓋A 區(qū)域，進(jìn)入了這種數(shù)據(jù)顯然是算法1的弱項(xiàng)，最后覆蓋面積為50792 略好5121。兩個算法都對A區(qū)域利用得太少了。BAC20自測數(shù)據(jù)1

12、0（200*200L=8, 算法1覆蓋面積為29756，算法23096420自測數(shù)據(jù)10（200*200L=8, 算法1覆蓋面積為29756，算法2309641 說算法1 的毛病就在成了浪費(fèi)。但是，在H較大時，它往往比算法1更能利用好所經(jīng)過的空地。因此，算法21 視型”算法帶來的浪費(fèi)就越大；在H較大的時候，離起點(diǎn)越近，給“遠(yuǎn)視型”算法帶來的浪費(fèi)就越大“遠(yuǎn)視型”算法的浪費(fèi)問題。曾經(jīng)想過兩種方法，一是通過地圖的總面積與H 的大小關(guān)系，來判斷應(yīng)該是否進(jìn)入缺口，但后來發(fā)現(xiàn)是否進(jìn)入缺口并不僅僅取決于H與地圖面積之間的關(guān)系，加上這個判以后，效果反而更差了；第二種方法，就是剛開始還是一如既往地向目標(biāo)進(jìn)發(fā)，以

13、后如果要補(bǔ)救缺口，必讓機(jī)器趕回去，而是調(diào)整缺口旁邊的移動方案，這樣浪費(fèi)的步數(shù)就大為減少整的缺口非常多，它們的價值又各不相同，如果每次都尋找價值最大的缺口來調(diào)整移動方案，時間上就優(yōu)，不知道為什么地以后不再出來，兩種方法是沒什么區(qū)別的。如果進(jìn)入空地以后還要出去，螺旋法，一般來說會終止于地確定好出口，然后沿著空地的邊界走到出口的對面，再開始蛇行（如圖6）。我在上面如圖7，首先用BFS找出到起地以后不再出來，兩種方法是沒什么區(qū)別的。如果進(jìn)入空地以后還要出去，螺旋法，一般來說會終止于地確定好出口，然后沿著空地的邊界走到出口的對面，再開始蛇行（如圖6）。我在上面如圖7，首先用BFS找出到起點(diǎn)S 距離最遠(yuǎn)的點(diǎn)T，將從S到T 的路線作為初始路線。然后路 動次數(shù)的代價增加2。取增加面積最多的一段進(jìn)行改進(jìn)，得到一個改進(jìn)線路。然后對改進(jìn)線路同樣進(jìn)行類似的操作，如此循環(huán)往復(fù)，最后就可以得到一條長度為H的