人工智能與專家系統(tǒng)教學(xué)課件

第五章問題求解策略5.1搜索的概念及基本原理5.2圖搜索策略5.3盲目搜索5.4啟發(fā)式搜索人工智能與專家系統(tǒng).第五章問題求解策略5.1搜索的概念及基本原理5.2圖搜索策略5.3盲目搜索5.4啟發(fā)式搜索5.1搜索的概念及基本原理●問題求解的基本方法有:搜索法、歸約法、歸結(jié)法、推理法和產(chǎn)生式等搜索技術(shù)是人工智能的核心技術(shù)之一?！駥τ跓o成熟方法可用的問題求解,只能利用已有的知識一步步地摸索求解,這種問題求解過程就是搜索。5.1搜索的概念及基本原理現(xiàn)實世界中的大多數(shù)問題都是非結(jié)構(gòu)化問題,一般不存在現(xiàn)成的求解方法來求解這樣的問題,而只能利用已有的知識一步一步地摸索著前進。搜索:是一種求解問題的方法,是尋找從問題初始事實到最終答案的推理路線的一種過程搜索包含兩層含義:一是根據(jù)問題實際情況,按照一定策略,從知識庫中尋找可利用的知識,從而構(gòu)造出一條使問題獲得解決的推理路線;另一是找到的這條路線是時空復(fù)雜度最小的求解路線35.1搜索的概念及基本原理●問題求解的基本方法有:搜索法、歸約法、歸結(jié)法、推理法和產(chǎn)生式等搜索技術(shù)是人工智能的核心技術(shù)之一。●對于無成熟方法可用的問題求解,只能利用已有的知識一步步地摸索求解,這種問題求解過程就是搜索。5.1搜索的概念及基本原理現(xiàn)實世界中的大多數(shù)問題都是非結(jié)構(gòu)化問題,一般不存在現(xiàn)成的求解方法來求解這樣的問題,而只能利用已有的知識一步一步地摸索著前進。搜索:是一種求解問題的方法,是尋找從問題初始事實到最終答案的推理路線的一種過程搜索包含兩層含義:一是根據(jù)問題實際情況,按照一定策略,從知識庫中尋找可利用的知識,從而構(gòu)造出一條使問題獲得解決的推理路線;另一是找到的這條路線是時空復(fù)雜度最小的求解路線3搜索與問題求解●問題求解過程是搜索答案(目標)的過程/所以問題求解技術(shù)也叫搜索技術(shù)一通過對狀態(tài)空間的搜索而求解問題的技術(shù)問題求解智能體是一種基于目標的智能體在尋找到達目標的過程中,當智能體面對多個未知的選項時,首先檢驗各個不同的導(dǎo)致已知評價的狀態(tài)的可能行動序列,然后選擇最佳序列一這個過程就是搜索4問題與問題的解●問題可以形式化地定義為4個組成部分智能體的初始狀態(tài)(即搜索的開始)后繼函數(shù)—智能體采取的可能行動的描述,通常為<行動,后繼狀態(tài)〉/初始狀態(tài)和后繼函數(shù)隱含地定義了問題的狀態(tài)空間/狀態(tài)空間中的一條路徑是通過行動序列連接起來的一個狀態(tài)序列目標測試一檢查給定的狀態(tài)是不是目標路徑耗散函數(shù)—每條路徑都有一個數(shù)值化的耗散值,反映了性能度量/求解問題的代價5問題的解●問題的解就是初始狀態(tài)到目標狀態(tài)的路徑解的優(yōu)劣由路徑耗散函數(shù)量度(代價)最優(yōu)解就是路徑耗散函數(shù)值最小的路徑●上述解題過程把解決一個問題的過程描述出來,稱之為解題知識的過程性表示過程性知識與陳述性知識相對搜索過程解題的特點一沒有直接的方法(公式)可以求解,而是一步一步的探索6狀態(tài)空間數(shù)據(jù)基:代表了所要解決的問題,有初始狀態(tài),可能有目標狀態(tài)也可能沒有●狀態(tài)空間:在解題過程中的每一時刻,數(shù)據(jù)基都處于一定的狀態(tài),數(shù)據(jù)基所有可能狀態(tài)的集合稱為狀態(tài)空間●有向圖:若把每個狀態(tài)看成一個節(jié)點,則整個狀態(tài)空間是一個有向圖/該圖不一定全連通即從某些狀態(tài)不一定能到達另外一些狀態(tài)7①搜索的基本問題●搜索過程是否一定能找到解;●搜索過程是否終止運行或是否會陷入死循環(huán)當搜索過程找到一個解時,是否為最佳解●搜索過程的時間與空間復(fù)雜性如何。9②搜索的主要過程(1)從初始或目的狀態(tài)出發(fā),并將它作為當前狀態(tài)(2)掃描操作算子集,運用操作算子得到新的狀態(tài)