知識的搜索與推理是人工智能研究的一個核心問題，對這一問題的研究曾經(jīng)十分活躍,而且至今仍不乏高層次的研究課題。正如知識表示一樣,知識的搜索與推理也有眾多的方法,同一問題可能采用不同的搜索策略,而其中有的比較有效,有的不大適合具體問題。

表示問題是為了進一步解決問題,從問題表示到問題的解決,有個求解的過程,也就是搜索過程。在這一過程中,采用適當?shù)乃阉骷夹g,包括各種規(guī)則、過程和算法等推理技術,力求找到問題的解答。下面討論一些早期的搜索技術或用于解決比較簡單問題的搜索原理。

首先研究圖搜索(graphsearch)的一般策略,它給出圖搜索過程的一般步驟,并可從中看出無信息搜索和啟發(fā)式搜索的區(qū)別。

可把圖搜索控制策略看成一種在圖中尋找路徑的方法，初始節(jié)點和目標節(jié)點分別代表初始數(shù)據(jù)庫和滿足終止條件的目標數(shù)據(jù)庫。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。

不需要重新安排open表的搜索叫做無信息搜索或盲目搜索,它包括寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價搜索等,盲目搜索只適用于求解比較簡單的問題。

盲目搜索的效率低,耗費過多的計算空間與時間，如果能夠找到一種方法用于排列待擴展節(jié)點的順序,即選擇最有希望的節(jié)點加以擴展,那么搜索效率將會大為提高。在許多情況下,能夠通過檢測來確定合理的順序，優(yōu)先考慮這類檢測的搜索為啟發(fā)式搜索( heuristic search)或有信息搜索( informed search)。

消解原理( resolution principle)是一種可用于一定的子句公式的重要推理規(guī)則。子句定義為由文字的析取組成的公式(一個原子公式和原子公式的否定都叫做文字)。當消解可使用時,消解過程被應用于母體子句對,以產(chǎn)生一個導出子句。

例如,如果存在某個公理e∨e和另一公理e∨e,那么e∨e在邏輯上成立，這就是消解。

對于許多比較復雜的系統(tǒng)和問題,如果采用前面討論過的搜索推理方法,那么很難甚至無法使問題獲得解決。需要應用一些更先進的推理技術和系統(tǒng)(如規(guī)則演繹系統(tǒng)、產(chǎn)生式系統(tǒng)、系統(tǒng)組織技術、不確定性推理和非單調(diào)推理等),求解這種比較復雜的問題,而對于那些發(fā)展特別快的高級求解技術,如 agent、計算智能、專家系統(tǒng)、機器學習和自動規(guī)劃系統(tǒng)等。

產(chǎn)生式系統(tǒng)( production system)由波斯特(post)于1943年提出的產(chǎn)生式規(guī)則( production rule)而得名。人們用這種規(guī)則對符號串進行置換運算。1965年美國的組厄爾和西蒙利用這個原理建立了一個人類的認知模型。同時,斯坦福大學利用產(chǎn)生式系統(tǒng)結(jié)構設計出第一個專家系統(tǒng) dendral。

產(chǎn)生式系統(tǒng)用來描述若干個不同的以一個基本概念為基礎的系統(tǒng)。這個基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的概念。在產(chǎn)生式系統(tǒng)中,論域的知識分為兩部分:用事實表示靜態(tài)知識,如事物、事件和它們之間的關系;用產(chǎn)生式規(guī)則表示推理過程和行為。由于這類系統(tǒng)的知識庫主要用于存儲規(guī)則,因此又把此類系統(tǒng)稱為基于規(guī)則的系統(tǒng)(rule-based system)。

建立在謂詞邏輯基礎上的傳統(tǒng)系統(tǒng)是單調(diào)的,這意味著,已知為真的命題數(shù)目將隨時間而嚴格增加。那是由于新的命題可加人系統(tǒng),新的定理可被證明,但這種加入和被證明絕不會導致前面已知為真或已被證明的命題變成無效。

這種系統(tǒng)具有以下優(yōu)點:

(1)當加入一個新命題時,不必檢查新命題與原有知識之間的不相容性。

(2)對每一個已被證明了的命題,不必保留一個命題表。它的證明以該命題表中的命題為根據(jù),因為不存在那些命題會被取消的危險。