第五講經(jīng)典人工智能技術(shù)—知識(shí)表示、推理與搜索77-資料下載頁
2025-03-15 21:12本頁面
【正文】 的算法稱為 A*算法 f (x) = g (x) + h (x) A*算法的限制條件 大于 0 不大于 x到目標(biāo)的實(shí)際代價(jià) 彼得 .哈特 智能科學(xué)與技術(shù)系 利用 A*算法求解八數(shù)碼問題 估價(jià)函數(shù)的定義 f (x) = g (x) + h (x) g (x)：從初始狀態(tài)到 x需要進(jìn)行的移動(dòng)操作的次數(shù) h (x)：？ 誰更接近目標(biāo)狀態(tài)？ 錯(cuò)放的棋子越少越好！ =x狀態(tài)下錯(cuò)放的棋子數(shù) 滿足限制條件 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 8 1 3 2 4 5 6 7 h(x)=1 h(x)=2 h(x)=4 智能科學(xué)與技術(shù)系 4 5 6 3 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1+3 1+5 1+5 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 2+4 2+3 2+3 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 3+2 3+4 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 3+3 3+4 1 2 3 8 4 5 6 7 4+1 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 5+0 5+2 5 7 1 1 2 3 8 4 6 0+4 5 2 OPEN表 CLOSED表 智能科學(xué)與技術(shù)系 估價(jià)函數(shù)對(duì)算法的影響 不同的估價(jià)函數(shù)對(duì)算法的效率可能產(chǎn)生極大的影響 不同的估價(jià)函數(shù)甚至產(chǎn)生不同的算法 f (x) = g (x) + h (x) h (x)=0： Dijkstra算法，非啟發(fā)式算法 g (x)=0：貪婪搜索，無法保證找到解 即使采用同樣的形式 f (x) = g (x) + h (x) ，不同的定義和不同的值也會(huì)影響搜索過程 智能科學(xué)與技術(shù)系 估價(jià)函數(shù)對(duì)算法的影響示例 例：八數(shù)碼問題 f (x) = g (x) + h (x) g (x)：從初始狀態(tài)到 x需要進(jìn)行的移動(dòng)操作的次數(shù) h (x)：所有棋子與目標(biāo)位置的曼哈頓距離之和 曼哈頓距離：兩點(diǎn)之間水平距離和垂直距離之和 仍滿足估價(jià)函數(shù)的限制條件 1 2 3 8 4 5 6 7 h(x)= 2 +1 +1 +2=6 智能科學(xué)與技術(shù)系 3 4 5 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1+4 1+6 1+6 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 2+5 2+5 2+3 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 3+2 3+4 1 2 3 8 4 5 6 7 4+1 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 5+0 5+2 0+5 5 7 1 1 2 3 8 4 6 5 2 智能科學(xué)與技術(shù)系 例：路徑規(guī)劃 S G 45 6 4 4 5 5 6 6 A*算法被廣泛應(yīng)用于靜態(tài)路網(wǎng)中的最短路徑規(guī)劃 用距離表示代價(jià) 每一步可以往相鄰的 8個(gè)無障礙格子移動(dòng)，移動(dòng)距離為 1 g (x)：從出發(fā)點(diǎn) S到當(dāng)前點(diǎn) x的距離 h (x)：從當(dāng)前點(diǎn) x到目標(biāo)點(diǎn) G的距離 5 6 6 7 5 6 7 7 7 7 7 5 5 5 6 7 7 6 6 6 7 智能科學(xué)與技術(shù)系 謝謝大家！ 智能科學(xué)與技術(shù)系 靜夜四無鄰，荒居舊業(yè)貧。 , April 2, 2023 雨中黃葉樹，燈下白頭人。 01:37:0301:37:0301:374/2/2023 1:37:03 AM 1以我獨(dú)沈久，愧君相見頻。 :37:0301:37Apr232Apr23 1故人江海別，幾度隔山川。 01:37:0301:37:0301:37Sunday, April 2, 2023 1乍見翻疑夢(mèng)，相悲各問年。 :37:0301:37:03April 2, 2023 1他鄉(xiāng)生白發(fā)，舊國見青山。 2023年 4月 2日星期日 上午 1時(shí) 37分 3秒 01:37: 1比不了得就不比，得不到的就不要。 。 2023年 4月 上午 1時(shí) 37分 :37April 2, 2023 1行動(dòng)出成果，工作出財(cái)富。 2023年 4月 2日星期日 1時(shí) 37分 3秒 01:37:032 April 2023 1做前，能夠環(huán)視四周；做時(shí)，你只能或者最好沿著以腳為起點(diǎn)的射線向前。 上午 1時(shí) 37分 3秒 上午 1時(shí) 37分 01:37: 沒有失敗，只有暫時(shí)停止成功！。 , April 2, 2023 很多事情努力了未必有結(jié)果，但是不努力卻什么改變也沒有。 01:37:0301:37:0301:374/2/2023 1:37:03 AM 1成功就是日復(fù)一日那一點(diǎn)點(diǎn)小小努力的積累。 :37:0301:37Apr232Apr23 1世間成事，不求其絕對(duì)圓滿，留一份不足，可得無限完美。 01:37:0301:37:0301:37Sunday, April 2, 2023 1不知香積寺，數(shù)里入云峰。 :37:0301:37:03April 2, 2023 1意志堅(jiān)強(qiáng)的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 4月 2日星期日 上午 1時(shí) 37分 3秒 01:37: 1楚塞三湘接，荊門九派通。 。 2023年 4月 上午 1時(shí) 37分 :37April 2, 2023 1少年十五二十時(shí)，步行奪得胡馬騎。 2023年 4月 2日星期日 1時(shí) 37分 3秒 01:37:032 April 2023 1空山新雨后，天氣晚來秋。 上午 1時(shí) 37分 3秒 上午 1時(shí) 37分 01:37: 楊柳散和風(fēng)，青山澹吾慮。 , April 2, 2023 閱讀一切好書如同和過去最杰出的人談話。 01:37:0301:37:0301:374/2/2023 1:37:03 AM 1越是沒有本領(lǐng)的就越加自命不凡。 :37:0301:37Apr232Apr23 1越是無能的人，越喜歡挑剔別人的錯(cuò)兒。 01:37:0301:37:0301:37Sunday, April 2, 2023 1知人者智，自知者明。勝人者有力，自勝者強(qiáng)。 :37:0301:37:03April 2, 2023 1意志堅(jiān)強(qiáng)的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 4月 2日星期日 上午 1時(shí) 37分 3秒 01:37: 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。 2023年 4月 上午 1時(shí) 37分 :37April 2, 2023 1業(yè)余生活要有意義，不要越軌。 2023年 4月 2日星期日 1時(shí) 37分 3秒 01:37:032 April 2023 1一個(gè)人即使已登上頂峰，也仍要自強(qiáng)不息。 上午 1時(shí) 37分 3秒 上午 1時(shí) 37分 01:37: MOMODA POWERPOINT Lorem ipsum dolor sit amet, consectetur adipiscing elit. Fusce id urna blandit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis ut cursus. 感謝您的下載觀看 專家告訴
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1