人工智能之問題規(guī)約策略

1、Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology人工智能原理人工智能原理( (符號計算科學(xué)符號計算科學(xué)) )Principles ofArtificial IntelligenceRuan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology第五章：第五章：問題規(guī)約策略問題規(guī)約策略Chapter 05Problem-Reductio

2、nApproachRuan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology01 PRA 的基本思想的基本思想Section 01the Essentialsof PRARuan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology01 PRA 的基本思想的基本思想1.1 PRA與狀態(tài)空間法與狀態(tài)空間法 Three-S 的局限性的局限性與狀態(tài)

3、空間法一樣，問題規(guī)約方法也是人工智能的一種基于圖搜索策略的問題求解方法。問題的表現(xiàn)形式是多樣的，甚至是無限的，因此，問題狀態(tài)的數(shù)量可能是巨大的，并非所有的問題都象八數(shù)碼問題一樣，只有 9! 種可能的狀態(tài)。從某種意義上說，狀態(tài)空間法求解問題的過程是狀態(tài)樹生長的過程，是問題狀態(tài)近乎幾何級數(shù)地生長的過程，是被搜索的狀態(tài)空間惡性膨脹的過程Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology01 PRA 的基本思想的基本思想1.1 PRA與狀態(tài)空間法與狀態(tài)空間法 Thr

4、ee-S 的局限性的局限性隨著狀態(tài)空間的膨脹，數(shù)量巨大的問題狀態(tài)需要占用計算機(jī)大量的資源，包括存儲空間和運(yùn)行時間。特別的，對大的問題或復(fù)雜的問題，其狀態(tài)空間中問題狀態(tài)的數(shù)量之大，甚至可能令當(dāng)代最大的計算機(jī)也難以承受。因此，狀態(tài)空間法作為一種人工智能問題求解方法，仍然存在一定的局限性，特別是在求解大問題或復(fù)雜問題的能力上。Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology01 PRA 的基本思想的基本思想1.2 模擬人的復(fù)雜問題求解行為模擬人的復(fù)雜問題求解行為

5、 PRA 面向復(fù)雜問題面向復(fù)雜問題問題規(guī)約是人類處理或求解大問題或復(fù)雜問題的一種常用的方式。人們常常將大的問題或復(fù)雜的問題分解為一系列小的或簡單的問題，然后，分別加以處理或求解。一個大的問題常常是由一些小的問題構(gòu)成的，一個復(fù)雜的問題常常是由一些簡單問題構(gòu)成的。這些小的問題或簡單的問題就是大問題或復(fù)雜問題的子問題。Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology01 PRA 的基本思想的基本思想1.2 模擬人的復(fù)雜問題求解行為模擬人的復(fù)雜問題求解行為 PRA

6、 的的 AI 特征特征問題規(guī)約方法模擬人類處理大問題或復(fù)雜問題的智能行為，將大問題或復(fù)雜問題分解為較小或較簡單的問題，將較小或較簡單的問題再分解為更小或更簡單的問題，直至所有的問題都易于處理或求解為止。最小的問題或具有明顯解答的問題被稱為本原問題。一般地，本原問題是原始問題的子孫問題。因此，問題規(guī)約的過程就是在問題空間中不斷搜索問題的子問題和子問題的子問題的過程，直至將原始問題分解為本原問題集合。Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology01 PRA

7、 的基本思想的基本思想1.3 規(guī)約：規(guī)約： 化解復(fù)雜問題化解復(fù)雜問題問題規(guī)約的基本思想是：將大問題或復(fù)雜問題分解為小的或簡單的本原問題集合。問題規(guī)約方法和狀態(tài)空間法具有共同的特征，這就是圖搜索。問題規(guī)約的圖搜索過程：在問題空間中，以待求解的原始問題為出發(fā)點(diǎn)，以本原問題為目標(biāo)，不斷地搜尋子問題的過程。Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology02 PRA 自學(xué)要點(diǎn)自學(xué)要點(diǎn)Section 02The Focuseson Self-Learning PRA

8、Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology02 PRA 自學(xué)要點(diǎn)自學(xué)要點(diǎn)(一一) PRA 問題的形式化問題的形式化 定義：定義：問題規(guī)約方法中的問題被定義為一個四元組：其中：P,O,p(o),p(p) (5.1)(1) P =p：問題空間 (問題的集合)(2) O =O：算子空間 (操作的集合)(3) p(o)P：原始問題 (Original Problem)(4) p(p)P：本原問題 (Primitive Problem)應(yīng)用 O 中的算子對 p

9、(o) 進(jìn)行操作，將原始問題 p(o) 轉(zhuǎn)化為本原問題集合 p(g) 的過程稱為問題(5.1)的求解。本原問題集合Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology02 PRA 自學(xué)要點(diǎn)自學(xué)要點(diǎn)(一一) PRA 問題的形式化問題的形式化 關(guān)于本原問題：關(guān)于本原問題：所謂本原問題，是指具有明顯解答的問題，或有現(xiàn)成答案的問題，有現(xiàn)成解決方案的問題。從計算機(jī)實現(xiàn)的角度來講，在計算機(jī)數(shù)據(jù)庫 (或方法庫或知識庫) 中已經(jīng)給出了解答的問題，即可視為本原問題。 例如，對于

10、不定積分問題， dx 就是一個本原問題，其答案是顯而易見的，即： dx=x。 Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology02 PRA 自學(xué)要點(diǎn)自學(xué)要點(diǎn)(一一) PRA 問題的形式化問題的形式化 示例：示例：不定積分問題：不定積分問題：不定積分問題的求解過程，常常表現(xiàn)為問題規(guī)約的過程。一個不定積分問題的描述示例如下：(1) 原始問題 p(o)：dxxxxx241cossin(2) 本原問題 p(p)： dz(3) 算子空間 O： 積分規(guī)則Ruan Xi

11、aogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology02 PRA 問題的描述問題的描述(一一) PRA 問題的形式化問題的形式化 示例：示例：不定積分問題：不定積分問題：不定積分問題規(guī)約過程的與或搜索圖Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology02 PRA 自學(xué)要點(diǎn)自學(xué)要點(diǎn)(二二) PRA 問題的三要素問題的三要素 p(o)和和

12、p(p)以及以及O(1) 原始問題 (Original Problem)：p(o)P (問題原態(tài)的描述)(2) 本原問題 (Primitive Problem)：p(p)P (問題終態(tài)的描述)(3) 操作 (又稱算子，Operator)：O: S S或： p(j) = O(p(i) (p(i),p(j)P ; OO)Ruan XiaogangInstitute of Artificial Intelligence & RobotsBeijing University of Technology03 PRA 自學(xué)要點(diǎn)自學(xué)要點(diǎn)(三三) 問題空間問題空間 AND / OR 圖和樹圖和樹AND/OR 圖和樹：描述問題空間，對應(yīng)狀態(tài)空間法中的狀態(tài)圖和狀態(tài)樹。AND/OR 圖和樹搜索算法：(1) AND/OR 圖寬度優(yōu)先搜索算法(2) AND/OR 圖寬深度優(yōu)先搜索算法(3) AND/OR 圖