信息學(xué)集訓(xùn)隊(duì)作業(yè)林希德0022visit

1、IOI2003國(guó)家集訓(xùn)隊(duì) 難題討論活動(dòng)階段IVPAGE PAGE 4訪問(wèn)解題報(bào)告金陵中學(xué) 林希德【題目大意】有一列客戶，當(dāng)客戶x向顧問(wèn)咨詢以后，該顧問(wèn)根據(jù)x的性別指示客戶x + 1到顧問(wèn)(male)處或(female)處。這樣，新的顧問(wèn)為客戶x+1服務(wù)。請(qǐng)你找出最短的客戶隊(duì)列，使得不論咨詢從哪個(gè)顧問(wèn)開(kāi)始，隊(duì)伍的最后一個(gè)客戶總遇到顧問(wèn)?！窘鉀Q情況】?jī)煞N算法：1、利用無(wú)判重的BFS在0.83s內(nèi)通過(guò)原始測(cè)試數(shù)據(jù)，其中時(shí)間復(fù)雜度，空間復(fù)雜度不超過(guò)60M（其中是最短客戶隊(duì)列的長(zhǎng)度）。2、利用“動(dòng)態(tài)規(guī)劃 + 反向搜索”在0.22s內(nèi)較好解決原始測(cè)試數(shù)據(jù)，復(fù)雜度無(wú)法估算；總的來(lái)說(shuō)，兩種算法都具備較好的實(shí)戰(zhàn)

2、性，可惜沒(méi)能將問(wèn)題徹底解決。【算法梗概】算法1：是客戶1可能訪問(wèn)的顧問(wèn)集合。如果客戶1為女性，那么客戶2可能訪問(wèn)的顧問(wèn)集合為；如果客戶1為男性，那么客戶2可能訪問(wèn)的顧問(wèn)集合為。根據(jù)這樣的規(guī)則，我們用BFS不斷擴(kuò)展出客戶3、客戶4、客戶5可能訪問(wèn)的顧問(wèn)集合，直到找到某大小為1的集合，即是問(wèn)題答案。算法2：布爾函數(shù)表示是否存在分別從顧問(wèn)i和顧問(wèn)j出發(fā)，客戶1為女性且長(zhǎng)度為k的訪問(wèn)隊(duì)列。定義類同。利用動(dòng)態(tài)規(guī)劃不斷求出GF和GM的值，一旦存在整數(shù)k滿足或者全部為真，立刻用反向搜索，判斷是否已經(jīng)找到合法隊(duì)列?！居懻撌斋@與感謝】當(dāng)可行解需滿足的條件十分苛刻不易求解時(shí)，轉(zhuǎn)而尋找滿足部分易求解條件的解也不失為

3、一種有效策略?！菊摹?一、算法1算法描述：因?yàn)閱?wèn)題要求“咨詢可以開(kāi)始于任何顧問(wèn)”，所以客戶1可能訪問(wèn)的顧問(wèn)集合必然是，這與訪問(wèn)隊(duì)列的具體內(nèi)容無(wú)關(guān)。如果是第k個(gè)客戶可能訪問(wèn)的顧問(wèn)集合，那么第k + 1個(gè)客戶的訪問(wèn)集合就應(yīng)該是（假設(shè)客戶k是女性）或者（假設(shè)客戶k是男性）。我們用一個(gè)長(zhǎng)度為n的布爾數(shù)組保存訪問(wèn)集合，然后根據(jù)上述規(guī)則BFS依次擴(kuò)展出客戶2、客戶3、客戶4的訪問(wèn)集合。過(guò)程如下： pp1 = 1，p2 = 1，p1 = 1n；While p1 = p2 doPp2+1 = 空集，Pp2+2 = 空集；For i = 1 n do If i在集合Pp1中 ThenPp2+1 = Pp2+1

4、 + Fi；Pp2+2 = Pp2+2 + Mi； End If If | Pp2+1 | 或者 | Pp2+2 | = 1 Then 輸出訪問(wèn)隊(duì)列，退出程序； p2 = p2 + 2，p1 = p1 + 1；End while復(fù)雜度分析：因?yàn)槁窂讲幌嗤?，所以客戶可能的訪問(wèn)集合恰有個(gè)，因此算法1的總復(fù)雜度決定于最短訪問(wèn)隊(duì)列的長(zhǎng)度T，即為。本題中N = 40，時(shí)空復(fù)雜度上限高達(dá)，因此，在BFS的過(guò)程中我們無(wú)奈地選擇了不判重。盡管由集合Pp1擴(kuò)展到集合Pp2時(shí)，元素個(gè)數(shù)不會(huì)增加，但也不保證嚴(yán)格減少。所以，一旦出現(xiàn)循環(huán)，不判重的BFS將擴(kuò)展出無(wú)限多的元素，我們只能考慮當(dāng)P2大到一定程度以后即退出Wh

5、ile，輸出無(wú)解。二、算法2算法描述：算法2實(shí)則是個(gè)靜態(tài)規(guī)劃的過(guò)程。定義布爾函數(shù)= true表示存在隊(duì)列S滿足：S1 = F；S的長(zhǎng)度不超過(guò)k；分別從顧問(wèn)i和顧問(wèn)j出發(fā)，隊(duì)列末端的顧客將遇到同一個(gè)顧問(wèn)；的定義類同。易知， = 或者 或者，= 或者或者。 我們以k的增長(zhǎng)來(lái)劃分DP階段，一旦發(fā)現(xiàn)k滿足或者全部為真，立刻用“反向搜索”判斷是否已經(jīng)找到合法隊(duì)列?！胺聪蛩阉鳌边^(guò)程如下： U= (x,y)；x,yU= (x,y)；x,y1.n；Search（U,k,空串）；void Search(集合 U；整數(shù)k；字符隊(duì)列str)如果k = 0 那么輸出str、結(jié)束所有程序；fv = GFi,j,k（i,

6、j）屬于U）均為真；mv = GMi,j,k（i,j）屬于U）均為真；If fv為真 ThenV = (Fi,Fj)：(i,j)屬于U；Search(V，k - 1，str + F)；End ifIf mv為真 ThenV = (Mi,Mj)：(i,j)屬于U；Search(V，k - 1，str + M)；End if當(dāng)然，如果某時(shí)出現(xiàn)=并且=，那么就停止靜態(tài)遞推而輸出無(wú)解。算法2的主要根據(jù)就是：自認(rèn)為出針對(duì)性的大數(shù)據(jù)實(shí)在不容易。 復(fù)雜度分析：空間復(fù)雜度 = DP的狀態(tài)數(shù) = 。時(shí)間復(fù)雜度 = DP的復(fù)雜度 + 反向搜索的復(fù)雜度 = + ；算法2的時(shí)間復(fù)雜度理論值較高，但實(shí)際遠(yuǎn)達(dá)不到。三、算法比較如果本題的數(shù)據(jù)規(guī)模只有20左右（事實(shí)上，官方測(cè)試數(shù)據(jù)最大為19），那么判重的BFS即算法1在理論上是時(shí)空都可以承受的NP算法。不過(guò)，從實(shí)際運(yùn)行效果看，算法2比算法1要好