人工智能技術(shù)與應(yīng)用（案例版）課件 第3章 搜索與推理

第3章

搜索與推理人工智能技術(shù)與應(yīng)用ArtificialintelligencetechnologyandApplication1.搜索概述2.盲目搜索3.啟發(fā)式搜索4.推理5.搜索案例案例引入當(dāng)我們到陌生的城市旅游時(shí)，常使用手機(jī)的APP進(jìn)行搜索地點(diǎn)、路徑導(dǎo)航等，也會(huì)搜索附近的美食、旅店等。當(dāng)我們?cè)诿鎸?duì)一個(gè)新事物，新產(chǎn)品，新概念時(shí)，常使用搜索引擎工具進(jìn)行查詢、了解、學(xué)習(xí)。搜索技術(shù)在日常生活中的普遍應(yīng)用和重要性是不言而喻的。但你是否想過，在你使用智能助手搜索附近的餐廳過程中，智能助手是如何從成千上萬(wàn)的選項(xiàng)中找到最符合你需求的那幾家餐廳的？它不僅能夠快速搜索，而且還對(duì)你的喜好、地理位置，甚至是當(dāng)時(shí)的餐飲潮流進(jìn)行復(fù)雜的分析和判斷。這背后就是搜索技術(shù)的功勞。1.搜索概述美國(guó)人工智能專家尼爾森（Nilsson）把搜索列為人工智能研究的四個(gè)核心問題之一。知識(shí)的模型化和表示，常識(shí)性推理、演繹和問題求解，啟發(fā)式搜索，人工智能系統(tǒng)和語(yǔ)言。在人工智能中，搜索問題一般包括兩個(gè)重要的問題：（1）搜索什么（2）在哪里搜索發(fā)展歷史20世紀(jì)50年代。最初，搜索被用于解決邏輯和數(shù)學(xué)問題，如象棋等游戲。這些早期的AI系統(tǒng)，如IBM的DeepBlue，通過搜索算法評(píng)估可能的棋局走法，并選擇最佳策略。DeepBlue在1997年擊敗國(guó)際象棋世界冠軍加里·卡斯帕羅夫，這標(biāo)志著搜索技術(shù)在解決復(fù)雜問題上的巨大潛力。2.盲目搜索在問題的求解過程中，只按照一般的邏輯法則或控制性知識(shí)，在預(yù)定的控制策略下進(jìn)行搜索。典型的盲目搜索有深度優(yōu)先搜索和寬度優(yōu)先搜索。回溯搜索

回溯算法實(shí)際上是一個(gè)類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯”返回，嘗試別的路徑?；厮莘ㄊ且环N選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”八皇后問題如何能夠在8×8的國(guó)際象棋棋盤上放置8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。3.啟發(fā)式搜索僅從當(dāng)前狀態(tài)節(jié)點(diǎn)擴(kuò)展出子節(jié)點(diǎn)(相當(dāng)于找到上爬的路徑)，并將h(x)最小的子節(jié)點(diǎn)(對(duì)應(yīng)于到頂峰最近的上爬路徑)作為下一次考察和擴(kuò)展的節(jié)點(diǎn)，其余子節(jié)點(diǎn)全部丟棄。3.啟發(fā)式搜索A搜索算法是基于估價(jià)函數(shù)的一種加權(quán)啟發(fā)式圖搜索算法f(n)=g(n)+h(n)A*算法則是對(duì)A算法進(jìn)行了優(yōu)化，讓h(n)≤h*(n)，對(duì)h(n）進(jìn)行了限制，是優(yōu)化版的A算法。A算法與A*算法模擬退火算法

模擬退火算法來源于固體退火原理，是一種基于概率的算法。左圖物體處于非晶體狀態(tài)。將固體加溫至充分高（中圖），再讓其徐徐冷卻，也就是退火（右圖）。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小，此時(shí)物體以晶體形態(tài)呈現(xiàn)。4.推理人們?cè)趯?duì)各種事物進(jìn)行分析、綜合并最后做出決策時(shí)，通常是從已知的事實(shí)出發(fā)，通過運(yùn)用已掌握的知識(shí)，找出其中蘊(yùn)含的事實(shí)，或歸納出新的事實(shí)，這一過程通常稱為推理。概念推理分類按推出新判斷的途徑分類01按推出新判斷的途徑分類02按所用知識(shí)確定性分類03按推理過程中的單調(diào)性04按推理過程是否運(yùn)用啟發(fā)性知識(shí)分類推理策略演繹推理所謂演繹推理，就是從一般性的前提出發(fā)，通過推導(dǎo)即“演繹”，得出具體陳述或個(gè)別結(jié)論的過程。形式有三段論、假言推理和選言推理等。歸納推理歸納推理屬于邏輯學(xué)范疇，是一種由個(gè)