從根基點出發(fā)探索解空間樹

在所有解決問題的解算室樹中，根據(jù)深度優(yōu)先搜索戰(zhàn)略，深入挖掘解決方案的結(jié)構(gòu)樹。若用回溯法求問題的所有解時,要回溯到根,且根結(jié)點的所有可行的子樹都要已被搜索遍才結(jié)束。而若使用回溯法求任一個解時,只要搜索到問題的一個解就可以結(jié)束。貪心法它適用于解一些組合數(shù)較大的問題。根據(jù)當(dāng)前已有的信息就做出選擇,而且一旦做出了選擇,不管將來有什么結(jié)果,這個選擇都不會改變。換言之,貪心法并不是從整體最優(yōu)考慮,它所做出的選擇只是在某種意義上的局部最優(yōu)。1繪畫中的問題分類1.1主導(dǎo)快速搜索回溯法是一種系統(tǒng)地搜索問題解的搜索算法。它在包含問題的所有解的解空間樹中,按照深度優(yōu)先的策略,從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時,總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含,則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索,逐層向其祖先結(jié)點回溯。否則,進入該子樹,繼續(xù)按深度優(yōu)先的策略進行搜索。用回溯法解題的一般步驟:(1)描述解的形式,定義一個解空間,它包含問題的所有解。(2)構(gòu)造狀態(tài)空間樹。(3)構(gòu)造約束函數(shù)(用于殺死節(jié)點)。1.2整體最優(yōu)解的選擇貪心算法(又稱貪婪算法)是指,在對問題求解時,總是做出在當(dāng)前看來是最好的選擇。不從整體最優(yōu)上加以考慮,他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解,但對一些問題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法沒有固定的算法框架,算法設(shè)計的關(guān)鍵是貪婪策略的選擇。一定要注意,選擇的貪婪策略要具有無后向性,即某階段狀態(tài)一旦確定以后,不受這個狀態(tài)以后的策略影響,也就是說某個狀態(tài)以后的過程不會影響以前的狀態(tài),只與當(dāng)前狀態(tài)有關(guān),也稱為這種特性為無后效性。因此,適應(yīng)用貪婪策略解決的問題類型較少,對所采用的貪婪策略一定要仔細(xì)分析其是否滿足無后效性。圖的著色問題是由地圖的著色問題引申而來的:用m種顏色為地圖著色,使得地圖上的每一個區(qū)域著一種顏色,且相鄰區(qū)域顏色不同。2處理問題如果把每一個區(qū)域收縮為一個頂點,把相鄰兩個區(qū)域用一條邊相連接,就可以把一個區(qū)域圖抽象為一個平面圖。2.1主導(dǎo)點的提取回溯法有“通用解題法”之稱,是一種比窮舉“聰明”的搜索技術(shù),在搜索過程中動態(tài)地產(chǎn)生問題的解空間,系統(tǒng)地搜索問題的所有解。當(dāng)搜索到解空間樹的任一結(jié)點時,判斷該結(jié)點是否包含問題的解。如果該結(jié)點肯定不包含,則“見壁回頭”,跳過以該結(jié)點為根的子樹的搜索,逐層向其祖先結(jié)點回溯,可大大縮減無效操作,提高搜索效率。因此,結(jié)合具體案例的實際設(shè)計合適的回溯點是應(yīng)用回溯法的關(guān)鍵所在。值得注意的是,遞歸具有回溯的功能,很多問題應(yīng)用遞歸回溯可探索出問題的所有解。2.2較明顯的同位分配算法貪心算法的思想是首先用第一種顏色對圖中盡可能多的頂點著色,然后用第二種顏色對余下的頂點中盡可能多的頂點著色;如此等等,直到把所有的頂點都著完色。當(dāng)用一種新顏色對余下的頂點著色時,我們采取下列步驟:(1)選取某個未著色的頂點,并且用新顏色對它著色。(2)掃描所有未著色的頂點集,對其中的每個頂點,確定它是否與已著新顏色的任何頂點相鄰。若不相鄰,則用新顏色對它著色。首先把所有頂點的顏色初始化為0,然后依次為每個頂點著色。如果其中i個頂點已經(jīng)著色,并且相鄰兩個頂點的顏色都不一樣,就稱當(dāng)前的著色是有效的局部著色;否則,就稱為無效的著色。如果由根節(jié)點到當(dāng)前節(jié)點路徑上的著色,對應(yīng)于一個有效著色,并且路徑的長度小于n,那么相應(yīng)的著色是有效的局部著色。這時,就從當(dāng)前節(jié)點出發(fā),繼續(xù)探索它的兒子節(jié)點,并把兒子結(jié)點標(biāo)記為當(dāng)前結(jié)點。在另一方面,如果在相應(yīng)路徑上搜索不到有效的著色,就把當(dāng)前結(jié)點標(biāo)記為死結(jié)點,并把控制轉(zhuǎn)移去搜索對應(yīng)于另一種顏色的兄弟結(jié)點。如果對所有m個兄弟結(jié)點,都搜索不到一種有效的著色,就回溯到它的父親結(jié)點,并把父親結(jié)點標(biāo)記為死結(jié)點,轉(zhuǎn)移去搜索父親結(jié)點的兄弟結(jié)點。這種搜索過程一直進行,直到根結(jié)點變?yōu)樗澜Y(jié)點,或者搜索路徑長度等于n,并找到了一個有效的著色為止。圖的m色優(yōu)化問題:給定無向連通圖G,為圖G的各頂點著色,使圖中任2鄰接點著不同顏色,問最少需要幾種顏色。所需的最少顏色的數(shù)目m稱為該圖的色數(shù)。4chpowell法在一個平面或球面上的任何地圖能夠只用4種顏色來著色使得相鄰的國家在地圖上著有不同顏色,任意圖的著色,采用的是WelchPowell法。這次實驗主要解決了一個問題,那就是圖著色問題,用兩種不同的方法來解決,分別用回溯法及貪心法。用回溯法求圖著色的時候,固定了