羅馬尼亞問題

1、羅馬尼亞問題、問題描述(1)羅馬尼亞問題：Find Bucharest starting at Arad分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和A*算法求解“羅馬利亞度假問 題”。要求：分別用文件存儲地圖和啟發(fā)函數(shù)表，用生成節(jié)點數(shù)比較幾種算 法在問題求解時的效率，列表給出結(jié)果。（3）附各結(jié)點啟發(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、存儲結(jié)構(gòu)(物理結(jié)構(gòu))：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)啟發(fā)函數(shù)表采用順序存儲結(jié)構(gòu)數(shù)

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

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

4、先判斷待擴(kuò)展結(jié)點表是否為空，若否則從待擴(kuò)展結(jié)點表中取 出一個結(jié)點進(jìn)行擴(kuò)展，并將擴(kuò)展后的結(jié)點存進(jìn)該表，若是，則返回失敗。該算法同時能生成一棵根為Arad且包括所有可達(dá)頂點的寬度優(yōu)先樹。寬度優(yōu)先算法一直通過已找到和未找到頂點之間的邊界向外擴(kuò)展。通 過為每個頂點著色（白色、灰色和黑色）。算法開始前所有頂點都是白色， 隨著搜索的進(jìn)行，各頂點會逐漸被著色。在搜索中第一次碰到，著灰色， 然后是灰色。因此，灰色和黑色頂點都已被發(fā)現(xiàn)，灰色頂點與一些白色頂 點相鄰接，它們代表著已找到和未找到頂點之間的邊界。在寬度優(yōu)先搜索中，我用到單鏈表來存儲待擴(kuò)展結(jié)點表。偽代碼實現(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é)點；BFSnode+;取鏈表的第一個結(jié)點；if (為 goal)( return BFSnode;else if(不為 goal)(BFS ()； /遞歸調(diào)用return BFSnode; put successors (BFS) in fringe;end;end;算法評價：寬度優(yōu)先是完備的（如果分支因子有限的話），所以說，在任何情況下寬度 優(yōu)先都能找到一個解。此外，最壞的情況是，當(dāng)目標(biāo)結(jié)點是第d層的最后一個被 擴(kuò)展的結(jié)點

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

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

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

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

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

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

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

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

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

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

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

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

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