【文章內(nèi)容簡(jiǎn)介】 件。 隨機(jī)化加上多次求解的改進(jìn)對(duì)這個(gè)漏洞也有一定效果，但是當(dāng)圖中邊的密度接近1時(shí)，算法可能要經(jīng)過(guò)很多次隨機(jī)才能找到那僅有的幾個(gè)不合法環(huán)。 這個(gè)漏洞的存在是因?yàn)槲覀冃枰牟⒉皇呛笙蜻厓啥它c(diǎn)之間的最短路徑長(zhǎng)度，我們需要的是這“兩個(gè)端點(diǎn)之間無(wú)弦路徑中最長(zhǎng)的一條的長(zhǎng)度”。如果這個(gè)長(zhǎng)度小于等于2，那么與這條反向邊對(duì)應(yīng)的所有環(huán)均合法，否則至少有一個(gè)不合法。 不幸的是，進(jìn)一步的思考證明，用樹(shù)形遞推的方法根本不可能在深搜樹(shù)中求出最長(zhǎng)無(wú)弦路徑的長(zhǎng)度。如何轉(zhuǎn)換思路、求出這個(gè)長(zhǎng)度的方法還在探索中……不能徹底解決問(wèn)題的一個(gè)改進(jìn) 起初，為了避免帶弦路徑的出現(xiàn)，我們直接采用了尋找最短路徑的方法。而這其實(shí)是無(wú)弦路徑中我們最不需要的一條（最好是最長(zhǎng)無(wú)弦路徑的長(zhǎng)度）。與其辛辛苦苦去找這么一條最沒(méi)用的路徑，我們倒不如任意地找一條，只要無(wú)弦就行。 其實(shí)，只要在搜索到一個(gè)點(diǎn)時(shí)，做一次由下向上的掃描，就可以得到它到每個(gè)祖先的某一條無(wú)弦路徑的長(zhǎng)度。具體方法并不復(fù)雜，我會(huì)將程序放在附件中，這里不再深入說(shuō)明。這個(gè)改進(jìn)在提高算法正確率的同時(shí)，把時(shí)間復(fù)雜度降到了O(N2+M)。結(jié)果 很可惜，最后的結(jié)果仍然不算完美。相信在繼續(xù)的思考與嘗試中，這個(gè)算法可以被做得更快、更好。[例] 可疑的斑點(diǎn) 題目來(lái)源：USACO 2005年十二月競(jìng)賽，Cow Patterns。 約翰的奶牛中有K(1≤K≤25,000)頭格外喜歡鬧事兒，排隊(duì)時(shí)她們總是站在一起。為了找出她們，約翰讓他所有的N(1≤N≤100,000)頭奶牛排成一列進(jìn)入畜棚，并希望你能告訴他隊(duì)列中的長(zhǎng)度為K的可疑群體。 約翰通過(guò)斑點(diǎn)數(shù)S(1≤S≤25)來(lái)辨別奶牛。他已經(jīng)忘了那些愛(ài)鬧事的奶牛身上具體有多少個(gè)斑點(diǎn)，但仍然記得在這些牛中誰(shuí)的斑點(diǎn)更多、或者哪些牛的斑點(diǎn)數(shù)一樣。于是他用一個(gè)由斑點(diǎn)數(shù)排名構(gòu)成的序列描述出了這些奶牛排成的隊(duì)伍。比如說(shuō)”1,4,4,3,2,1”表示：第一頭與最后一頭牛斑點(diǎn)數(shù)相同，并且比所有其它牛少；第五頭牛身上的斑點(diǎn)稍多一些；而第二頭和第三頭牛擁有最多的斑點(diǎn)。 請(qǐng)你幫助約翰在隊(duì)伍中找出所有符合描述的子序列。初步分析 這是一個(gè)模式串可以浮動(dòng)的模式匹配問(wèn)題。規(guī)模不小，很容易猜到最終的算法會(huì)與KMP算法有關(guān)。 直接套用肯定不行：KMP的高效在于模式串向后推移后，仍然保存著以前的匹配結(jié)果。在這個(gè)問(wèn)題中，模式串位置的推移很有可能會(huì)導(dǎo)致模式串本身的變化，以前的結(jié)果顯然就無(wú)法再用了。從整體枚舉到逐一枚舉 上面的分析告訴了我們一個(gè)簡(jiǎn)單的道理：KMP中的模式串必須始終不變，想用KMP就得先把模式串確定。這會(huì)讓人想到預(yù)先枚舉并一一匹配，但即使題目中的最大斑點(diǎn)數(shù)只有25，這也是不能接受的。最壞的情況下：在1..25這25個(gè)斑點(diǎn)數(shù)中選擇12個(gè)或13個(gè)對(duì)應(yīng)排名，具體的模式串會(huì)有500多萬(wàn)個(gè)，再來(lái)一一匹配，1秒的時(shí)間限制是遠(yuǎn)遠(yuǎn)不夠的。 這個(gè)枚舉可以剪枝！因?yàn)樵诖蠖鄶?shù)情況下，只是確定幾個(gè)排名就會(huì)發(fā)現(xiàn)這個(gè)模式串已經(jīng)不可能在原串中匹配成功了。新的算法改動(dòng)較大（因?yàn)樵儆眠f歸就顯得有些累贅了）：每次為一個(gè)排名枚舉出對(duì)應(yīng)的斑點(diǎn)數(shù)，用KMP算法得出這個(gè)不完整的模式串能匹配到原串的哪些位置（如題目所說(shuō)，用起點(diǎn)的位置代表一個(gè)子串）。注意到，這個(gè)模式串雖然不完整，但它是確定的：如果正在被枚舉的排名對(duì)應(yīng)的斑點(diǎn)數(shù)是5，那么其它排名在模式串中占的位置始終匹配除了5以外的所有斑點(diǎn)數(shù)，所以可以使用KMP算法。做完這些工作后，檢查原串中的每個(gè)位置，如果一個(gè)位置成功地匹配了所有排名，并且這些匹配中各個(gè)排名所對(duì)應(yīng)的斑點(diǎn)數(shù)正好與排名一致，那么從這個(gè)位置開(kāi)始的長(zhǎng)度為K的子串就是一個(gè)要找的可疑子串了。 比如，原串是”45858”、可疑子串的斑點(diǎn)排名是”121”。首先考慮排名為1的：當(dāng)它對(duì)應(yīng)5時(shí)，”5?5”可以匹配到原串的第2個(gè)位置；當(dāng)對(duì)應(yīng)8時(shí)，”8?8”可匹配到第3個(gè)位置；對(duì)應(yīng)其它斑點(diǎn)數(shù)時(shí)皆無(wú)處匹配。然后考慮排名2：對(duì)應(yīng)5時(shí)，”?5?”可匹配到3兩個(gè)位置；對(duì)應(yīng)8時(shí)，”?8?”只匹配第2個(gè)位置；其它無(wú)匹配?？偨Y(jié)果如下表：原串45858匹配第一個(gè)排名58匹配第二個(gè)排名585 3兩個(gè)位置都成功地匹配了兩個(gè)排名，但是第3個(gè)位置不滿足排名的大小順序要求，所以最后確定的可疑子串只有一個(gè)。跳過(guò)已被排除的位置 上面所說(shuō)的算法有了運(yùn)行時(shí)間上質(zhì)的飛躍，只是仍然無(wú)法完全達(dá)到題目的要求。 它的確還會(huì)做許多無(wú)用功：就上面的例子來(lái)說(shuō)，第一個(gè)排名不能匹配5這三個(gè)位置，那么考慮第二個(gè)排名時(shí)應(yīng)該直接跳過(guò)它們。進(jìn)一步看，如果按大小順序處理每個(gè)排名，大小關(guān)系的矛盾也可以讓我們放心地跳過(guò)一些位置。 但是在具體的操作過(guò)程中如何“跳過(guò)”一個(gè)位置呢？匹配完一個(gè)位置后，找到下一個(gè)仍有意義的位置再開(kāi)始匹配？這可就是樸素的模式匹配了！我們還是得利用KMP算法的思想：如果當(dāng)前位置已經(jīng)沒(méi)有意義，就繼續(xù)利用后綴函數(shù)把模式串向后推。KMP算法的小優(yōu)化 優(yōu)化到這一步，我們已經(jīng)得到了一個(gè)高效的算法。讓人奇怪的是，它在測(cè)試中出現(xiàn)了錯(cuò)誤。分析錯(cuò)誤之前，讓我們回憶一下KMP算法中對(duì)后綴函數(shù)的一個(gè)小優(yōu)化。小 優(yōu) 化 用一個(gè)例子來(lái)說(shuō)明。假設(shè)模式串是”aaab”，next()表示后綴函數(shù)。那么當(dāng)?shù)谌齻€(gè)a匹配失敗時(shí)，無(wú)優(yōu)化的KMP算法會(huì)把模式串向后推一位，嘗試匹配第二個(gè)a，即next(3)=2。但是這個(gè)匹配很明顯也會(huì)失敗，所以在這種情況下，可以直接把后綴函數(shù)值再向前賦一步，即next(3)=next(2)，以避免無(wú)畏的比較。 注意到，這個(gè)優(yōu)化有一個(gè)潛在的前提：每一次模式串后推都是由匹配失敗導(dǎo)致的。在這個(gè)前提下，我們才能確定，如果推移后模式串的待匹配字符沒(méi)有變化則匹配仍會(huì)失敗。但是在上面的算法中，我們還會(huì)用這種后推方式來(lái)跳過(guò)已被排除的位置——這時(shí)候匹配可能還可以繼續(xù)。 去掉優(yōu)化之后，問(wèn)題終于得到了圓滿的解決。啟示 如果把算法中這樣的細(xì)節(jié)出成問(wèn)答題，稍加揣摩，相信誰(shuí)也不會(huì)答錯(cuò)。但在緊張的考試中，一個(gè)之前從未被考慮過(guò)的細(xì)節(jié)卻極有可能被忽略。只有經(jīng)過(guò)了幾次錯(cuò)誤、投入了足夠的思考后，我們才能真正地掌握一個(gè)算法。 小結(jié) 與時(shí)間復(fù)雜度的優(yōu)化相比，尋找并糾正算法錯(cuò)誤是一種更靈活的優(yōu)化：對(duì)錯(cuò)誤的敏感使我們?cè)谶@方面有更多的靈感。廣泛積累、總結(jié)糾錯(cuò)經(jīng)驗(yàn)會(huì)使算法的設(shè)計(jì)過(guò)程更加流暢，讓我們不至于總是因?yàn)橐稽c(diǎn)小問(wèn)題無(wú)計(jì)可施、甚至從頭再來(lái)，讓算法的世界中條條大路通羅馬。四、結(jié)束語(yǔ) 每一次算法優(yōu)化都是一次思想的旅程，細(xì)心與經(jīng)驗(yàn)是思想的雙腳、特殊的信息是思想的路標(biāo)，無(wú)論是否走到了終點(diǎn)，思想都會(huì)有所收獲?！緟⒖嘉墨I(xiàn)】[1] Chordal Graph Isomorphism，作者不詳。[2] 算法藝術(shù)與信息學(xué)競(jìng)賽，作者：劉汝佳、黃亮。[3] USACO關(guān)于Flying Right的分析，作者：Bruce Merry。[4] 從一道題目的解法試談網(wǎng)絡(luò)流的構(gòu)造與算法，作者：江鵬?！靖兄x】衷心感謝吳亞妮老師對(duì)我的指導(dǎo)和幫助。衷心感謝曾呈、吳斌對(duì)論文提出的寶貴意見(jiàn)?！靖戒洝恳弧⒃}牧場(chǎng)規(guī)劃 小可可的好朋友Sealock最喜歡吃花生了，于是借用了小可可的牧場(chǎng)從事花生選種試驗(yàn)。他以網(wǎng)格的方式，非常規(guī)整地把牧場(chǎng)分割成M*N個(gè)矩形區(qū)域，由于各個(gè)區(qū)域中地水面、沼澤面積各不相同，因此各區(qū)域地實(shí)際可種植面積也各不相同，已知區(qū)域(i,j)地可種面積使A(i,j)。 每個(gè)區(qū)域種最多只能種植一個(gè)品種地花生?？煞N植面積為零地區(qū)域不能被選擇用來(lái)從事選種試驗(yàn)，同時(shí)為了防止花粉傳播到相鄰區(qū)域造成試驗(yàn)結(jié)果不正確，任何兩個(gè)相鄰的區(qū)域都不可以同時(shí)種植花生。這里說(shuō)的相鄰指的是兩個(gè)區(qū)域有公共邊，僅僅有公共點(diǎn)的兩個(gè)區(qū)域不算做相鄰。 小可可準(zhǔn)備幫助Sealock規(guī)劃一下如何選擇種植區(qū)域，才能使得實(shí)際可種植面積總和P最大。輸入： 文件第一行有兩個(gè)正整數(shù)，一次是M、N(M*N≤5000)，用空白字符隔開(kāi)。隨后的M行中，每行有N個(gè)不大于100的非負(fù)整數(shù)，都由空白字符隔開(kāi)，分別表示各區(qū)域的實(shí)際可種植面積A(i,j)。輸出： 輸出用于選種試驗(yàn)的各區(qū)域的實(shí)際可種植面積總和的最大值Pmax。樣例： 輸入 2 1 1 2 輸出 2 輸入 2 2 10 50 2 3 輸出 52Flying RightFiguring that they cannot do worse than the humans have, Farmer John39。s cows have decided to start an airline. Being cows, they decide to cater to the heretoforeuntapped market of cows as passengers. They plan to serve the cows who live along the western coast of Lake Michigan. Each morning, they will fly from the northernmost point of the coast southward towards Chicowgo, making many stops along the way. Each evening, they will fly back north to the northernmost point. They need your help to decide which passengers to carry each day. Each of N (1 = N = 10,000) farms numbered 1..N along the coast contains an airport (Farm 1 is northernmost。 farm N is southernmost). On this day, K (1 = K