從人工智慧初期的智力難題、棋類遊戲、簡單數學定理證明等問題的研究中開始形成和發展起來的一大類解題技術，簡稱解題。機器定理證明（即自動演繹）已形成一門獨立的分支學科。解題技術主要包括問題表示、搜索和行動計畫等內容。也有人對問題求解作更廣泛的理解，即指為瞭實現給定目標而展開的動作序列的執行過程。這樣，一切人工智慧系統便都可歸結為問題求解系統。

　　問題求解系統　問題求解系統一般由由全局數據庫、算子集和控制程序三部分組成。①全局數據庫：用來反映當前問題、狀態及預期目標。所采用的數據結構因問題而異，可以是邏輯公式、語義網絡、特性表，也可以是數組、矩陣等一切具有陳述性的斷言結構。②算子集：用來對數據庫進行操作運算。算子集實際上就是規則集。③控制程序：用來決定下一步選用什麼算子並在何處應用。解題過程可以運用正向推理，即從問題的初始狀態開始，運用適當的算子序列經過一系列狀態變換直到問題的目標狀態。這是一種自底向上的綜合方法。也可以運用逆向推理，即從問題的目標出發，選用另外的算子序列將總目標轉換為若幹子目標，也就是將原來的問題歸約為若幹較易實現的子問題，直到最終得到的子問題完全可解。這是一種自頂向下的分析方法。A.紐厄爾和H.A.西蒙在通用解題程序GPS中提出的手段-目的分析，則是將正向推理和逆向推理結合起來的一種解題技術。采用這種技術時，不是根據當前的問題狀態而是根據當前狀態和目標狀態間的差異，選用最合適算子去縮小這種差異（正向推理）。如果當前沒有一個算子適用，那末就將現時目標歸約為若幹子目標（逆向推理），以便選出適用算子，依此進行，直到問題解決為止。人工智能許多技術和基本思想在早期的問題求解系統中便孕育形成，後來又有所發展。例如現代產生式系統的體系結構大體上仍可分為三部分。隻是全局數據庫采用瞭更復雜的結構（例如黑板結構）,用知識庫取代瞭算子集,控制功能更加完善，推理技術也有所發展。

　　問題表示　有狀態空間、問題歸約、博弈問題、定理證明等表示方式。所有這些表示方式，都廣泛采用數學上的有向圖（包括樹）作為描述手段。

　　狀態空間表示　如果一個問題求解系統運用正向推理，而且每次算子對全局數據庫操作後都生成一新狀態，則該系統采用的解題方法就稱狀態空間表示法。圖1中樹的節點標號代表狀態，其中

為初始狀態， 為目標狀態；有向弧線的標號代表算子；從初始狀態到達目標狀態經歷 →②→③→ 的狀態變換。這時問題的一個解便是能將問題初始狀態最終變換為目標狀態的一個有限的算子序列。本例中即為 P 2- P 2- P 4。而尋找問題的解，也就是尋找適用的算子序列的過程，這稱為搜索。

　　問題歸約表示　問題歸約有三個要素，即目標、算子集和基元問題集。①目標：即問題的初始描述。②算子集：用來將給定問題變換為若幹子問題。③基元問題集：已有解或其解十分明顯可以直接描述的問題。問題約表示是同逆向推理聯系在一起的。圖2為問題的歸約表示，其中每個節點標號代表一個問題或一組問題,標號為A的根節點（即沒有射入弧線的節點）代表原始問題或問題組。沒有射出弧線的節點稱為葉或終端節點（或終止節點），其標號代表基元問題。運用算子實行問題變換。如果原來問題被變換為若幹子問題，而隻需要解決其中之一便可解決原問題，那末代表這些子問題的節點稱為相對於原問題節點的或節點。圖2的B、C、D即為相對於 A的或節點。如果原問題被變換為缺一不可（均需解決）的若幹子問題，那麼代表這些子問題的節點稱為相對於原問題節點的與節點，並在這些與節點各自的射入弧線間標記一條連接線，以同或結點相區別。圖2的E、F、G和G、H、K分別為相對於B和D的與節點。既包含與節點又包含或節點的有向圖稱為與或圖。問題歸約表示常借助於與或圖的形式。為瞭表明原問題有解，其實隻需要畫出與或圖中同問題的解有關的那一部分（即子圖）,稱為解圖。圖2有三個解圖，{A，B，E，F，G}、{A，C}、{A，D，G，H，K}。如果在與或圖中,除根節點以外的每個節點有且僅有一條射入弧線（即隻有一個父親），便得到與或樹。與或樹是與或圖的特例。

　　博弈問題與定理證明問題的表示　以計算機為一方的棋類或其他遊戲問題，常用對策樹（或稱博弈樹）來表示，同一般與或樹的主要差異是：對策樹既要反映兩個問題求解者的共同行動，又隻能從一方的立場加以描述。定理證明的問題表示特點在於引入瞭一類多重輸入單一輸出的算子。

　　問題求解的基本技術除問題表示外，尚有搜索、行動計劃和機器定理證明等方面。

　　

參考書目

　N.J.尼爾遜著,石純一等譯：《人工智能原理》,科學出版社，北京，1983。（N.J. Nilsson，Principles of Artificial Ihtel-ligence，Tioga Publ. Co.，New York, 1980.)

　N.J.Nilsson，Problem－Solving Methods in Artificial Intelligence，McGraw-Hill，New York，1971.