從根基點(diǎn)出發(fā)探索解空間樹(shù)

從根基點(diǎn)出發(fā)探索解空間樹(shù)

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