問題求解
正文
從人工智慧初期的智力難題、棋類遊戲、簡單數學定理證明等問題的研究中開始形成和發展起來的一大類解題技術,簡稱解題。機器定理證明(即自動演繹)已形成一門獨立的分支學科。解題技術主要包括問題表示、搜尋和行動計畫等內容。也有人對問題求解作更廣泛的理解,即指為了實現給定目標而展開的動作序列的執行過程。這樣,一切人工智慧系統便都可歸結為問題求解系統。問題求解系統 問題求解系統一般由全局資料庫、運算元集和控制程式三部分組成。①全局資料庫:用來反映當前問題、狀態及預期目標。所採用的數據結構因問題而異,可以是邏輯公式、語義網路、特性表,也可以是數組、矩陣等一切具有陳述性的斷言結構。②運算元集:用來對資料庫進行操作運算。運算元集實際上就是規則集。③控制程式:用來決定下一步選用什麼運算元並在何處套用。解題過程可以運用正向推理,即從問題的初始狀態開始,運用適當的運算元序列經過一系列狀態變換直到問題的目標狀態。這是一種自底向上的綜合方法。也可以運用逆向推理,即從問題的目標出發,選用另外的運算元序列將總目標轉換為若干子目標,也就是將原來的問題歸約為若干較易實現的子問題,直到最終得到的子問題完全可解。這是一種自頂向下的分析方法。A.紐厄爾和H.A.西蒙在通用解題程式GPS中提出的手段-目的分析,則是將正向推理和逆向推理結合起來的一種解題技術。採用這種技術時,不是根據當前的問題狀態而是根據當前狀態和目標狀態間的差異,選用最合適運算元去縮小這種差異(正向推理)。如果當前沒有一個運算元適用,那末就將現時目標歸約為若干子目標(逆向推理),以便選出適用運算元,依此進行,直到問題解決為止。人工智慧許多技術和基本思想在早期的問題求解系統中便孕育形成,後來又有所發展。例如現代產生式系統的體系結構大體上仍可分為三部分。只是全局資料庫採用了更複雜的結構(例如黑板結構),用知識庫取代了運算元集,控制功能更加完善,推理技術也有所發展。
問題表示 有狀態空間、問題歸約、博弈問題、定理證明等表示方式。所有這些表示方式,都廣泛採用數學上的有向圖(包括樹)作為描述手段。
狀態空間表示 如果一個問題求解系統運用正向推理,而且每次運算元對全局資料庫操作後都生成一新狀態,則該系統採用的解題方法就稱狀態空間表示法。圖1中樹的節點標號代表狀態,其中






博弈問題與定理證明問題的表示 以計算機為一方的棋類或其他遊戲問題,常用對策樹(或稱博弈樹)來表示,同一般與或樹的主要差異是:對策樹既要反映兩個問題求解者的共同行動,又只能從一方的立場加以描述。定理證明的問題表示特點在於引入了一類多重輸入單一輸出的運算元。
問題求解的基本技術除問題表示外,尚有搜尋、行動計畫和機器定理證明等方面。
參考書目
N.J.尼爾遜著,石純一等譯:《人工智慧原理》,科學出版社,北京,1983。(N.J.Nilsson, Principlesof Artificial Ihtel-ligence,Tioga Publ.Co.,New York, 1980.)
N.J.Nilsson,Problem-Solving Methods in Artificial Intelligence,McGraw-Hill,New York,1971.