【正文】 2023年 3月 15日星期三 12時 48分 48秒 00:48:4815 March 2023 1一個人即使已登上頂峰，也仍要自強(qiáng)不息。 2023年 3月 15日星期三 上午 12時 48分 48秒 00:48: 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。勝人者有力，自勝者強(qiáng)。 :48:4800:48Mar2315Mar23 1越是無能的人，越喜歡挑剔別人的錯兒。 , March 15, 2023 閱讀一切好書如同和過去最杰出的人談話。 2023年 3月 15日星期三 12時 48分 48秒 00:48:4815 March 2023 1空山新雨后，天氣晚來秋。 2023年 3月 15日星期三 上午 12時 48分 48秒 00:48: 1楚塞三湘接，荊門九派通。 00:48:4800:48:4800:48Wednesday, March 15, 2023 1不知香積寺，數(shù)里入云峰。 00:48:4800:48:4800:483/15/2023 12:48:48 AM 1成功就是日復(fù)一日那一點(diǎn)點(diǎn)小小努力的積累。 上午 12時 48分 48秒 上午 12時 48分 00:48: 沒有失敗，只有暫時停止成功！。 2023年 3月 上午 12時 48分 :48March 15, 2023 1行動出成果，工作出財富。 :48:4800:48:48March 15, 2023 1他鄉(xiāng)生白發(fā)，舊國見青山。 :48:4800:48Mar2315Mar23 1故人江海別，幾度隔山川。 , March 15, 2023 雨中黃葉樹，燈下白頭人。 開放實(shí)驗(yàn)：不同搜索策略的算法實(shí)現(xiàn)與性能分析 —— 以 8數(shù)碼問題求解為例 ? 摘要 ? 詞匯表 ? 第一章、 8數(shù)碼問題概述 ? 第二章、 x算法的一般描述 ? 第三章、用 x算法分析八數(shù)碼問題 ? （第四章、評價函數(shù)的啟發(fā)能力） ? 第五章、 x算法在 y開發(fā)環(huán)境下的實(shí)現(xiàn)（不限編程語言） ? （ （可參見附錄）） ? ? ? 第六章、性能比較與分析（如廣度優(yōu)先、深度優(yōu)先） ? 第七章、進(jìn)一步討論（改進(jìn)與研究） ? 附錄 ? 參考文獻(xiàn) 要求 ? 編程語言環(huán)境不作要求（ Matlab、 C/C++、Java等均可）； ? 獨(dú)立完成，至少包括一種非啟發(fā)性、一種啟發(fā)性算法； ? 提交最終報告與代碼。 這種算法主要用于人工智能和機(jī)器人技術(shù)。正如當(dāng)我們到另一城市時，可分解為從家里“搜索”一條路徑至車站，再從車站“搜索”一條路徑到另一城市，當(dāng)我們從家里出發(fā)時，需要考慮的是怎樣盡快地到達(dá)車站，而不是怎樣盡快地到另一城市。 ? e. Hierarchical A*。 這種算法從起點(diǎn)和終點(diǎn)同時應(yīng)用 A*算法，直到有結(jié)點(diǎn)相遇。 這種算法是基于這樣的考慮，即在搜索初期以速度優(yōu)先，在搜索后期以準(zhǔn)確度優(yōu)先 (這可通過對搜索初、后期賦予不同的權(quán)值來實(shí)現(xiàn) )。這其實(shí)是一種博奕算法的變形。 ? b. Iterative deepening。 改進(jìn)的 A*算法 ? a. Beam Search。 ? if( cross0 ) cross = cross。 ? double dy2 = startY goalY。 ? double dy1 = currentY goalY。 ? a. Manhattan Distance， 這是一種標(biāo)準(zhǔn)的估價函數(shù)， h(A) = 10 * (abs() + abs()) ? b. Diagonal Distance， 如果在地圖上允許作斜線方向的運(yùn)動，則 Mahattan Distance修正為 Diagonal Distance： h(A) = max(abs(), abs()) 估價函數(shù)的判優(yōu) ? 一般情形下，我們只需對估價函數(shù)的值進(jìn)行比較而取其大者即可，但在幾個結(jié)點(diǎn)的估價函數(shù)值相同的情形下，我們需要采取一定的策略來決定這幾者誰更優(yōu)，從而避免對多個點(diǎn)的搜索。 估價函數(shù)（ Heuristic Function） ? 估價函數(shù)的正確選取將直接關(guān)系到 A*算法的成功與否，而函數(shù)的確定卻與實(shí)際情形有著密切的關(guān)系。要實(shí)現(xiàn)這些，可以通過二分樹、跳轉(zhuǎn)表等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，實(shí)踐中如采用簡單而高效的帶優(yōu)先權(quán)的堆棧，經(jīng)實(shí)驗(yàn)表明，一個 1000個結(jié)點(diǎn)的圖，插入而且移動一個排序的鏈表平均需 500次比較和 2次移動；未排序的鏈表平均需1000次比較和 2次移動；而堆僅需 10次比較和 10次移動。 A*算法的數(shù)據(jù)結(jié)構(gòu) ? 眾所周知，對圖的表示可以采用數(shù)組或鏈表，而且這些表示法也各有優(yōu)缺點(diǎn)，數(shù)組可以方便地實(shí)現(xiàn)對其中某個元素的存取，但插入和刪除操作卻很困難，而鏈表則利于插入和刪除，但對某個特定元素的定位卻需借助于搜索。一個不理想的估價函數(shù)可能會使它工作得很慢，甚至?xí)o出錯誤的解答。它通過一個估價函數(shù)（ Heuristic Function） f(h)來估計圖中的當(dāng)前點(diǎn) p到終點(diǎn)的距離 (帶權(quán)值 )，并由此決定它的搜索方向，當(dāng)這條路徑失敗時，它會嘗試其它路徑。 (3,2,0) (3,1,0) (2,2,0) (3,3,1) h=4,f=4 f(n)=d(n)+m+c2b h h=5,f=6 h=4,f=5 h=4,f=5 (3,2,1) h=3,f=5 (2,1,0) (3,0,0) h=3,f=6 h=3,f=6 (2,2,1) (3,1,1) h=2,f=6 h=2,f=6 h=2,f=7 h=2,f=7 傳教士和野人問題的 A*搜索圖 (0,0,0) (0,3,1) h=1,f=7 (0,1,0) h=1,f=8 (0,2,1) h=0,f=8 (0,2,0) (1,1,0) 關(guān)于 A*算法的一些討論 ? A*算法是到目前為止最快的一種計算最短路徑的算法，但它是一種‘較優(yōu)’算法，即它一般只能找到較優(yōu)解，而非最優(yōu)解，但由于其高效性，使其在實(shí)時系統(tǒng)、人工智能等方面應(yīng)用極其廣泛。 f(n) = g(n) ＋ h(n) = d(n) ＋ m ＋ c － 2b 其中， d(n)為節(jié)點(diǎn)深度。用三元式表示狀態(tài)： S= (m, c, b) 其中， m表示左岸修道士人數(shù)， c表示左岸野人人數(shù)， b表示左岸船的數(shù)目。 2 8 3 1 4 7 6 5 h=4, f=4 S0 2 3 1 8 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 g=1 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 g=2 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 Sg g=4 h=5, f=6 h=5, f=6 h=3, f=4 h=5, f=6 h=2, f=4 h=3, f=5 1