優(yōu)先搜索應(yīng)用

1、萬(wàn)能的解題金鑰匙搜索基礎(chǔ)概念在我們遇到的一些問(wèn)題當(dāng)中，有些問(wèn)題不能夠確切的建立數(shù)學(xué)模型，或即便有數(shù)學(xué)模型但該模型的準(zhǔn)確方法也不一定能運(yùn)用現(xiàn)成算法。在要求枚舉方案時(shí)，常常會(huì)遇到這一類問(wèn)題。解決這一類問(wèn)題，我們一般采用搜索的方法解決，即從初始狀態(tài)出發(fā)，運(yùn)用題目所給出的條件和規(guī)則擴(kuò)展所有可能情況，從中找出滿足題意要求的解答。狀態(tài)：指當(dāng)前所面臨的具體問(wèn)題轉(zhuǎn)移：指從一個(gè)狀態(tài)到另一狀態(tài)的一種決策狀態(tài)和轉(zhuǎn)移可能是題目中已經(jīng)給出，也可能是需要自己分析出的。一道題的狀態(tài)與決策可能有多種。產(chǎn)生式系統(tǒng)：把狀態(tài)通過(guò)轉(zhuǎn)移得到的一顆狀態(tài)樹(shù)，稱作產(chǎn)生式系統(tǒng)廣度優(yōu)先搜索在搜索算法中，我們對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行拓展，深度越小的結(jié)點(diǎn)越先

2、得到擴(kuò)展，就是廣度優(yōu)先搜索法，下面通過(guò)一個(gè)具體實(shí)例來(lái)討論廣度優(yōu)先算法的一般規(guī)律。例題一八數(shù)碼難題：在33的棋盤上，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字。棋盤中留有一個(gè)空格（空格用0表示）?？崭裰車钠遄涌梢砸频娇崭裰?。要求解的問(wèn)題是：給出一種初始布局（初始狀態(tài)）和目標(biāo)面局（目標(biāo)狀態(tài)），找到一種最少步驟的移動(dòng)方法，實(shí)現(xiàn)從初始布局到目標(biāo)布局的轉(zhuǎn)變。 以上圖為例，從初始狀態(tài)到目標(biāo)狀態(tài)的最少步數(shù)方案如下：將8移到空位，將7移到空位，將4移到空位，將5移到空位，將6移到空位，將3移到空位，將2移到空位，將1移到空位。初始狀態(tài)目標(biāo)狀態(tài)分析由于題目要找到的解是達(dá)到目標(biāo)最少步驟，因此解題的方法為：從初

3、始狀態(tài)出發(fā)，先把移動(dòng)一步后的布局全部找到，檢查是否達(dá)到目標(biāo)布局，如果沒(méi)有，再?gòu)倪@些移動(dòng)一步的布局出發(fā)，找到移動(dòng)兩步后的所有布局，再判斷是否有達(dá)到目標(biāo)的，如此繼續(xù)，一直達(dá)到目標(biāo)狀態(tài)為止，輸出結(jié)果。由于是按移動(dòng)步數(shù)從少到多產(chǎn)生新布局的，所以找到的第一個(gè)目標(biāo)一定是移動(dòng)步數(shù)最少的一個(gè)，也就是最優(yōu)解。分析具體實(shí)現(xiàn)使用產(chǎn)生式系統(tǒng)：那么對(duì)于當(dāng)前的一個(gè)狀態(tài)，我們記錄如下信息：一個(gè)3*3的矩陣ch用于表示矩陣的布局，其中chi,j表示第i行，第j列所放的數(shù)字；為了方便程序編寫(xiě)，我們記錄空格的位置(si, sj)以及深度dep，即從初始狀態(tài)到達(dá)這個(gè)狀態(tài)的最少步數(shù)。分析因?yàn)樾庐a(chǎn)生的結(jié)點(diǎn)深度（也即從初始布局到該結(jié)點(diǎn)的

4、步數(shù)）一般要比數(shù)據(jù)庫(kù)原有結(jié)點(diǎn)大（或相等），按步數(shù)大的后擴(kuò)展的要求，應(yīng)該放在數(shù)據(jù)庫(kù)的后面。而當(dāng)前擴(kuò)展的結(jié)點(diǎn)從數(shù)據(jù)庫(kù)前面選取，即符合先產(chǎn)生的先擴(kuò)展，后產(chǎn)生的后擴(kuò)展規(guī)律。所以數(shù)據(jù)庫(kù)的結(jié)構(gòu)用隊(duì)列的結(jié)構(gòu)形式較合適。用上述記錄為元素的數(shù)組data來(lái)表示數(shù)據(jù)庫(kù)，并設(shè)置兩個(gè)指針：closed為隊(duì)列的首指針，open為隊(duì)列的尾指針。分析產(chǎn)生規(guī)則。原規(guī)則規(guī)定空格周圍的棋子可以向空格移動(dòng)。但如果換一產(chǎn)生規(guī)則。原規(guī)則規(guī)定空格周圍的棋子可以向空格移動(dòng)。但如果換一種角度觀察，也可看作空格向四周移動(dòng)。這樣處理更便于編程。如果種角度觀察，也可看作空格向四周移動(dòng)。這樣處理更便于編程。如果空格位置在（空格位置在（si，sj），則

5、有四條規(guī)則：），則有四條規(guī)則：（1）空格向上移動(dòng)。）空格向上移動(dòng)。 If si-1=1 then ch(si,sj)：=ch(si-1,sj); ch(si-1,sj):=0（2）空格向下移動(dòng)。）空格向下移動(dòng)。 If si+1=1 then ch(si,sj)：=ch(si,sj-1); ch(si,sj-1):=0（4）空格向右移動(dòng)。）空格向右移動(dòng)。 If sj+1=open； 隊(duì)列空隊(duì)列空具體程序?qū)崿F(xiàn)參照具體程序?qū)崿F(xiàn)參照ppt附帶的附帶的num8.pas總結(jié)與拓展從上例可以看出，廣度優(yōu)先搜索法可以求出步數(shù)最少的解，即深度最少的解。與深度優(yōu)先搜索類似，不同的問(wèn)題，用廣度優(yōu)先搜索的基本算法是一

6、樣的，但在數(shù)據(jù)庫(kù)的表示方法、產(chǎn)生的結(jié)點(diǎn)是否符合條件和重復(fù)的判斷上可以有不同的編程技巧，程序的運(yùn)行效率也有所不同。以八數(shù)碼問(wèn)題為例，上面的程序中用3*3的二維數(shù)組表示布局比較直觀，但在判斷重復(fù)，判斷是否達(dá)到目標(biāo)方面，卻給程序增加了復(fù)雜性，也影響了運(yùn)行速度?？梢愿挠米址问絹?lái)表示布局，第1.3個(gè)數(shù)表示第一行的三個(gè)數(shù)，第4.6個(gè)數(shù)，表示第二行的三個(gè)數(shù)，第7.9個(gè)數(shù)表示第三行的三個(gè)數(shù)。例如初始布局表示為“123456780”，目標(biāo)布局表示為“012563478”。產(chǎn)生規(guī)則也必須作相應(yīng)改動(dòng)。設(shè)空格當(dāng)前位置是SI，則有：（1）空格向上移動(dòng)：空格的位置減3，即交換SI和SI-3的字符；（2）空格向左移動(dòng)：

7、空格的位置減1，即交換SI和SI-1的字符；（3）空格向右移動(dòng)：空格的位置加1，即交換SI和SI+1的字符；（4）空格向下移動(dòng)：空格的位置加3，即交換SI和SI+3的字符。如設(shè)規(guī)則編號(hào)為k，則上述四條規(guī)則可歸納為一條：交換SI和SI+（2*k-5）的字符布局用字符串表示，使得判斷重復(fù)過(guò)程和判斷目標(biāo)的過(guò)程變得很簡(jiǎn)單，只需判斷兩個(gè)字符串是否相等就可以了。按照上述的改進(jìn)，讀者可自己編制的解八數(shù)碼問(wèn)題的程序?？偨Y(jié)與拓展一般廣度優(yōu)先搜索的基本框架根據(jù)八數(shù)碼問(wèn)題的基本框架，與一般廣度優(yōu)先搜索的基本思想，我們可以根據(jù)八數(shù)碼問(wèn)題的基本框架，與一般廣度優(yōu)先搜索的基本思想，我們可以得到如下一般廣度優(yōu)先搜索的基本框

8、架。得到如下一般廣度優(yōu)先搜索的基本框架。Program BFS;初始化；建立數(shù)據(jù)庫(kù)初始化；建立數(shù)據(jù)庫(kù)data；初始狀態(tài)存入數(shù)據(jù)庫(kù)；初始狀態(tài)存入數(shù)據(jù)庫(kù)data；設(shè)隊(duì)列首指針設(shè)隊(duì)列首指針closed：=0； 隊(duì)列尾指針隊(duì)列尾指針open：=1；RepeatClosed增增1，取出，取出closed所指結(jié)點(diǎn)進(jìn)行擴(kuò)展；所指結(jié)點(diǎn)進(jìn)行擴(kuò)展；For r：=1 to rmax do r為產(chǎn)生規(guī)則編號(hào)為產(chǎn)生規(guī)則編號(hào)BeginIf 子結(jié)點(diǎn)符合條件子結(jié)點(diǎn)符合條件 thenBegin Open增增1，并把新結(jié)點(diǎn)存入數(shù)據(jù)庫(kù)隊(duì)尾；，并把新結(jié)點(diǎn)存入數(shù)據(jù)庫(kù)隊(duì)尾； If 新結(jié)點(diǎn)與原有結(jié)點(diǎn)重復(fù)新結(jié)點(diǎn)與原有結(jié)點(diǎn)重復(fù) then 刪去

9、該結(jié)點(diǎn)（刪去該結(jié)點(diǎn)（open減減1） Else if 新結(jié)點(diǎn)即目標(biāo)新結(jié)點(diǎn)即目標(biāo) then 輸出并退出；輸出并退出；End；End；Until closed=open； 隊(duì)列空隊(duì)列空例題二翻幣問(wèn)題。有N個(gè)硬幣（N6）正面朝上排成一排，每次將5個(gè)硬幣翻過(guò)來(lái)放在原位置，直到最后全部硬幣翻成反面朝上為止。編程讓計(jì)算機(jī)找出步數(shù)最少的翻法并把翻幣過(guò)程及次數(shù)打印出來(lái)（用O表示正面，*表示反面）。例如N=6的情況：step 0: oooooostep 1: *ostep 2: oooo*step 3: *ooostep 4: oo*step 5: *ooooostep 6: *分析由于問(wèn)題要求找出最少步驟，用

10、廣度優(yōu)先搜索法來(lái)求解。表面看，翻幣的過(guò)程與正反面硬幣的排列位置有關(guān)，但只要經(jīng)過(guò)仔細(xì)分析會(huì)發(fā)現(xiàn)：實(shí)際上翻幣過(guò)程僅與硬幣正反面的個(gè)數(shù)有關(guān)，與它們的位置是無(wú)關(guān)的。例如下面兩種狀態(tài)：O * O * O * O O* * * O O O O O都只要把5個(gè)正面朝上的硬幣翻過(guò)來(lái)就達(dá)到了目標(biāo)。因此在搜索過(guò)程中只需考慮當(dāng)前狀態(tài)正面朝上的個(gè)數(shù)。分析又如，如果當(dāng)前狀態(tài)是：* * * O O * * *翻第1，2，4，6，8個(gè)得到：O O * * O O * O而翻第3，5，6，7，8個(gè)得到：* * O O * O O O這兩種翻法雖翻的硬幣不同，但都是把原狀態(tài)中4個(gè)反面朝上1個(gè)正面朝上的硬幣翻過(guò)來(lái)。結(jié)果狀態(tài)不同，

11、但都有5個(gè)硬幣正面朝上，再翻一次就都可以達(dá)到目標(biāo)。所以產(chǎn)生規(guī)則也只需考慮翻正面朝上的硬幣的個(gè)數(shù)不同就可以了。分析建立產(chǎn)生式系統(tǒng)。其中：綜合數(shù)據(jù)庫(kù)。綜合數(shù)據(jù)庫(kù)中每個(gè)記錄設(shè)計(jì)為三項(xiàng)：當(dāng)前狀態(tài)中硬幣正面朝上的個(gè)數(shù)，父結(jié)點(diǎn)位置，由父結(jié)點(diǎn)翻了幾個(gè)正面朝上的硬幣得到當(dāng)前狀態(tài)。數(shù)據(jù)庫(kù)本身用隊(duì)列形式。產(chǎn)生規(guī)則有六條，即翻R(0=R=5)個(gè)正面朝上的硬幣：if 當(dāng)前結(jié)點(diǎn)正面朝上的硬幣個(gè)數(shù)MR且反面朝上的個(gè)數(shù)5-Rthen 子結(jié)點(diǎn)data=（M-R）+（5-R） R=0，1，2，5搜索策略。采用廣度優(yōu)先搜索法求解。具體程序見(jiàn)目錄下coin.pas例題三有兩個(gè)無(wú)刻度標(biāo)志的水壺，分別可裝x升和y升（x、y為整數(shù)，x、

12、y=100）的水，設(shè)另有一水缸，可用來(lái)向水壺灌水或倒出水，兩水壺間，水也可以相互傾灌。已知x升壺為滿壺，y升壺為空壺。問(wèn)如何通過(guò)倒水或灌水操作，用最少步數(shù)能在y升壺中量出z(0且b0且a0時(shí),可以從水壺A倒a升水給水缸,這時(shí)水壺A內(nèi)有0升水.水壺B內(nèi)有b升水；(4)當(dāng)a0時(shí),可以從水壺B倒b升水給水缸，這時(shí)水壺A內(nèi)有a升水；水壺B內(nèi)有0升水（6）當(dāng)by時(shí),可以從水缸倒y-b升水給水壺B，這時(shí)水壺A內(nèi)有a升水水壺B內(nèi)有y升水分析初始時(shí)，水壺A內(nèi)有x升水，水壺B內(nèi)有0升水。綜合數(shù)據(jù)庫(kù)：可用一個(gè)記錄類型描述一個(gè)狀態(tài)：atype=recordfather，a，b：word； end；father記錄當(dāng)

13、前節(jié)點(diǎn)的父親節(jié)點(diǎn)的編號(hào)，a、b表示當(dāng)前狀態(tài)中，水壺A和水壺B里各有多少水。整個(gè)數(shù)據(jù)庫(kù)可用一個(gè)以為數(shù)組DATA1.10000 of atype;另外用一個(gè)標(biāo)志數(shù)組bool，當(dāng)boolI，j為真，表示水壺A為I升，水壺B為j升的狀態(tài)還沒(méi)有產(chǎn)生過(guò)，反之則表示已產(chǎn)生過(guò)。使用廣度優(yōu)先搜索求解即可。源程序見(jiàn)目錄下battle.pas例題四 黑白棋游戲的棋盤由44方格陣列構(gòu)成。棋盤的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。這16枚棋子的每一種放置方案都構(gòu)成一個(gè)游戲狀態(tài)。在棋盤上擁有1條公共邊的2個(gè)方格稱為相鄰方格。一個(gè)方格最多可有4個(gè)相鄰方格。在玩黑白棋游戲時(shí)，每一步可將任何2個(gè)相鄰方格中棋子互

14、換位置。對(duì)于給定的初始游戲狀態(tài)和目標(biāo)游戲狀態(tài)，編程計(jì)算從初始游戲狀態(tài)變化到目標(biāo)游戲狀態(tài)的最短著棋序列。分析首先分析狀態(tài)量，16個(gè)格子，每個(gè)格子可以是黑或者白，所以狀態(tài)不超過(guò)216，這個(gè)狀態(tài)量是很小的，完全可以進(jìn)行廣搜。狀態(tài)：一個(gè)4*4的棋盤決策：將任何2個(gè)相鄰方格中棋子互換位置分析那么廣搜的判重就可以用hash表來(lái)解決把16個(gè)格子的黑白棋看成是一個(gè)二進(jìn)制數(shù)，那么一個(gè)狀態(tài)就對(duì)應(yīng)一個(gè)數(shù)，這是最簡(jiǎn)單的hash函數(shù)通過(guò)這樣的hash函數(shù)，hash是可以不用掛鏈的例題五分析看到這一問(wèn)題，首先想到的自然是廣度優(yōu)先搜索。但是搜索中必然會(huì)出現(xiàn)許多重復(fù)，大大的增加了時(shí)空復(fù)雜度，比如連用兩次規(guī)則A顯然是浪費(fèi)的，因

15、此需要判重。如果是用傳統(tǒng)的比較方法來(lái)排除重復(fù)的話，無(wú)疑將花去很多的時(shí)間，事實(shí)上也的確如此。因?yàn)?，我們需要找到一種更為便捷的方法，來(lái)進(jìn)行判重。受多維數(shù)組元素地址的計(jì)算方法的啟發(fā)，可以將矩陣的每一種狀態(tài)按以下規(guī)則對(duì)應(yīng)于一個(gè)雙字節(jié)的整數(shù)K：（1）用一維數(shù)組S1.8表示一種狀態(tài)。例如初始狀態(tài)Si=i；（2）令Ti表示S1.i-1這i-1個(gè)數(shù)中，比Si小的數(shù)的個(gè)數(shù)；（3） 分析81)!1(*iiiTK可以證明040319之間的每一個(gè)整數(shù)都唯一的對(duì)應(yīng)了一個(gè)T數(shù)列，也就是說(shuō)，魔板的每一個(gè)狀態(tài)都與每一個(gè)整數(shù)一一對(duì)應(yīng)。n!=(n-1)*(n-1)!+(n-1)!n!=(n-1)*(n-1)!+(n-2)*(n-

16、2)!+(n-3)*(n-3)!+2*2!+1*1!+1 n!-1=(n-1)*(n-1)!+(n-2)*(n-2)!+(n-3)*(n-3)!+2*2!+1*1!這一式子類似于10k-1=9*10k-1+9*10k-2+9*100，對(duì)于上面的結(jié)論就很容易證明了。分析因此可以用一個(gè)040319的布爾型映射數(shù)組，初始狀態(tài)為假。如果一種狀態(tài)已經(jīng)搜索到，則將其對(duì)應(yīng)的數(shù)組元素標(biāo)記為真。判斷一種狀態(tài)是否與以前的狀態(tài)重復(fù)的時(shí)候，只需要檢查該狀態(tài)所對(duì)應(yīng)的數(shù)組元素，若為真則該狀態(tài)一定已經(jīng)搜索到了。這樣省略了查找工作的時(shí)間量，雖然多花了40k的空間，卻大大提高了時(shí)間效率。在廣度搜索當(dāng)中，擴(kuò)張出來(lái)的新的節(jié)點(diǎn)總是有

17、很大的重復(fù)，必須對(duì)這些節(jié)點(diǎn)進(jìn)行判重操作，最簡(jiǎn)單判重方法是相當(dāng)耗時(shí)的，它需要將新的節(jié)點(diǎn)與已經(jīng)生成的節(jié)點(diǎn)分別進(jìn)行比較，在搜索的初期階段，這一步的耗時(shí)是不明顯的，但隨著節(jié)點(diǎn)數(shù)目增大，判重的耗時(shí)相對(duì)就大大增加，從而降低了算法的時(shí)間效率。為了省去這一個(gè)判重工作，往往是利用數(shù)據(jù)結(jié)構(gòu)當(dāng)中的哈希表。源程序見(jiàn)目錄下exchange.pas哈希表的缺點(diǎn)但是哈希表的運(yùn)用并不是萬(wàn)能的，因?yàn)楣１肀旧硪泊嬖谥粋€(gè)很大的缺點(diǎn)，就是其所占用的空間很大，在很多搜索問(wèn)題當(dāng)中哈希表都是無(wú)法定義的，但是有的時(shí)候表面上看來(lái)哈希表示無(wú)法定義的，但是可以采用壓縮存儲(chǔ)的方法進(jìn)行定義?？聪旅孢@一個(gè)例題。例題六補(bǔ)丁與錯(cuò)誤。（補(bǔ)丁與錯(cuò)誤。（CT

18、SC99）錯(cuò)誤就是人們所說(shuō)的錯(cuò)誤就是人們所說(shuō)的Bug。用戶在使用軟件時(shí)總是希望其錯(cuò)。用戶在使用軟件時(shí)總是希望其錯(cuò)誤越少越好，最好是沒(méi)有錯(cuò)誤的。但是推出一個(gè)沒(méi)有錯(cuò)誤誤越少越好，最好是沒(méi)有錯(cuò)誤的。但是推出一個(gè)沒(méi)有錯(cuò)誤的軟件幾乎不可能。所有很多軟件公司都在瘋狂地發(fā)放補(bǔ)的軟件幾乎不可能。所有很多軟件公司都在瘋狂地發(fā)放補(bǔ)?。ㄓ袝r(shí)這種補(bǔ)丁甚至是收費(fèi)的）。?。ㄓ袝r(shí)這種補(bǔ)丁甚至是收費(fèi)的）。T公司就是其中之一。公司就是其中之一。上個(gè)月，上個(gè)月，T公司推出了一個(gè)新的字處理軟件，隨后發(fā)放了一公司推出了一個(gè)新的字處理軟件，隨后發(fā)放了一批補(bǔ)丁。最近批補(bǔ)丁。最近T公司發(fā)現(xiàn)其發(fā)放的補(bǔ)丁有致命的問(wèn)題，那就公司發(fā)現(xiàn)其發(fā)放的補(bǔ)丁

19、有致命的問(wèn)題，那就是一個(gè)補(bǔ)丁在排除某些錯(cuò)誤的同時(shí)，往往會(huì)加入另一些錯(cuò)是一個(gè)補(bǔ)丁在排除某些錯(cuò)誤的同時(shí)，往往會(huì)加入另一些錯(cuò)誤。此字處理軟件只可能出現(xiàn)誤。此字處理軟件只可能出現(xiàn)n個(gè)特定的錯(cuò)誤，這個(gè)特定的錯(cuò)誤，這n個(gè)錯(cuò)誤個(gè)錯(cuò)誤是由軟件公司本身決定的。是由軟件公司本身決定的。T公司目前公發(fā)放了公司目前公發(fā)放了m個(gè)補(bǔ)丁，個(gè)補(bǔ)丁，對(duì)于每一個(gè)補(bǔ)丁，都有特定的適用環(huán)境，某個(gè)補(bǔ)丁只有在對(duì)于每一個(gè)補(bǔ)丁，都有特定的適用環(huán)境，某個(gè)補(bǔ)丁只有在當(dāng)前軟件中包含某些錯(cuò)誤而同時(shí)又不包含另一些錯(cuò)誤時(shí)才當(dāng)前軟件中包含某些錯(cuò)誤而同時(shí)又不包含另一些錯(cuò)誤時(shí)才可以使用，如果它被使用，它將修復(fù)某些錯(cuò)誤而同時(shí)加入可以使用，如果它被使用，它將修復(fù)

20、某些錯(cuò)誤而同時(shí)加入某些錯(cuò)誤。另外，使用每個(gè)補(bǔ)丁都要耗一定的時(shí)間（即補(bǔ)某些錯(cuò)誤。另外，使用每個(gè)補(bǔ)丁都要耗一定的時(shí)間（即補(bǔ)丁程序運(yùn)行的時(shí)間）。丁程序運(yùn)行的時(shí)間）。例題六更準(zhǔn)確地說(shuō)明如下：更準(zhǔn)確地說(shuō)明如下：此字處理軟件中可能出現(xiàn)的此字處理軟件中可能出現(xiàn)的n個(gè)錯(cuò)誤為集合個(gè)錯(cuò)誤為集合B=b1,b2,bn中中的元素，的元素，T公司目前共發(fā)放了公司目前共發(fā)放了m個(gè)補(bǔ)?。簜€(gè)補(bǔ)?。簆1,p2,pm。對(duì)于。對(duì)于每一個(gè)補(bǔ)丁每一個(gè)補(bǔ)丁pi，都有特定的適用環(huán)境，某個(gè)補(bǔ)丁只有在軟件中，都有特定的適用環(huán)境，某個(gè)補(bǔ)丁只有在軟件中包含某些錯(cuò)誤而同時(shí)又不包含另一些錯(cuò)誤時(shí)才可以使用，為了包含某些錯(cuò)誤而同時(shí)又不包含另一些錯(cuò)誤時(shí)才可以

21、使用，為了說(shuō)明清楚，設(shè)錯(cuò)誤集合：說(shuō)明清楚，設(shè)錯(cuò)誤集合：Bi-、Bi+，當(dāng)軟件包含了，當(dāng)軟件包含了Bi+中的所有中的所有錯(cuò)誤，而沒(méi)有包含錯(cuò)誤，而沒(méi)有包含Bi-中的任何錯(cuò)誤時(shí)，補(bǔ)丁中的任何錯(cuò)誤時(shí)，補(bǔ)丁Pi才可以被使用，才可以被使用，否則不能被使用，顯然否則不能被使用，顯然Bi+、Bi-交集為空。補(bǔ)丁交集為空。補(bǔ)丁Pi將修復(fù)某些將修復(fù)某些錯(cuò)誤而同時(shí)加入某些錯(cuò)誤，設(shè)錯(cuò)誤集合為錯(cuò)誤而同時(shí)加入某些錯(cuò)誤，設(shè)錯(cuò)誤集合為Fi-、Fi+，使用過(guò)補(bǔ)，使用過(guò)補(bǔ)丁丁Pi之后，之后，F(xiàn)i-中的任何錯(cuò)誤都不會(huì)在軟件中出現(xiàn)，而軟件將包中的任何錯(cuò)誤都不會(huì)在軟件中出現(xiàn)，而軟件將包含含F(xiàn)i+中的所有錯(cuò)誤。同樣中的所有錯(cuò)誤。同樣Fi

22、-，F(xiàn)i+交集為空。另外，使用每個(gè)交集為空。另外，使用每個(gè)補(bǔ)丁都要耗一定的時(shí)間（即補(bǔ)丁程序的運(yùn)行時(shí)間）。補(bǔ)丁都要耗一定的時(shí)間（即補(bǔ)丁程序的運(yùn)行時(shí)間）?，F(xiàn)在現(xiàn)在T公司的問(wèn)題很簡(jiǎn)單，其字處理軟件的初始版本不幸包含公司的問(wèn)題很簡(jiǎn)單，其字處理軟件的初始版本不幸包含了集合了集合B中的全部中的全部n個(gè)錯(cuò)誤，有沒(méi)有可能通過(guò)使用這些補(bǔ)丁（任個(gè)錯(cuò)誤，有沒(méi)有可能通過(guò)使用這些補(bǔ)?。ㄈ我忭樞虻厥褂?，一個(gè)補(bǔ)丁可以使用多次），使此字處理軟件成意順序地使用，一個(gè)補(bǔ)丁可以使用多次），使此字處理軟件成為一個(gè)沒(méi)有錯(cuò)誤的軟件。如果可能，希望找到耗時(shí)最少的方案。為一個(gè)沒(méi)有錯(cuò)誤的軟件。如果可能，希望找到耗時(shí)最少的方案。分析這顯然是一道

23、求最優(yōu)解的題目，以各類錯(cuò)誤的出現(xiàn)情況為狀態(tài)，可以計(jì)算出所有狀態(tài)的總數(shù)為 。如果采用深度優(yōu)先搜索的話，由于遞歸的層數(shù)過(guò)多，是不可行的。自然想到了廣度優(yōu)先搜索。但是狀態(tài)判重編程是棘手的問(wèn)題，是否還能夠采用哈希表呢？表面上看來(lái)，哈希表需要的空間為 。但是一個(gè)Byte型的整數(shù)，是由8個(gè)二進(jìn)制為構(gòu)成的，因此對(duì)于8個(gè)布爾類型的數(shù)，可以把它壓縮成占一個(gè)字節(jié)的Byte型整數(shù)，這樣一來(lái)哈希表所占用的空間就只需要128Kb了，程序是完全可以承受的。1048576220MbKbbyte11024220分析在具體的實(shí)現(xiàn)過(guò)程當(dāng)中，為了滿足最優(yōu)性，每次對(duì)權(quán)值最小的節(jié)點(diǎn)在具體的實(shí)現(xiàn)過(guò)程當(dāng)中，為了滿足最優(yōu)性，每次對(duì)權(quán)值最小的

24、節(jié)點(diǎn)進(jìn)行擴(kuò)展，然后對(duì)新生成的節(jié)點(diǎn)進(jìn)行處理，如果某一個(gè)節(jié)點(diǎn)已經(jīng)被進(jìn)行擴(kuò)展，然后對(duì)新生成的節(jié)點(diǎn)進(jìn)行處理，如果某一個(gè)節(jié)點(diǎn)已經(jīng)被擴(kuò)展了，就不對(duì)其進(jìn)行處理。如果這一個(gè)節(jié)點(diǎn)處在隊(duì)列之中還未被擴(kuò)展了，就不對(duì)其進(jìn)行處理。如果這一個(gè)節(jié)點(diǎn)處在隊(duì)列之中還未被擴(kuò)展，則調(diào)整隊(duì)列當(dāng)中的這個(gè)節(jié)點(diǎn)的權(quán)值。如果這個(gè)節(jié)點(diǎn)既不在隊(duì)擴(kuò)展，則調(diào)整隊(duì)列當(dāng)中的這個(gè)節(jié)點(diǎn)的權(quán)值。如果這個(gè)節(jié)點(diǎn)既不在隊(duì)列之中，又未被擴(kuò)展則加入隊(duì)列當(dāng)中。列之中，又未被擴(kuò)展則加入隊(duì)列當(dāng)中。對(duì)于一個(gè)狀態(tài)可以把其描述成為一個(gè)對(duì)于一個(gè)狀態(tài)可以把其描述成為一個(gè)01串，串的長(zhǎng)度為錯(cuò)誤的總個(gè)串，串的長(zhǎng)度為錯(cuò)誤的總個(gè)數(shù)，數(shù)，0表示沒(méi)有這個(gè)錯(cuò)誤，表示沒(méi)有這個(gè)錯(cuò)誤，1表示有這個(gè)錯(cuò)誤。

25、然后把這個(gè)表示有這個(gè)錯(cuò)誤。然后把這個(gè)01串看作串看作成一個(gè)二進(jìn)制數(shù)，把它化成對(duì)應(yīng)的十進(jìn)制數(shù)，這個(gè)十進(jìn)制數(shù)就是一成一個(gè)二進(jìn)制數(shù)，把它化成對(duì)應(yīng)的十進(jìn)制數(shù)，這個(gè)十進(jìn)制數(shù)就是一個(gè)對(duì)應(yīng)的狀態(tài)了。在搜索的過(guò)程當(dāng)中，主要是利用哈希表來(lái)判斷狀個(gè)對(duì)應(yīng)的狀態(tài)了。在搜索的過(guò)程當(dāng)中，主要是利用哈希表來(lái)判斷狀態(tài)是否已經(jīng)進(jìn)行過(guò)擴(kuò)展。下面是對(duì)哈希表的定義：態(tài)是否已經(jīng)進(jìn)行過(guò)擴(kuò)展。下面是對(duì)哈希表的定義： type TList=array1.128of Byte; var Hash: array1.1024of Tlist;分析將狀態(tài)K（0Ktime2timen，使得處理機(jī)有序化，其中time1便是完成所有工作的時(shí)間。用貪心法可

26、以得到time1的上限，并且我們可以計(jì)算出time1的下限，然后搜索。貪心求上限的方法無(wú)非是構(gòu)造一組可行解，使得time1盡量小。比如說(shuō)我們依次掃描每一個(gè)物品，在滿足time1time2timen的條件下，往背包內(nèi)放，這樣就可以構(gòu)造出一組可行解出來(lái)，我們就可以拿這時(shí)的time1作為上界了。偽代碼Procedure dfs(i:integer); i表示當(dāng)前搜索到了哪一個(gè)處理機(jī)For i:=1 to m do if (not boi) and 該作業(yè)未被之前的處理機(jī)處理 (timei+ti=timei-1) then 滿足timei=timei-1Beginboi:=true; 標(biāo)記改作業(yè)已被處

27、理timei:=timei+ti;Dfs(i+1);boi:=false; 取消標(biāo)記timei:=timei-ti; End生日蛋糕條件1：V = n H = m 層 形狀：每層都是一個(gè)圓柱體。條件2： 設(shè)從下往上數(shù)第i(1=i=m)層蛋糕是半徑為Ri, 高度為Hi的圓柱。 當(dāng)iRi+1且HiHi+1。條件3： 表面積Q最小，令Q= S問(wèn)題： 給出的n和m， 找出蛋糕的制作方案（適當(dāng)?shù)腞i和Hi的值），使S最小。 (除Q外，以上所有數(shù)據(jù)皆為正整數(shù))輸入 n (n=10000)， m (m Ri+1 （2） Hi Hi+1 （3） Vi+1 = Vi - Ri+1* Ri+1* Hi+1 （4）

28、 Si+1 = Si + 2 * Ri+1* Hi+1確定第一層蛋糕的大小根據(jù)上一層蛋糕的大小確定下一層蛋糕該怎么做看是否符合條件 1）是否做到了m層 2）是否最終體積為0 3）是否當(dāng)前面積最小若上述條件成立，則保留當(dāng)前最優(yōu)值，否則繼續(xù)做下一層蛋糕，若重做蛋糕基本算法Search (i, Ri , Hi , Si , Vi) 對(duì)每層蛋糕進(jìn)行搜索if (i=m) and (Vi =0) then 更新最優(yōu)值else for Ri + 1Ri -1 downto i for Hi + 1Hi -1 downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi -

29、Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) Problem-Cake枚舉所有的初始狀態(tài) - 第一層蛋糕的大小 for R1m to sqrt ( n ) do /*假設(shè) H1=1，只做一層蛋糕 */ for H1n div (R1*R1) downto m do S1=2 * R1* H1+ R1* R1 V1=n - R1* R1 * H1 Search (1, R1, H1, S1, V1) 優(yōu)化？（1 1）因?yàn)橹烙嘞碌牡案怏w積）因?yàn)橹烙嘞碌牡案怏w積, ,因此可以估算一下余下側(cè)面積因此可以估算一

30、下余下側(cè)面積, , 這樣我們可以就加入如下剪枝條件這樣我們可以就加入如下剪枝條件: : if if 當(dāng)前的表面積當(dāng)前的表面積 + + 余下的側(cè)面積余下的側(cè)面積 當(dāng)前最優(yōu)值當(dāng)前最優(yōu)值 then exitthen exit 設(shè)已經(jīng)做了設(shè)已經(jīng)做了i i層蛋糕層蛋糕, ,則還需做則還需做m-im-i層層, , S Si i：為第：為第i i層蛋糕的側(cè)面積層蛋糕的側(cè)面積, , FSFSi i：余下的側(cè)面積：余下的側(cè)面積, ,怎么求怎么求FSFSi i ? ? 因?yàn)橐驗(yàn)? : 2Vi= 2Ri+1 * Ri+1 * Hi+1 + .+ 2Rm * Rm * Hm = Ri+1 * Si+1 + .+ Rm

31、 * Sm Ri+1 * (Si+1+ .+ Sm) = Ri+1 * FSi 所以所以: : FSi 2Vi / Ri+1 因此剪枝條件為：因此剪枝條件為： if Si-1 + 2 * Vi-1 / Ri 當(dāng)前最優(yōu)值當(dāng)前最優(yōu)值 then exit優(yōu)化？(2)如果剩下的蛋糕材料太少，不能保證做到m層,那么沒(méi)有必要繼續(xù)往下做了，設(shè)，最m層半徑和高都為1，Rm=Hm=1第m-1層半徑和高都為2，Rm-1=Hm-1=2 第 i +1層半徑和高都為i, Ri = Hi = m i 這樣， 余下的m-i層的最小體積為imkikMIN13因此,剪枝條件為, if Vi當(dāng)前最優(yōu)值當(dāng)前最優(yōu)值 then exi

32、t; 剪枝剪枝1 if Vi MINi then exit; 剪枝剪枝2 if Vi MAXi then exit; 剪枝剪枝3 if im then for Ri + 1 Ri downto ifor Hi + 1min(Vi div (Ri + 1*Ri + 1), Hi) downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) Else if Vi =0 then 更新最優(yōu)值更新最優(yōu)值Problem-Cake

33、1. 計(jì)算計(jì)算MINi和和MAXi R,H ; 2. for R1m to sqrt ( n ) do /*假設(shè)假設(shè) H1=1，只做一層蛋糕，只做一層蛋糕 */ 3. for H1n div (R1*R1) downto m do 4. S1=2 * R1* H1+ R1* R1 5. V1=n - R1* R1 * H1 6. Search (1, R1, H1, S1, V1) 7. 小結(jié)可行性剪枝 剪枝2：if Vi當(dāng)前最優(yōu)值 then exit 剪枝原則 正確、高效深度搜索消耗時(shí)間深度搜索消耗時(shí)間 每個(gè)節(jié)點(diǎn)操作系數(shù)每個(gè)節(jié)點(diǎn)操作系數(shù) 節(jié)點(diǎn)個(gè)數(shù)節(jié)點(diǎn)個(gè)數(shù) 優(yōu)化 1）減少節(jié)點(diǎn)個(gè)數(shù)這就是剪枝優(yōu)化

34、剪枝優(yōu)化； 2）減少每個(gè)節(jié)點(diǎn)的操作系數(shù)即程序操作量程序操作量。例題四對(duì)任意的正整數(shù)N，我們有整數(shù)方程：1X11X21Xn=1,該整數(shù)方程的一個(gè)解集x1,x2,，xn是使整數(shù)方程成立的一組正整數(shù)，例如n,n,n,，n就是一個(gè)解集，在統(tǒng)計(jì)解集時(shí)，把數(shù)據(jù)值相同但順序不一樣的解集認(rèn)為是同一個(gè)解集，例如：當(dāng)n=3時(shí)，我們把2,3,6和3,6,2看為是同一個(gè)解集?，F(xiàn)在的任務(wù)是：對(duì)于一個(gè)給定的n，m ,在最多只允許1個(gè)xi大于m時(shí)，求出整數(shù)方程不同解集的個(gè)數(shù)。(n=20,m=100)分析這道題只能用搜索來(lái)做，每次搜索一個(gè)Xi首先規(guī)定搜索順序：從小到大進(jìn)行搜索，X1=X2=.=Xn，因?yàn)樗阉鞯慕夂晚樞驘o(wú)關(guān)，所

35、以可以這么規(guī)定最優(yōu)性剪枝：因?yàn)橐阉魉薪?，所以無(wú)最優(yōu)性樣例：n=3 m=10 3個(gè)解分析可行性剪枝：假設(shè)當(dāng)前要搜Xi ，而和已經(jīng)是t1/t2 若以后的(n-i+1) 個(gè)數(shù)都取最大值，即1/XI-1 ，也不可能達(dá)到1，則必然是無(wú)解的如果后(n-i+1)個(gè)數(shù)中，最后一個(gè)分?jǐn)?shù)無(wú)窮小，而后(n-i)個(gè)分?jǐn)?shù)都取最小值，即1/m，它們的和也會(huì)大于1，則必然也是無(wú)解的例題五 喬治有一些同樣長(zhǎng)的小木棍，他把這些木棍隨意砍成幾段，直到每段的長(zhǎng)都不超過(guò)50。 現(xiàn)在，他想把小木棍拼接成原來(lái)的樣子，但是卻忘記了自己開(kāi)始時(shí)有多少根木棍和它們的長(zhǎng)度。 給出每段小木棍的長(zhǎng)度，編程幫他找出原始木棍的最小可能長(zhǎng)度。(木棍數(shù)=

36、60)分析題目大意：給出一個(gè)序列，把它們分成組，使得每組和相等，求最大的基本思路：枚舉木棍長(zhǎng)度，再判斷是否可行。也就是說(shuō)先枚舉，再搜索判斷。樣例：5 2 1 5 2 1 5 2 1答案：5,15,15,12,2,2原木棍長(zhǎng)度=6分析枚舉時(shí)，拼出來(lái)的木棍長(zhǎng)度必須符合以下規(guī)則：不能小于原木棍長(zhǎng)度里面最大的，不能大于所有木棍長(zhǎng)度之和，且所有木棍長(zhǎng)度之和mod該長(zhǎng)度=0。枚舉順序：從大到小比較好，因?yàn)榭梢约糁γ杜e剪枝：如果長(zhǎng)度為L(zhǎng)的木棍已經(jīng)判斷為不能拼出來(lái)，那么長(zhǎng)度為L(zhǎng)的約數(shù)的木棍也均不能拼得分析搜索狀態(tài)：哪些木棍用了，哪些木棍沒(méi)用，當(dāng)前拼到第幾根木棍了搜素順序：先用木棍長(zhǎng)度較大的，因?yàn)樗阉鲿r(shí)，假設(shè)當(dāng)

37、前能用長(zhǎng)度為s的木棍去拼（恰能拼出已定長(zhǎng)度），是一定比用s1, s2, s3, , sn這n根長(zhǎng)度較小木棍去拼要優(yōu)的（其中sum(s1, s2, , sn) = s），也就是說(shuō)先用長(zhǎng)度較大的拼更容易得到答案沒(méi)有最優(yōu)性與可行性剪枝例題六n(n=10)個(gè)點(diǎn)的有向完全圖，每條邊都有一個(gè)實(shí)數(shù)權(quán)值，現(xiàn)在我們要找一條長(zhǎng)度為n的路使得路上的邊權(quán)和最接近一個(gè)數(shù)x。注意：每個(gè)點(diǎn)都有自環(huán)。自環(huán)指的是對(duì)于一個(gè)點(diǎn)，存在一條邊，從這個(gè)點(diǎn)出發(fā)，指向這個(gè)點(diǎn)本身。這條路徑允許經(jīng)過(guò)重復(fù)的點(diǎn)和重復(fù)的邊。分析考慮搜索狀態(tài)：將所有的路徑都搜索出來(lái)。狀態(tài)量：當(dāng)n=10時(shí)，狀態(tài)量高達(dá)1010，所以廣搜是不行的。那么考慮進(jìn)行深搜，考慮深搜

38、的剪枝搜索順序（無(wú)關(guān)緊要）可行性剪枝（不行，每條路徑都可行）最優(yōu)性剪枝（有可能）經(jīng)典剪枝（二分法）我們可以將一條路徑分兩次搜索，每次搜一半。先搜出所有的長(zhǎng)度為n/2的路徑，并存下來(lái)，當(dāng)做路徑的前半段。用fij數(shù)組存下所有以i結(jié)尾的長(zhǎng)度為n/2的路徑權(quán)值和，并將j這一維按權(quán)值和排序。即fi1表示所有路徑中權(quán)值和最大的， fi2表示權(quán)值和第二大的，以此類推。然后搜后半段路徑，每搜出一條路徑，若這條路徑以i開(kāi)頭，權(quán)值和為y，則在fi中二分查找一個(gè)離x-y最近的權(quán)值和，構(gòu)成完整的路徑。Noi2001方程的解數(shù)也是用這個(gè)方法。例題七15數(shù)碼問(wèn)題。聯(lián)系8數(shù)碼問(wèn)題，用廣搜來(lái)做，狀態(tài)量太大，有15!種狀態(tài)。所

39、以我們確定要用深搜做。但是深搜做一個(gè)狀態(tài)會(huì)一直搜到最底層，時(shí)間無(wú)法承受。傳統(tǒng)的搜索已經(jīng)無(wú)法適應(yīng)這一道題目了。怎么辦？引入迭代加深算法：從小到大枚舉ans，用深搜判斷ans是否可行。因?yàn)閍ns越小越容易進(jìn)行可行性剪枝。因?yàn)閍ns枚舉出來(lái)了，所以不存在最優(yōu)性剪枝。其實(shí)也可以理解成枚舉ans，更好地進(jìn)行最優(yōu)性剪枝。搜索順序的優(yōu)化就要根據(jù)題目討論了。估價(jià)函數(shù)s問(wèn)題的某種狀態(tài)。h*(s)s到目標(biāo)的實(shí)際最短距離。h(s)s的估價(jià)函數(shù)，表示s到目標(biāo)距離的下界，h(s)=h*(s)，若h函數(shù)是相容的，則還需要滿足h(s1)=ans，則當(dāng)前狀態(tài)舍去，進(jìn)行最優(yōu)性剪枝。本題的估價(jià)函數(shù)考慮到每次移動(dòng)時(shí)除0以外的其他數(shù)

40、最多有一個(gè)向目標(biāo)位置靠近一格。所以h(s)=d(k,k) 1=k=15h(s)滿足兩個(gè)條件h(s)=h*(s)h(s1)=h(s2)+c(s1,s2)A*算法與IDA*算法將估價(jià)函數(shù)運(yùn)用到廣搜的算法稱為A*算法，需用堆來(lái)實(shí)現(xiàn)。A*算法是理論上時(shí)間最優(yōu)的算法，但所需空間太大。為了解決A*算法的空間問(wèn)題，IDA*算法被提出，它是將估價(jià)函數(shù)與迭代加深算法結(jié)合起來(lái)的算法。所以此題用深搜，通過(guò)IDA*算法進(jìn)行優(yōu)化即可。練習(xí)一下：例題八給你一個(gè)1n的任意排列，你需要進(jìn)行最少的操作將它變成從小到大的排列。一次操作是指將排列中的任一段剪貼出來(lái)并粘貼到任意位置。分析這是一道IDA*的練習(xí)題，我們直接分析估計(jì)函數(shù)

41、首先很容易想到h(s)=后繼正確的個(gè)數(shù)。但這樣h(s)并不滿足相容性，考慮到我們一次操作會(huì)改變3個(gè)數(shù)的后繼，所以將h(s)/3即可。綜合運(yùn)用講了這么多道對(duì)于深搜的優(yōu)化， 下面請(qǐng)各位嘗試著想出一些對(duì)下面這道題目的優(yōu)化來(lái)。例題九給你n(n=1000)個(gè)字符串，每個(gè)字符串長(zhǎng)度范圍是511，且都由小寫(xiě)字母組成?，F(xiàn)在告訴你其實(shí)每個(gè)字符串都是一個(gè)數(shù)學(xué)等式（其中只包括+、*、=、0.9），問(wèn)你能否確定每個(gè)字母所表示的是什么。如果能唯一確定，則輸出。例題九樣例輸入：abcdeccdefe樣例輸出：a6b*d=f+分析首先這題根據(jù)分析后可得到搜索量是13!，用廣搜肯定承受不了的，所以我們來(lái)討論深搜加剪枝。由于此

42、題并不存在最優(yōu)值問(wèn)題，所以最優(yōu)性剪枝就不可能了。搜索順序優(yōu)化：我們要先搜索更易剪枝的信息。可行性剪枝：此題約束條件很多。搜索順序=每個(gè)等式中有且僅有一個(gè)，并且不在最左邊和最右邊。*不在最左邊與最右邊且不與=,*相鄰。+不在最左邊與最右邊且不與=,*,+相鄰。0不能出現(xiàn)前導(dǎo)0。19搜完后n個(gè)等式都要滿足。剪枝一估算等式兩邊的最大值與最小值。用0或9取代所有沒(méi)搜出來(lái)的字符。剪枝二若當(dāng)前還未搜索的字母都已確定是多解并且搜過(guò)的字母與當(dāng)前答案一致時(shí)就可以回溯了，沒(méi)必要往下繼續(xù)搜索，因?yàn)樵偎阉饕膊粫?huì)影響結(jié)果。源代碼見(jiàn)目錄下ex7.pas總結(jié)通過(guò)這一次的學(xué)習(xí)，我們可以經(jīng)過(guò)歸納，總結(jié)出分析搜索問(wèn)題的一般步驟，

43、與對(duì)搜索問(wèn)題優(yōu)化的大致方向。分析搜索問(wèn)題的一般步驟根據(jù)題意確定出狀態(tài)，并算出狀態(tài)量若狀態(tài)量不是很大，直接廣搜，用hash表優(yōu)化判重若狀態(tài)量很大，就深搜，可以考慮重新選定狀態(tài)或者進(jìn)行深搜優(yōu)化優(yōu)化廣搜（優(yōu)化空間并不大，所以我們主要討論深搜）用hash表在判重時(shí)優(yōu)化與動(dòng)規(guī)優(yōu)化類似，優(yōu)化狀態(tài)量與轉(zhuǎn)移。深搜搜索順序優(yōu)化最優(yōu)性剪枝可行性剪枝所有優(yōu)化都是以這些為核心的。神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)(NOIP2003-1)在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)稱為神經(jīng)元，而且兩個(gè)神圖，圖中的節(jié)點(diǎn)稱為神經(jīng)元，而且兩個(gè)神經(jīng)元之間至多有一條邊相連，下圖是一個(gè)經(jīng)元之間至多有一條邊相

44、連，下圖是一個(gè)神經(jīng)元的例子神經(jīng)元的例子圖中，圖中，X1X3是信息輸入渠道，是信息輸入渠道，Y1Y2是信息輸出渠道，是信息輸出渠道，C1表示神經(jīng)元目前的狀態(tài)，表示神經(jīng)元目前的狀態(tài)，Ui是閾值，可視為神經(jīng)元的一是閾值，可視為神經(jīng)元的一個(gè)內(nèi)在參數(shù)。個(gè)內(nèi)在參數(shù)。 神經(jīng)元按一定的順序排列，構(gòu)成整個(gè)神經(jīng)網(wǎng)絡(luò)。在蘭蘭神經(jīng)元按一定的順序排列，構(gòu)成整個(gè)神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無(wú)分為幾層；稱為輸入層、的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無(wú)分為幾層；稱為輸入層、輸出層，和若干個(gè)中間層。每層神經(jīng)元只向下一層的神經(jīng)輸出層，和若干個(gè)中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。元輸出

45、信息，只從上一層神經(jīng)元接受信息。 神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)蘭蘭規(guī)定，蘭蘭規(guī)定，Ci服從公式：（其中服從公式：（其中n是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）公式中的公式中的WjiWji（可能為負(fù)值）表示連接（可能為負(fù)值）表示連接j j號(hào)神經(jīng)元和號(hào)神經(jīng)元和 i i號(hào)神經(jīng)元號(hào)神經(jīng)元的邊的權(quán)值。當(dāng)?shù)倪叺臋?quán)值。當(dāng) CiCi大于大于0 0時(shí)，該神經(jīng)元處于興奮狀態(tài)，否則時(shí)，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時(shí)，下一秒它會(huì)向就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時(shí)，下一秒它會(huì)向其他神經(jīng)元傳送信號(hào)，信號(hào)的強(qiáng)度為其他神經(jīng)元傳送信號(hào)，信號(hào)的強(qiáng)度為CiCi。 如此在輸入層如此在輸入層神

46、經(jīng)元被激發(fā)之后，整個(gè)網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿?dòng)下進(jìn)神經(jīng)元被激發(fā)之后，整個(gè)網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿?dòng)下進(jìn)行運(yùn)作?，F(xiàn)在，給定一個(gè)神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的行運(yùn)作?，F(xiàn)在，給定一個(gè)神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)（狀態(tài)（CiCi），要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)。），要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)。 【輸入格式輸入格式】 第一行是兩個(gè)整數(shù)第一行是兩個(gè)整數(shù)n n（1n201n20）和）和p p。接下來(lái)。接下來(lái)n n行，每行兩行，每行兩個(gè)整數(shù)，第個(gè)整數(shù)，第i i1 1行是神經(jīng)元行是神經(jīng)元i i最初狀態(tài)和其閾值（最初狀態(tài)和其閾值（UiUi），非），非輸入層的神經(jīng)元開(kāi)始時(shí)狀態(tài)必然為輸入層

47、的神經(jīng)元開(kāi)始時(shí)狀態(tài)必然為0 0。再下面。再下面P P行，每行由兩行，每行由兩個(gè)整數(shù)個(gè)整數(shù)i i，j j及一個(gè)整數(shù)及一個(gè)整數(shù)WijWij，表示連接神經(jīng)元，表示連接神經(jīng)元i i、j j的邊權(quán)值的邊權(quán)值為為WijWij?！据敵龈袷捷敵龈袷健?輸出包含若干行，每行有兩個(gè)整數(shù)，分別對(duì)應(yīng)一個(gè)神經(jīng)元的輸出包含若干行，每行有兩個(gè)整數(shù)，分別對(duì)應(yīng)一個(gè)神經(jīng)元的編號(hào)，及其最后的狀態(tài)，兩個(gè)整數(shù)間以空格分隔。編號(hào)，及其最后的狀態(tài)，兩個(gè)整數(shù)間以空格分隔。僅輸出最僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號(hào)由小到大順后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號(hào)由小到大順序輸出！序輸出！ 若輸出層的神經(jīng)元最后狀態(tài)均為若輸出

48、層的神經(jīng)元最后狀態(tài)均為 0 0，則輸出，則輸出 NULLNULL。分析理解問(wèn)題的第一步就是認(rèn)真理解問(wèn)題的第一步就是認(rèn)真“讀題讀題”。那么我們。那么我們先來(lái)看一看這個(gè)題目涉及的問(wèn)題。研究一下題目先來(lái)看一看這個(gè)題目涉及的問(wèn)題。研究一下題目中所給的圖的一些性質(zhì)，可以發(fā)現(xiàn)如下特點(diǎn)：中所給的圖的一些性質(zhì)，可以發(fā)現(xiàn)如下特點(diǎn)：1 1圖中所有的節(jié)點(diǎn)都有一個(gè)確定的等級(jí)，我們記圖中所有的節(jié)點(diǎn)都有一個(gè)確定的等級(jí)，我們記作作Level(iLevel(i) )2 2圖中所有的邊都是有向的，并且從圖中所有的邊都是有向的，并且從LevelLevel值為值為i-1i-1的節(jié)點(diǎn)指向的節(jié)點(diǎn)指向LevelLevel值為值為i i的

49、節(jié)點(diǎn)的節(jié)點(diǎn) 我們不妨將其抽象為我們不妨將其抽象為“階段圖階段圖”。更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向無(wú)環(huán)的，這樣我們可以通過(guò)拓?fù)渑判騺?lái)得到期望無(wú)環(huán)的，這樣我們可以通過(guò)拓?fù)渑判騺?lái)得到期望的處理節(jié)點(diǎn)的順序。的處理節(jié)點(diǎn)的順序?？尚兴惴ㄓ捎陔A段圖的性質(zhì)使得該圖的所有邊所連接節(jié)點(diǎn)的等級(jí)都由于階段圖的性質(zhì)使得該圖的所有邊所連接節(jié)點(diǎn)的等級(jí)都是相鄰的，因此就可以設(shè)計(jì)出一個(gè)基于寬度優(yōu)先搜索（即是相鄰的，因此就可以設(shè)計(jì)出一個(gè)基于寬度優(yōu)先搜索（即BFSBFS）的算法：）的算法：1 1初始時(shí)將所有輸入層的節(jié)點(diǎn)放入隊(duì)列；初始時(shí)將所有輸入層的節(jié)點(diǎn)放入隊(duì)列；2 2取出隊(duì)列中

50、的一個(gè)元素，不重復(fù)地?cái)U(kuò)展并處理該節(jié)點(diǎn)所發(fā)出的邊取出隊(duì)列中的一個(gè)元素，不重復(fù)地?cái)U(kuò)展并處理該節(jié)點(diǎn)所發(fā)出的邊的目標(biāo)節(jié)點(diǎn)；的目標(biāo)節(jié)點(diǎn)；3 3如果隊(duì)列非空，則轉(zhuǎn)向如果隊(duì)列非空，則轉(zhuǎn)向2 2；4 4輸出輸出層中所有滿足條件的節(jié)點(diǎn)。輸出輸出層中所有滿足條件的節(jié)點(diǎn)。但是由于本題在問(wèn)題描述中并沒(méi)有明確的給出判斷一個(gè)節(jié)但是由于本題在問(wèn)題描述中并沒(méi)有明確的給出判斷一個(gè)節(jié)點(diǎn)是否是輸入節(jié)點(diǎn)，因此需要在算法進(jìn)行的過(guò)程當(dāng)中額外點(diǎn)是否是輸入節(jié)點(diǎn)，因此需要在算法進(jìn)行的過(guò)程當(dāng)中額外地考慮一些邊界情況的數(shù)據(jù)（這個(gè)過(guò)程即便是真實(shí)數(shù)據(jù)沒(méi)地考慮一些邊界情況的數(shù)據(jù)（這個(gè)過(guò)程即便是真實(shí)數(shù)據(jù)沒(méi)有這樣出也是要有的），下面給出的更一般的算法可能會(huì)

51、有這樣出也是要有的），下面給出的更一般的算法可能會(huì)更好的跳過(guò)這些邊界情況。更好的跳過(guò)這些邊界情況。1 1對(duì)原圖中所有的節(jié)點(diǎn)進(jìn)行一次拓?fù)渑判?；?duì)原圖中所有的節(jié)點(diǎn)進(jìn)行一次拓?fù)渑判颍? 2按照拓?fù)漤樞蛱幚砻恳粋€(gè)節(jié)點(diǎn)；按照拓?fù)漤樞蛱幚砻恳粋€(gè)節(jié)點(diǎn)；3 3輸出輸出層中所有滿足條件的節(jié)點(diǎn)。輸出輸出層中所有滿足條件的節(jié)點(diǎn)。蟲(chóng)食算蟲(chóng)食算(NOIP2004-4)【問(wèn)題描述】 所謂蟲(chóng)食算，就是原先的算式中有一部分被蟲(chóng)子啃掉了，需要我們根據(jù)剩下的數(shù)字來(lái)判定被啃掉的字母。來(lái)看一個(gè)簡(jiǎn)單的例子： 43#9865#045 + 8468#6633 44445506978 其中#號(hào)代表被蟲(chóng)子啃掉的數(shù)字。根據(jù)算式，我們很容易判斷：

52、第一行的兩個(gè)數(shù)字分別是5和3，第二行的數(shù)字是5?，F(xiàn)在，我們對(duì)問(wèn)題做兩個(gè)限制： 首先，我們只考慮加法的蟲(chóng)食算。這里的加法是N進(jìn)制加法，算式中三個(gè)數(shù)都有N位，允許有前導(dǎo)的0。 其次，蟲(chóng)子把所有的數(shù)都啃光了，我們只知道哪些數(shù)字是相同的，我們將相同的數(shù)字用相同的字母表示，不同的數(shù)字用不同的字母表示。如果這個(gè)算式是N進(jìn)制的，我們就取英文字母表午的前N個(gè)大寫(xiě)字母來(lái)表示這個(gè)算式中的0到N-1這N個(gè)不同的數(shù)字：但是這N個(gè)字母并不一定順序地代表0到N-1)。輸入數(shù)據(jù)保證N個(gè)字母分別至少出現(xiàn)一次。 BADC + CRDA DCCC 上面的算式是一個(gè)4進(jìn)制的算式。很顯然，我們只要讓ABCD分別代表0123，便可以讓

53、這個(gè)式子成立了。你的任務(wù)是，對(duì)于給定的N進(jìn)制加法算式，求出N個(gè)不同的字母分別代表的數(shù)字，使得該加法算式成立。輸入數(shù)據(jù)保證有且僅有一組解，【輸入文件】 輸入文件alpha.in包含4行。第一行有一個(gè)正整數(shù)N(N=26)，后面的3行每行有一個(gè)由大寫(xiě)字母組成的字符串，分別代表兩個(gè)加數(shù)以及和。這3個(gè)字符串左右兩端都沒(méi)有空格，從高位到低位，并且恰好有N位?！据敵鑫募?輸出文件alpha.out包含一行。在這一行中，應(yīng)當(dāng)包含唯一的那組解。解是這樣表示的：輸出N個(gè)數(shù)字，分別表示A，B，C所代表的數(shù)字，相鄰的兩個(gè)數(shù)字用一個(gè)空格隔開(kāi)，不能有多余的空格。樣例：【樣例輸入】5ABCEDBDACEEBBAA【樣例輸

54、出】1 0 3 4 2【數(shù)據(jù)規(guī)?！繉?duì)于30的數(shù)據(jù)，保證有N10；對(duì)于50的數(shù)據(jù)，保證有N15；對(duì)于全部的數(shù)據(jù)，保證有N26。 解決方案解決方案1要求一一對(duì)應(yīng)的關(guān)系，就可以枚舉要求一一對(duì)應(yīng)的關(guān)系，就可以枚舉這些一一對(duì)應(yīng)的關(guān)系，找出符合的這些一一對(duì)應(yīng)的關(guān)系，找出符合的一項(xiàng)。這樣，關(guān)系總數(shù)有一項(xiàng)。這樣，關(guān)系總數(shù)有O(N!)個(gè)個(gè)，最壞情況下必須枚舉所有的關(guān)系，最壞情況下必須枚舉所有的關(guān)系，并且加以判斷，復(fù)雜度高達(dá)，并且加以判斷，復(fù)雜度高達(dá)O(N*N!)！解決方案解決方案2:大體上，從算式最后一位開(kāi)始模擬運(yùn)算情況，當(dāng)可遞推時(shí)遞推，不可遞大體上，從算式最后一位開(kāi)始模擬運(yùn)算情況，當(dāng)可遞推時(shí)遞推，不可遞推則枚

55、舉。推則枚舉。對(duì)于一豎列，先處理兩個(gè)加數(shù)，當(dāng)遇到的字母的值不確定時(shí)，則枚舉當(dāng)對(duì)于一豎列，先處理兩個(gè)加數(shù)，當(dāng)遇到的字母的值不確定時(shí)，則枚舉當(dāng)前位（注意與前面的情況判重）；否則不作為處理和，當(dāng)遇到的字母的前位（注意與前面的情況判重）；否則不作為處理和，當(dāng)遇到的字母的值不確定時(shí)值不確定時(shí),可從加數(shù)部分確定的值來(lái)確定（注意與前面的情況判重和進(jìn)可從加數(shù)部分確定的值來(lái)確定（注意與前面的情況判重和進(jìn)位）；否則看加數(shù)部分確定的值是否能得到和部分（注意進(jìn)位）。引出位）；否則看加數(shù)部分確定的值是否能得到和部分（注意進(jìn)位）。引出矛盾就回溯。矛盾就回溯。如題目的樣例：如題目的樣例：5ABCEDBDACEEBBAA它最

56、后一位的情況是它最后一位的情況是(D+E) mod N=A, 對(duì)于最后一位只要枚舉對(duì)于最后一位只要枚舉D,E的情況；的情況；A 則可以由則可以由D,E的值遞推而來(lái)。對(duì)于倒的值遞推而來(lái)。對(duì)于倒2位位, (E+C+最后一位進(jìn)位最后一位進(jìn)位) mod N=A ；E的值可以用前面的結(jié)果；枚舉的值可以用前面的結(jié)果；枚舉C；判斷；判斷A是否為是否為(D+C+最后一位最后一位進(jìn)位進(jìn)位) mod N雖然復(fù)雜度還是雖然復(fù)雜度還是O(N!)，但這種方法限制很多（相當(dāng)于剪枝）。，但這種方法限制很多（相當(dāng)于剪枝）。 解決方案解決方案3觀察題目的條件已經(jīng)限制得很苛刻：觀察題目的條件已經(jīng)限制得很苛刻：N個(gè)變量，個(gè)變量，每

57、個(gè)至少出現(xiàn)一次；而且正好一共有每個(gè)至少出現(xiàn)一次；而且正好一共有N位的算式。位的算式。這樣就構(gòu)成了解方程的動(dòng)機(jī)。這這樣就構(gòu)成了解方程的動(dòng)機(jī)。這N個(gè)變量的對(duì)應(yīng)個(gè)變量的對(duì)應(yīng)N個(gè)未知量，有個(gè)未知量，有N位的算式對(duì)應(yīng)位的算式對(duì)應(yīng)N個(gè)方程；個(gè)方程；N個(gè)未知個(gè)未知量，量，N個(gè)方程，正好可以得到唯一解。這里要注個(gè)方程，正好可以得到唯一解。這里要注意，對(duì)解的要求很嚴(yán)格：必須是意，對(duì)解的要求很嚴(yán)格：必須是0至至N-1的每個(gè)整的每個(gè)整數(shù)都正好出現(xiàn)一次。數(shù)都正好出現(xiàn)一次。但對(duì)每位式子的進(jìn)位關(guān)系并不清楚，而進(jìn)位關(guān)但對(duì)每位式子的進(jìn)位關(guān)系并不清楚，而進(jìn)位關(guān)系正好影響了方程的常數(shù)項(xiàng)。枚舉每位是否進(jìn)位。系正好影響了方程的常數(shù)項(xiàng)

58、。枚舉每位是否進(jìn)位。用時(shí)用時(shí)O(2n), (因?yàn)槭孜徊豢赡苓M(jìn)位，無(wú)須枚舉因?yàn)槭孜徊豢赡苓M(jìn)位，無(wú)須枚舉)。然后，用高斯消元法來(lái)解方程?？梢栽诿杜e之前然后，用高斯消元法來(lái)解方程?？梢栽诿杜e之前先解出方程，枚舉的時(shí)候再把參數(shù)帶入。帶入求先解出方程，枚舉的時(shí)候再把參數(shù)帶入。帶入求解的復(fù)雜度是解的復(fù)雜度是O(n2) 。解決方案解決方案4在解決方案在解決方案3的基礎(chǔ)上，我們可以對(duì)進(jìn)位的枚舉剪的基礎(chǔ)上，我們可以對(duì)進(jìn)位的枚舉剪枝。觀察這個(gè)豎列：枝。觀察這個(gè)豎列：A+B=C，若無(wú)進(jìn)位則有，若無(wú)進(jìn)位則有A=C且且BC且且B=C.若能推導(dǎo)出若能推導(dǎo)出A=A （A,B為任何不相等為任何不相等字母），則當(dāng)前的枚舉不可行

59、?？捎眠f歸枚舉，從字母），則當(dāng)前的枚舉不可行?？捎眠f歸枚舉，從后向前枚舉，處理一個(gè)豎列時(shí)則加上后向前枚舉，處理一個(gè)豎列時(shí)則加上2個(gè)不等式，個(gè)不等式，看是否矛盾。數(shù)據(jù)結(jié)構(gòu)用鄰接矩陣。（規(guī)定看是否矛盾。數(shù)據(jù)結(jié)構(gòu)用鄰接矩陣。（規(guī)定A=B，再有向圖中有邊再有向圖中有邊）。）。若加進(jìn)不等式若加進(jìn)不等式A=B ，要加入所有，要加入所有x(x=A) =y(B=y)，枚舉，枚舉x,y用用O(n2)得時(shí)間。再判斷是得時(shí)間。再判斷是否有否有x=y.傳染病控制傳染病控制 (NOIP2003-4)染病的傳播具有兩種很特殊的性質(zhì)：染病的傳播具有兩種很特殊的性質(zhì)： 第一是它的傳播途徑是樹(shù)型的，一個(gè)人第一是它的傳播途徑是樹(shù)型的，一個(gè)人X X只可能被某個(gè)特定只可能被某個(gè)特定的人的人Y Y感染，只要感染，只要Y Y不得病，或者是不得病，或者是XYXY之間的傳播途徑被切斷，之間的傳播途徑被切斷，則則X X就不會(huì)得病。第二是，這種疾病的傳播有周期性，在一個(gè)就不會(huì)得病。第二是，這種疾病的傳播有周期性，在一個(gè)疾病傳播周期之內(nèi)，傳染病將只會(huì)感染一代患者，而不會(huì)再疾病傳播周期之內(nèi)，傳染病將只會(huì)感染一代患者，而不會(huì)再傳播給下一代。傳播給下一代。 這些性質(zhì)大大減輕了蓬萊國(guó)疾病防控的壓力，并且他們已經(jīng)這些性質(zhì)大大減輕了蓬萊國(guó)疾病防控的壓力，并且他們已經(jīng)得到了國(guó)內(nèi)部分易感人群的潛在傳播途徑圖（一棵樹(shù)）。但得到了國(guó)