羅馬尼亞問(wèn)題_第1頁(yè)
羅馬尼亞問(wèn)題_第2頁(yè)
羅馬尼亞問(wèn)題_第3頁(yè)
羅馬尼亞問(wèn)題_第4頁(yè)
羅馬尼亞問(wèn)題_第5頁(yè)
已閱讀5頁(yè),還剩11頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、羅馬尼亞問(wèn)題、問(wèn)題描述(1)羅馬尼亞問(wèn)題:Find Bucharest starting at Arad分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和A*算法求解“羅馬利亞度假問(wèn) 題”。要求:分別用文件存儲(chǔ)地圖和啟發(fā)函數(shù)表,用生成節(jié)點(diǎn)數(shù)比較幾種算 法在問(wèn)題求解時(shí)的效率,列表給出結(jié)果。(3)附各結(jié)點(diǎn)啟發(fā)值:366 241 0 234 160 380 242 100 161 193 176 253 77 329 151 80 226 199244 374 二、數(shù)據(jù)結(jié)構(gòu)1、邏輯結(jié)構(gòu):用到線性結(jié)構(gòu)包括數(shù)組、鏈表、棧;非線性結(jié)構(gòu):圖。2、存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu)):順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)啟發(fā)函數(shù)表采用順序存儲(chǔ)結(jié)構(gòu)數(shù)

2、組data20.存儲(chǔ),從文件中讀入:for (n=0;n20;n+)(fscanf(fp1,d,&datan);圖采用二維數(shù)組map 口存儲(chǔ),從文件中讀入:for (i=0;i20;i+)(for(j=0;j20;j+)(fscanf(fp2,%d,&mapij);(3)寬度優(yōu)先的fringe表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ),且每一個(gè)結(jié)點(diǎn)為一個(gè)包含結(jié) 點(diǎn)序號(hào)、h、g、f值等的結(jié)構(gòu)體;(4)深度優(yōu)先的fringe表采用順序棧存儲(chǔ),且每一個(gè)結(jié)點(diǎn)為一個(gè)包含結(jié)點(diǎn)序號(hào)、 h、g、f值等的結(jié)構(gòu)體;(5)貪婪算法和A*算法采用結(jié)構(gòu)體數(shù)組存儲(chǔ)。3、數(shù)據(jù)的運(yùn)算:抽象數(shù)據(jù)類型(1)定義typedef struct frin

3、ge(int state;/存儲(chǔ)點(diǎn)序號(hào)信息int g;/g 值int h;/h 值int f;/f 值int k;/標(biāo)記是否已擴(kuò)展FringeType;(2)運(yùn)算:檢索、插入、刪除等運(yùn)算(3)表示:每一個(gè)數(shù)據(jù)元素就是一個(gè)記錄。它包括學(xué)生的結(jié)點(diǎn)序號(hào)信息、g值、h 值、f值等數(shù)據(jù)項(xiàng),在解決實(shí)際應(yīng)用問(wèn)題時(shí)把每個(gè)記錄當(dāng)作一個(gè)基本單位進(jìn)行訪 問(wèn)和處理。三、算法思想1、寬度優(yōu)先(1)算法描述:從Arad結(jié)點(diǎn)出發(fā),判斷是否為目標(biāo)結(jié)點(diǎn),若否,寬度優(yōu)先搜索系統(tǒng)地探尋與該結(jié)點(diǎn)相連的結(jié)點(diǎn),算法首先搜索和Arad距離為k的所有頂點(diǎn),然后再去搜索和Arad距離為k+l的其他頂點(diǎn),找出并存進(jìn)待擴(kuò)展結(jié)點(diǎn)表,等 待擴(kuò)展,每次

4、先判斷待擴(kuò)展結(jié)點(diǎn)表是否為空,若否則從待擴(kuò)展結(jié)點(diǎn)表中取 出一個(gè)結(jié)點(diǎn)進(jìn)行擴(kuò)展,并將擴(kuò)展后的結(jié)點(diǎn)存進(jìn)該表,若是,則返回失敗。該算法同時(shí)能生成一棵根為Arad且包括所有可達(dá)頂點(diǎn)的寬度優(yōu)先樹(shù)。寬度優(yōu)先算法一直通過(guò)已找到和未找到頂點(diǎn)之間的邊界向外擴(kuò)展。通 過(guò)為每個(gè)頂點(diǎn)著色(白色、灰色和黑色)。算法開(kāi)始前所有頂點(diǎn)都是白色, 隨著搜索的進(jìn)行,各頂點(diǎn)會(huì)逐漸被著色。在搜索中第一次碰到,著灰色, 然后是灰色。因此,灰色和黑色頂點(diǎn)都已被發(fā)現(xiàn),灰色頂點(diǎn)與一些白色頂 點(diǎn)相鄰接,它們代表著已找到和未找到頂點(diǎn)之間的邊界。在寬度優(yōu)先搜索中,我用到單鏈表來(lái)存儲(chǔ)待擴(kuò)展結(jié)點(diǎn)表。偽代碼實(shí)現(xiàn):while(fringe!=NULL)tak

5、e out uE fringe口docolor u;while(u豐 goal)doexpand u;BFS()(for (1-20 循環(huán))(if (有路徑存在)(新生成結(jié)點(diǎn);BFSnode+;取鏈表的第一個(gè)結(jié)點(diǎn);if (為 goal)( return BFSnode;else if(不為 goal)(BFS (); /遞歸調(diào)用return BFSnode; put successors (BFS) in fringe;end;end;算法評(píng)價(jià):寬度優(yōu)先是完備的(如果分支因子有限的話),所以說(shuō),在任何情況下寬度 優(yōu)先都能找到一個(gè)解。此外,最壞的情況是,當(dāng)目標(biāo)結(jié)點(diǎn)是第d層的最后一個(gè)被 擴(kuò)展的結(jié)點(diǎn)

6、時(shí)。時(shí)間復(fù)雜度:A - *頃- k T打一 -司二。打一 .)(b為分支因子,d為深 度)空間復(fù)雜度:所存儲(chǔ)的節(jié)點(diǎn)的個(gè)數(shù)。2、深度優(yōu)先(1)算法描述:深度優(yōu)先搜索是一種每次都要達(dá)到被搜索結(jié)構(gòu)的葉結(jié)點(diǎn)的搜索方法,直到不能 再深入為止,然后返回到另一個(gè)結(jié)點(diǎn),繼續(xù)對(duì)該結(jié)點(diǎn)進(jìn)行深搜。當(dāng)有目標(biāo)結(jié)點(diǎn)出現(xiàn) 時(shí),返回目標(biāo)結(jié)點(diǎn),搜索結(jié)束;否則,若待擴(kuò)展結(jié)點(diǎn)表已空,且未找到目標(biāo)結(jié)點(diǎn), 則返回失敗,停止搜索。同樣,深度優(yōu)先搜索從Arad結(jié)點(diǎn)出發(fā),判斷是否為目標(biāo)結(jié)點(diǎn),若否,探 尋與該結(jié)點(diǎn)相連的結(jié)點(diǎn),算法首先搜索一條分支上的所有頂點(diǎn),然后再去 搜索和Arad的其它分支結(jié)點(diǎn),找出并存進(jìn)待擴(kuò)展結(jié)點(diǎn)表,等待擴(kuò)展,每次 先判斷

7、待擴(kuò)展結(jié)點(diǎn)表是否為空,若否,則從待擴(kuò)展結(jié)點(diǎn)表中取出一個(gè)結(jié)點(diǎn) 進(jìn)行擴(kuò)展,并將擴(kuò)展后的結(jié)點(diǎn)存進(jìn)該表,若是,則返回失敗。該算法同時(shí) 能生成一棵根為Arad且包括所有可達(dá)頂點(diǎn)的深度優(yōu)先樹(shù)。在深度優(yōu)先搜索中,我用到堆棧來(lái)存儲(chǔ)待擴(kuò)展結(jié)點(diǎn)表。(2)偽代碼實(shí)現(xiàn)while(fringe!=NULL)take out uE fringe口docolor u;while(u尹goal)doexpand u;DFS()for (1-20 循環(huán))if (有路徑存在)新生成結(jié)點(diǎn);DFSnode+;出堆棧;if (是目標(biāo)結(jié)點(diǎn))(return DFSnode; else(DFS (); /遞歸調(diào)用return DFSnode

8、;put successors (DFS) in fringe;end;end;(3)算法評(píng)價(jià):不是完備的(除非查找空間是有限的)。同時(shí),也不能找到最優(yōu)解。時(shí)間復(fù)雜度:空間復(fù)雜度:OEs-I)(b為分支因子,m為深度,僅有一枝需要存儲(chǔ))3、貪婪算法(1)算法描述:貪婪算法是指,在對(duì)問(wèn)題求解時(shí),總是做出在當(dāng)前看來(lái)是最好的選擇。貪婪 算法不從整體最優(yōu)上加以考慮,所做出的僅是在某種意義上的局部最優(yōu)解。貪婪 算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解,但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn) 生整體最優(yōu)解或者是整體最優(yōu)解的近似解。在解決羅馬尼亞度假問(wèn)題時(shí),貪婪算法通過(guò)比較每個(gè)待擴(kuò)展結(jié)點(diǎn)的h值,即啟 發(fā)函數(shù)生成的到目

9、標(biāo)結(jié)點(diǎn)的啟發(fā)函數(shù)值,選取一個(gè)最小的,來(lái)確定當(dāng)前要擴(kuò)展的結(jié) 點(diǎn),并將生成的結(jié)點(diǎn)放進(jìn)fringe結(jié)點(diǎn)表。在貪婪算法中,我用到結(jié)構(gòu)體數(shù)組存儲(chǔ)待擴(kuò)展結(jié)點(diǎn)表。(2)偽代碼實(shí)現(xiàn):while(fringe!=NULL)take out uE fringe口docolor u;while(u豐 goal)doexpand u;greedy ()( for (1-20 循環(huán))if (有路徑)新生成結(jié)點(diǎn)IGNode+;for (循環(huán))if (比較h值大?。┱页鲎钚〉膆值結(jié)點(diǎn); if (離目標(biāo)的實(shí)際值! =0)greedy (); /遞歸調(diào)用return GNode;/生成結(jié)點(diǎn)數(shù)put successors ( g

10、reedy) in fringe;end;end;(3)算法評(píng)價(jià)不是完備的。同時(shí),找到的解也不一定是最優(yōu)解。時(shí)間復(fù)雜度:頊)(b代表分支數(shù),m為深度)空間復(fù)雜度:)4、A*算法(1)算法描述:A*算法用公式表示為:f(n)=g(n)+h(n),其中f(n)是從初始點(diǎn)經(jīng)由結(jié) 點(diǎn)n到目標(biāo)點(diǎn)的估價(jià)函數(shù);g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí) 際代價(jià),h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。A*能找到最優(yōu)解的條件,關(guān)鍵在于估價(jià)函數(shù)h(n)的選?。蝗艄纼r(jià)值實(shí)際值,則能保證得到最優(yōu)解。(2)偽代碼實(shí)現(xiàn):while(fringe!=NULL)take out uE fringe口docolor u

11、;while(u尹goal)doexpand u;Astar ()for (循環(huán))if (有路徑存在0)新生成結(jié)點(diǎn);ASNode+;for (循環(huán))if (f值比min?。┱页鲎頵值最小的結(jié)點(diǎn)擴(kuò)展for (循環(huán))if (為目標(biāo)結(jié)點(diǎn))return ASNode;Sstar (); /遞歸調(diào)用return ASNode;put successors (Astar ) in fringe口;end;end;算法評(píng)價(jià):完備的,能夠找到最優(yōu)解;時(shí)間復(fù)雜度:擴(kuò)展節(jié)點(diǎn)的數(shù)目;空間復(fù)雜度:所有生成的結(jié)點(diǎn)。四、運(yùn)行結(jié)果:寬度優(yōu)先、深度優(yōu)先、貪婪算法、 A*算法:五、比較結(jié)論:通過(guò)比較,DFS和Greedy搜索生

12、成的結(jié)點(diǎn)數(shù)目最少,為9個(gè),效率最 高;BFS生成的結(jié)點(diǎn)數(shù)目最多,為19個(gè),效率最低。但是 DFS、BFS和 Greedy搜索找到的都不一定最優(yōu)解,只有A*算法具有完備性且始終找到的 都是最優(yōu)解。寬度優(yōu)先雖然是完備的(如果分支因子有限的話),在任何情況 下寬度優(yōu)先都能找到一個(gè)解,但是,它找到的第一個(gè)解并非最優(yōu)的,此外,最壞 的情況是,當(dāng)目標(biāo)結(jié)點(diǎn)是第d層的最后一個(gè)被擴(kuò)展的結(jié)點(diǎn)時(shí),它將耗費(fèi)大量的時(shí)間。寬度優(yōu)先時(shí)間復(fù)雜度:b-m -n二至(b為分支因 子,d為深度);空間復(fù)雜度為所存儲(chǔ)的節(jié)點(diǎn)的個(gè)數(shù)。DFS不是完備的(除非查 找空間是有限的),同時(shí),它也不能找到最優(yōu)解。深度優(yōu)先的時(shí)間復(fù)雜度:一 : |

13、; 空間復(fù)雜度:Cl (b為分支因子,m為深度,僅有一枝需要存儲(chǔ))。貪 婪算法不是完備的。同時(shí),它找到的解也不一定是最優(yōu)解。其時(shí)間復(fù)雜度:* :1(b代表分支數(shù),m為深度);空間復(fù)雜度為)。所以只有A*算法是完備 的,且能夠找到最優(yōu)解;其時(shí)間復(fù)雜度:擴(kuò)展節(jié)點(diǎn)的數(shù)目;空間復(fù)雜度:所有 生成的結(jié)點(diǎn)。綜合來(lái)看,DFS和貪婪算法的效率較高,但解并非最優(yōu),而A*算法 的效率稍遜色,但解為最優(yōu);而B(niǎo)FS搜索則效率最低,且不一定為最優(yōu)解。n皇后問(wèn)題一、問(wèn)題描述:(1)n皇后問(wèn)題:在n*n格的國(guó)際象棋上擺放n個(gè)皇后,使其不能互相攻擊, 即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上,(2)分別用回溯法(遞

14、歸)、爬山法和GA算法求解n皇后問(wèn)題。要求:輸入 n,并用運(yùn)行時(shí)間比較幾種算法在相同規(guī)模的問(wèn)題時(shí)的求解效率。列表給出結(jié)果。二、數(shù)據(jù)結(jié)構(gòu)1、邏輯結(jié)構(gòu):用到線性結(jié)構(gòu)包括數(shù)組queenListcol等。2、存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu)):順序存儲(chǔ)結(jié)構(gòu)。3、 數(shù)據(jù)的運(yùn)算:一(1)表示:(queenListcol,co 1)表示 (row,col)的皇后(2)運(yùn)算:檢索、插入、刪除等運(yùn)算三、算法思想:1、回溯法(1)算法描述:回溯法是一種選優(yōu)搜索法,按選優(yōu)條件向前搜索,以達(dá)到目標(biāo)。但當(dāng)探索到 某一步時(shí),發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo),就退回一步重新選擇,這種走不 通就退回再走的技術(shù)為回溯法。(2)偽代碼實(shí)現(xiàn):基本

15、思想是:從一條路往前走,能進(jìn)則進(jìn),不能進(jìn)則退回來(lái),換一條路 再試。對(duì)于n皇后問(wèn)題,第一步按照順序放一個(gè)皇后,然后第二步符合要 求放第2個(gè)皇后,如果沒(méi)有符合位置符合要求,那么就要改變第一個(gè)皇后 的位置,重新放第2個(gè)皇后的位置,直到找到符合條件的位置就可以了, 在目標(biāo)狀態(tài)終止。(3 )算法評(píng)價(jià)回溯法在皇后數(shù)目較小的,很占優(yōu)勢(shì),它的速度非常的快,但隨著皇后 數(shù)目的增加,回溯法顯得很不實(shí)用,在 n=28時(shí),用回溯法已不能較好的解 決n皇后問(wèn)題。2、爬山法(1)算法描述:爬山法是指從當(dāng)前的節(jié)點(diǎn)開(kāi)始,和周圍的鄰居節(jié)點(diǎn)的值進(jìn)行比較。如果當(dāng) 前節(jié)點(diǎn)是最大的,那么返回當(dāng)前節(jié)點(diǎn),作為最大值(既山峰最高點(diǎn));反之就

16、用最 高的鄰居節(jié)點(diǎn)來(lái),替換當(dāng)前節(jié)點(diǎn),從而實(shí)現(xiàn)向山峰的高處攀爬的目的。如此循環(huán) 直到達(dá)到最高點(diǎn)。每次都選擇是與目標(biāo)結(jié)點(diǎn)啟發(fā)函數(shù)值最小的那個(gè)結(jié)點(diǎn),經(jīng)過(guò)迂回前進(jìn),最終達(dá) 到解決問(wèn)題的總目標(biāo)。如果我們把目標(biāo)函數(shù)的幾何圖形看成一個(gè)山峰,那么點(diǎn)的 直接移動(dòng)就像人在爬山,選擇方向,逐步向山頂移動(dòng)。爬山法需要建立一個(gè)描述數(shù) 據(jù)庫(kù)變化的單極值函數(shù),且使極值對(duì)應(yīng)目標(biāo)狀態(tài);選取使函數(shù)值增長(zhǎng)最大的那條規(guī)則 作用于數(shù)據(jù)庫(kù);重復(fù)上步,直到?jīng)]有規(guī)則使函數(shù)值繼續(xù)增長(zhǎng)。爬山法是一種局部搜索算法,也屬一種啟發(fā)式方法。但它一般只能得到局部 最優(yōu),并且這種解還依賴于起始點(diǎn)的選取。它是一種解多變量無(wú)約束最優(yōu)化問(wèn)題 的一類方法,通過(guò)點(diǎn)的

17、直接移動(dòng)產(chǎn)生的目標(biāo)值有所改善的點(diǎn),經(jīng)過(guò)這樣的移動(dòng),逐 步到達(dá)使目標(biāo)函數(shù)最優(yōu)的點(diǎn)。在爬山法中,h表示相互攻擊的皇后的對(duì)數(shù),用它來(lái)生成啟發(fā)函數(shù)。(2)偽代碼實(shí)現(xiàn):爬山函數(shù)(問(wèn)題)是局部極大值的一種狀態(tài)返回輸入問(wèn)題,一個(gè)問(wèn)題局部變量:當(dāng)前,一個(gè)節(jié)點(diǎn)。鄰居,一個(gè)節(jié)點(diǎn)。當(dāng)前生成節(jié)點(diǎn)(初始狀態(tài)問(wèn)題) 循環(huán)做鄰居 一個(gè)價(jià)值最高當(dāng)前的繼任者如果值鄰居W價(jià)值當(dāng)前,然后返回狀態(tài)當(dāng)前 當(dāng)前鄰居(3 )算法評(píng)價(jià)爬山法的缺點(diǎn):會(huì)出現(xiàn)山脊、高原,86%的時(shí)間會(huì)卡??;但是爬山算法較 簡(jiǎn)單,在皇后的個(gè)數(shù)較多時(shí)體現(xiàn)出來(lái)效率最高,處理多約束大規(guī)模問(wèn)題時(shí)往往不 能得到較好的解。3、遺傳算法(1)算法描述:遺傳算法(Genetic

18、Algorithm)是模擬物進(jìn)化論的自然選擇和遺傳學(xué)機(jī) 理的生物進(jìn)化過(guò)程的計(jì)算模型,是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方 法。對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問(wèn)題,首先初始化,包括種群的大小,編碼 的方案,遺傳的代數(shù),變異的概率,等等;然后進(jìn)行選擇操作;接著是將選擇的 個(gè)體進(jìn)行交叉;然后再進(jìn)行選擇,并將選擇的個(gè)體進(jìn)行變異;最后就是更新最優(yōu) 值了。(2)偽代碼實(shí)現(xiàn):函數(shù)GA (總?cè)?,最適合的FN)返回一個(gè)個(gè)體輸入:人口,個(gè)體最適合的FN,一個(gè)函數(shù),它決定了個(gè)體素質(zhì)循環(huán)新_種群空的集合從1到大?。ㄈ丝冢┳鰅次X 隨機(jī)選擇(人口,最適合的FN)Y 隨機(jī)選擇(人口,最適合的FN)孩子再生(X,Y)(隨機(jī)概率?。敲春⒆?變異(孩子)孩子添加到新_種群人口新_種群直到有個(gè)體適合足夠或足夠的時(shí)間耗完返回最佳個(gè)體大概分為:初始化、選擇運(yùn)算、不停的交叉運(yùn)算、終止計(jì)算。(3)算法評(píng)價(jià)遺傳算法優(yōu)點(diǎn)是能很好的處理約束,能很

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論