知識(shí)表示方法1

2知識(shí)表示方法

?2.1知識(shí)與知識(shí)表示的概念

■2.2狀態(tài)空間法

■2?3問(wèn)題規(guī)約法

?2.4謂詞邏輯法

?2.5語(yǔ)義網(wǎng)絡(luò)法

?2.6框架表示法

?2.7劇本表示法

?2.8過(guò)程表示法

2.9小結(jié)

1

2.1知識(shí)與知識(shí)表示的概念

?知識(shí)表示是人工智能研究中最基本的問(wèn)

題之一。在知識(shí)處理中總要問(wèn)到：如何

表示知識(shí)，怎樣使機(jī)器能懂這些知識(shí)，

能對(duì)之進(jìn)行處理，并能以一種人類能理

解的方式將處理結(jié)果告訴人們。

?在人工智能系統(tǒng)中，給出一個(gè)清晰簡(jiǎn)潔

的有關(guān)知識(shí)的描述是很困難的。有研究

報(bào)道認(rèn)為。嚴(yán)格地說(shuō)人工智能對(duì)知識(shí)表

示的認(rèn)真、系統(tǒng)的研究才剛剛開(kāi)始。

2

2.1知識(shí)與知識(shí)表示的概念（續(xù)）

?2d」知識(shí)

>是人們?cè)诟脑炜陀^世界的實(shí)踐中積累起來(lái)的認(rèn)識(shí)

和經(jīng)驗(yàn)

>Feigenbaum認(rèn)為知識(shí)是經(jīng)過(guò)削減、塑造、解釋

和轉(zhuǎn)換的信息。簡(jiǎn)單地說(shuō)，知識(shí)是經(jīng)過(guò)加工的信

息。

?Bernstein說(shuō)知識(shí)是由特定領(lǐng)域的描述、關(guān)系和過(guò)

程組成的。

>Hayes?Roth認(rèn)為知識(shí)是事實(shí)、信念和啟發(fā)式規(guī)則。

?從知識(shí)庫(kù)觀點(diǎn)看，知識(shí)是某論域中所涉及的各有

關(guān)方面、狀態(tài)的一種符號(hào)表或3

2.1知識(shí)與知識(shí)表示的概念（續(xù)）

?知識(shí)的特征

＞相對(duì)正確性：知識(shí)在一定的條件下是正確的，但在另

外一種情況下可能是不正確的。

＞不確定性：事物之間的關(guān)系有時(shí)難以用真假狀態(tài)來(lái)描

述，不確定性就是指這種介于真假之間的中間狀態(tài)。

＞可表示性：知識(shí)通常通過(guò)一定的方法進(jìn)行表示，如：

語(yǔ)言、文字、圖畫(huà)、姿勢(shì)、聲音等。

＞可利用性：人們常用知識(shí)來(lái)認(rèn)識(shí)和改造世界

4

2.1知識(shí)與知識(shí)表示的概念（續(xù)）

?知識(shí)的分類

事實(shí)知識(shí)：是有關(guān)問(wèn)題環(huán)境的一些事物的知識(shí)，常以“…是…”的形式出

現(xiàn)。如事物的分類、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等，事實(shí)是

靜態(tài)的為人們共享的可公開(kāi)獲得的公認(rèn)的知識(shí)，在知識(shí)庫(kù)中屬低層的知識(shí)。

如雪是白色的、鳥(niǎo)有翅膀、張三李四是好朋友、這輛車是張三的。

>規(guī)則知識(shí)：是有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識(shí)，

是動(dòng)態(tài)的，常以“如果…那么…”形式出現(xiàn)。特別是啟發(fā)式規(guī)則是屬專家

提供的專門(mén)經(jīng)驗(yàn)知識(shí)，這種知識(shí)雖無(wú)嚴(yán)格解釋但很有用處。

>控制知識(shí)：是有關(guān)問(wèn)題的求解步驟、技巧性知識(shí)，告訴怎么做一件事。

也包括當(dāng)有多個(gè)動(dòng)作同時(shí)被激活時(shí)應(yīng)選哪一個(gè)動(dòng)作來(lái)執(zhí)行的知識(shí)。

元知識(shí)：是有關(guān)知識(shí)的知識(shí)，是知識(shí)庫(kù)中的高層知識(shí)。包括怎樣使用規(guī)

則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等知識(shí)。元知識(shí)與控制知識(shí)是有

重迭的，對(duì)一個(gè)大的程序來(lái)說(shuō)，以元知識(shí)或說(shuō)元規(guī)則形式體現(xiàn)控制知識(shí)更

為方便，因?yàn)樵R(shí)存于知識(shí)庫(kù)中，而控制知識(shí)常與程序結(jié)合在一起出現(xiàn),

從而不容易修改。

5

2」知識(shí)與知識(shí)表示的概念（續(xù)）

?2.1.2知識(shí)表示

＞知識(shí)表示是研究用機(jī)器表示知識(shí)的可行性、有效性

的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體,

既考慮知識(shí)的存儲(chǔ)又考慮知識(shí)的使用。

＞知識(shí)表示可看成是一組描述事物的約定，以把人類

知識(shí)表示成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu)。

A從實(shí)用觀點(diǎn)看，人工智能是一門(mén)知識(shí)工程學(xué)：以知

識(shí)為對(duì)象，研究知識(shí)的表示方法、知識(shí)的運(yùn)用和知

識(shí)獲取。

6

2」知識(shí)與知識(shí)表示的概念（續(xù)）

?2.1-3知識(shí)表示分類

＞稱述性知識(shí)表示：語(yǔ)義網(wǎng)絡(luò)、框架和劇本等知識(shí)表

示方法，均是對(duì)知識(shí)和事實(shí)的一種靜止的表達(dá)方法,

稱這類知識(shí)表達(dá)方式為陳述式知識(shí)表達(dá)，它所強(qiáng)調(diào)

的是事物所涉及的對(duì)象是什么，是對(duì)事物有關(guān)知識(shí)

的靜態(tài)描述，是知識(shí)的一種顯式表達(dá)形式。而對(duì)于

如何使用這些知識(shí)，則通過(guò)控制策略來(lái)決定

A過(guò)程式知識(shí)表示：就是將有關(guān)某一問(wèn)題領(lǐng)域的知識(shí),

連同如何使用這些知識(shí)的方法，均隱式地表達(dá)為一

個(gè)求解問(wèn)題的過(guò)程。它所給出的是事物的一些客觀

規(guī)律，表達(dá)的是如何求解問(wèn)題。知識(shí)的描述形式就

是程序，所有信息均隱含在程序，因而難于添加新

知識(shí)和擴(kuò)充功能，適用范圍較窄。

7

2.2狀態(tài)空間法

?在分析了人工智能研究中運(yùn)用的'可題求解方法之后，

就會(huì)發(fā)現(xiàn)許多問(wèn)題求解方法是采用試探搜索方法的。

也就是說(shuō)，這些方法是通過(guò)在某個(gè)可能的解空間內(nèi)尋

找一人解來(lái)求解問(wèn)題的。這種基于解答空間的問(wèn)題表

示和求解方法就是狀態(tài)空間法，它是以狀態(tài)和算符

（operator）為基礎(chǔ)乘裝示和求解I可題的。

?狀態(tài)空間法的三要點(diǎn)

＞狀態(tài)（state）：表示問(wèn)題解法中每一步問(wèn)題狀況的數(shù)

據(jù)結(jié)構(gòu)；

＞算符（operator）：把問(wèn)題從一種狀態(tài)變換為另一種

狀態(tài)的事葭；

?狀態(tài)空間方法：基于解答空間的問(wèn)題表示和求解方法,

它是以狀態(tài)和算符為基礎(chǔ)來(lái)表示和求解問(wèn)題的。

8

2.2.1問(wèn)題狀態(tài)描述

?定義

?狀態(tài)￡tate）：為描述某類不同事物間的差別而引入的一組最

少變量q（）,q.…，的有序集合，其矢量形式如下:

式中每個(gè)元素q'S%,n謁4g分量，稱為狀態(tài)變

量。

?算符：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作

位或算符幺蝶作餞可為走步》過(guò)程、,規(guī)華則一.、_數(shù)__學(xué)__算‘子運(yùn)八一算

特號(hào)或邏輯將號(hào)笛。操作的條件（對(duì)狀7態(tài)的要求）和對(duì)狀態(tài)的

改變。

?問(wèn)題的狀態(tài)空間（statespace）：是一個(gè)表示該問(wèn)題全部可能

狀態(tài)及黑關(guān)家的圖，它包含”說(shuō)明的集「口，即=所…有可二能二的

問(wèn)題初始狀恚集合S、操作符集合F以及目標(biāo)狀態(tài)集合G?？?/p>

把狀態(tài)空間記為三元狀態(tài)（S,F,G）o

9

221問(wèn)題狀態(tài)描述（續(xù)）

?舉例

例1：二階梵塔問(wèn)題.設(shè)有三根柱子，它們的編號(hào)分

別是1號(hào),2號(hào),3號(hào).在初始情況下，1號(hào)柱子上穿

看A,B兩個(gè)園盤(pán),A比B小,A位于B的上面,要求把

這兩個(gè)園盤(pán)全部移到第3號(hào)柱子上,而且規(guī)定每次

只能移動(dòng)一個(gè)園盤(pán),任何時(shí)刻都不能使大園盤(pán)位

于小園盤(pán)的上面.

10

2.2.1問(wèn)題狀態(tài)描述（續(xù)）

?狀態(tài)

用Sk={Sk0,SkJ表示問(wèn)題狀態(tài),其中Sko表

示園盤(pán)A所在的柱子號(hào),Sy表示園盤(pán)B所在的

柱子號(hào)。

123123123

So=(l,1)§4=(2,2)§8=(3,3)

11

221問(wèn)題狀態(tài)描述(續(xù))

?算符

算符定義：

操作A(i,力表示把園盤(pán)A從/號(hào)柱子移到j(luò)號(hào)柱子,

操作B(j,7)表示把園盤(pán)B從/號(hào)柱子移到j(luò)號(hào)柱子。

一種得到解的操作序列:A(1,3),B(1,2),A(3,2)

操作的條件：B(1,2):Sk=(x,1)x#1

操作的結(jié)果：B(1,2):Sk=(x,1)Sk=(x,2)

12

221問(wèn)題狀態(tài)描述（續(xù)）

?例2

修道士和野人問(wèn)題：設(shè)在河的左岸有三個(gè)野人，三個(gè)

修道士和一條船，修道士想用這條船把所有的人運(yùn)到河對(duì)

岸，但受以下條件的約束：

1.修道士和野人都會(huì)劃船；

2.船每次至多可載兩個(gè)人；

3.在河的任一岸，如果野人數(shù)目超過(guò)修道士數(shù),修道士

就會(huì)被野人吃掉。

假設(shè)野人會(huì)服從任何一次過(guò)河安排，請(qǐng)規(guī)劃一個(gè)確保

修道士和野人都能過(guò)河，且沒(méi)有修道士被野人吃掉的安全

過(guò)河計(jì)劃。

13

2.2.1問(wèn)題狀態(tài)描述(續(xù))

?狀態(tài)

需要表示出在某岸上的修道士人數(shù)和野人

數(shù)及船在哪岸上。

Sk=(m,c,b)

其中，m表示左岸的修道士人數(shù),c表示左

岸的野人數(shù),b表示左岸的船數(shù)。

初始狀態(tài)：S°=(3,3,1)

中間狀態(tài)：S4=(1,1,1)

目標(biāo)狀態(tài)：S[5=(0,0,0)

14

221問(wèn)題狀態(tài)描述（續(xù)）

?算符

算符定義：

用符號(hào)p,7表示從左岸到右岸運(yùn)/個(gè)修道士j個(gè)野人；用

符號(hào)Q"表示從右岸到左岸運(yùn)/個(gè)修道士J個(gè)野人?？紤]到

船每次最多只能載兩人，則所有操作集合：

F={P01jP10jP11jP02，P20，Qoi，QlO，Q"，QO2，Q20}

操作的條件:

A當(dāng)前狀態(tài)滿足可執(zhí)行條件

>操作不能產(chǎn)生非法狀態(tài)

例：P（）i的操作條件：b=1,m=0或m=3,c>1

當(dāng)前狀態(tài)：S4=（1,1,1）

可執(zhí)行的操作：PO1,P11

15

221問(wèn)題狀態(tài)描述（續(xù)）

操作的結(jié)果：

＞操作執(zhí)行后對(duì)狀態(tài)的改變

例：P°i的結(jié)果:力=0,c=c-l

P10的結(jié)果：b=0,m=m-l

P”的結(jié)果：方=0,c=c-l,m=m-l

P02的結(jié)果：b=0,c=c?2,

P20的結(jié)果：b=0,m=m-2

Q01的結(jié)果：b=l,c=c+l

Q10的結(jié)果：b=Lm=m+l

16

2.2.1問(wèn)題狀態(tài)描述（續(xù)）

要完成某個(gè)問(wèn)題的狀態(tài)描述必須確

定三件事情：

1、該狀態(tài)描述方式，特別是初始狀

態(tài)的描述方式

2、操作符（算符）集合及其對(duì)狀態(tài)

描述的作用

3、目標(biāo)狀態(tài)描述的特征

17

2.2.2解題過(guò)程的表示

?圖的基本概念

節(jié)點(diǎn)(nod^：圖形上的匯合點(diǎn)，用來(lái)表示狀態(tài)、事件和時(shí)間關(guān)系的匯

合，也可用來(lái)指示通路的匯合；

弧線(arc)?節(jié)占間的連接線?

有向圖曼irectedgraph)：二對(duì)節(jié)點(diǎn)用弧線連接起來(lái)，從一個(gè)節(jié)點(diǎn)指向

另一個(gè)節(jié)點(diǎn)。

后繼節(jié)點(diǎn)(descendantnode)與父輩節(jié)點(diǎn)(parentnode)：如果某條弧

線從節(jié)點(diǎn)%指向節(jié)點(diǎn)叫,那么節(jié)點(diǎn)、就叫血節(jié)點(diǎn)n陽(yáng)后窕節(jié)點(diǎn)或后裔，

而節(jié)點(diǎn)岫叫做節(jié)點(diǎn)rij的父輩節(jié)點(diǎn)或咕先。

路徑：某個(gè)節(jié)點(diǎn)序列g(shù)k)當(dāng)當(dāng)jj==22,33,,??.，kk時(shí)時(shí)，，如如果果對(duì)對(duì)于于每每

點(diǎn)凸看2,二存，在，對(duì)么就把這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)

個(gè)Ug都有一個(gè)后

?室十點(diǎn)小的長(zhǎng)度為k的路徑。

代價(jià)：用c(g,g)來(lái)表示從節(jié)點(diǎn)w指向節(jié)點(diǎn)叫的那段弧線的代價(jià)。兩節(jié)

點(diǎn)間路徑的代林等于連接該路徑上各節(jié)點(diǎn)的所有弧線代價(jià)之和。

顯式表示：各節(jié)點(diǎn)及其具有代價(jià)的弧線由一張表明確給出。此表可能

列出該圖中的每一節(jié)點(diǎn)、它的后繼節(jié)點(diǎn)以及連接弧線的代價(jià)。

隱式表示：節(jié)點(diǎn)的無(wú)限集合｛sj作為起始節(jié)點(diǎn)是已知的。后繼節(jié)點(diǎn)算符

「也是已知的，它能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各

連接弧線的代價(jià)。18

2.2.2解題過(guò)程的表示（續(xù)）

?狀態(tài)空間圖

把初始狀態(tài)可達(dá)到的各狀態(tài)所組成的空間用有

向圖表示.用"狀態(tài)”標(biāo)識(shí)節(jié)點(diǎn)，用”操作"標(biāo)識(shí)

有

向邊,有向邊的方向由操作的施加對(duì)象狀態(tài)指向

操作的結(jié)果狀態(tài)。

19

2.2.2解題過(guò)程的表示（續(xù)）

?例1的狀態(tài)空間圖

A(3,l)B(3,2)A(?

20

2.2.2解題過(guò)程的表示（續(xù)）

?例2的狀態(tài)空間圖

I(3,2,0)

(3,2d)(0,1,0)

(3,0,0)

(3,1,1)||(0,3,1)|

(14,0)

(2.2J):(0,2,0)L

2.2.3狀態(tài)空間問(wèn)題求解

?狀態(tài)空間法：從某個(gè)初始狀態(tài)開(kāi)始，每次加一個(gè)操作符，

遞增地建立起操作符的試驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)為

止.

?基本過(guò)程：

1.為問(wèn)題選擇適當(dāng)?shù)摹盃顟B(tài)"及"操作符”的形式化描述

方法,定義初始狀態(tài)集合，目標(biāo)狀態(tài)集合及操作符集合；

2.將操作符作用在初始狀態(tài)（新?tīng)顟B(tài)）上生成新?tīng)顟B(tài)逐步構(gòu)

造狀態(tài)空間，判斷新?tīng)顟B(tài)是否為目標(biāo)狀態(tài),如果是轉(zhuǎn)3.否

則轉(zhuǎn)2.

3.尋找從初始狀態(tài)到目標(biāo)狀態(tài)的一個(gè)（最佳）路徑。路徑邊

上所使用的操作符序列就是該問(wèn)題的一個(gè)解.

22

223狀態(tài)空間問(wèn)題求解(續(xù))

?例1的求解過(guò)程

I(1>1)I

A(I,曳7尸二、A(in)

A(3,2)

I(2JL)h==d(3,1)

B(l,3)x^A(2,3)N>(1,2)

I(好II(32)|

AQ畛:公8B(2,3)______A(2Jp^(^，2)

(3,3)卜J(L3)卜」Q,2)(2,2)|

A(3,l)B(3,2)A(10

23

223狀態(tài)空間問(wèn)題求解(續(xù))

?使用狀態(tài)空間法求解問(wèn)題的系統(tǒng)：產(chǎn)生式系統(tǒng)

?產(chǎn)生式系統(tǒng)是描述搜索過(guò)程的方法，其構(gòu)成是：

?1.一個(gè)總數(shù)據(jù)庫(kù)(globaldatabase)，它含與具

體任務(wù)有關(guān)的信息。

?2.一套規(guī)則，它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)

則由左右兩部分組成，左部鑒別規(guī)則的適用性和

先決條件，右部描述規(guī)則應(yīng)用時(shí)所完成的動(dòng)作。

應(yīng)用規(guī)則來(lái)改變數(shù)據(jù)庫(kù)，就象應(yīng)用算符來(lái)改變狀

態(tài)一樣。

>3'一個(gè)控制策略，它確定應(yīng)該采用哪一條使用規(guī)

則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就停止計(jì)

舁。24

2.3問(wèn)題規(guī)約法

?2.3.1問(wèn)題歸約描述

?2.3.2問(wèn)題歸約的與或圖表示

?2.3.3問(wèn)題歸約法的問(wèn)題求解

25

231問(wèn)題規(guī)約描述

?1.問(wèn)題歸約：從較復(fù)雜難于求解的目標(biāo)問(wèn)題出發(fā)，

進(jìn)行分解或變換,將它轉(zhuǎn)化為一系列較簡(jiǎn)單易于求

解的子問(wèn)題及子問(wèn)題的子問(wèn)題,直至歸約為一個(gè)平

凡的易求解的本原問(wèn)題集合。

?2.問(wèn)題歸約表示的組成部分

>一個(gè)初始問(wèn)題描述；

>一套把問(wèn)題變換為子問(wèn)題的操作符；

>一套本原問(wèn)題描述。

?3.問(wèn)題的描述：采用各種數(shù)據(jù)結(jié)構(gòu)：表列，樹(shù)，字符串,

矢量,數(shù)組等。

26

2.3.1問(wèn)題規(guī)約描述（續(xù)）

?例3：三階梵塔問(wèn)題，設(shè)有三根柱子，它們的編號(hào)分別是1號(hào),

2號(hào),3號(hào).在初始情況下,1號(hào)柱子上穿有A,B,C三個(gè)園盤(pán),A

比B小，B比C小,A位于B的上面，B位于C的上面.要求把這

三個(gè)園盤(pán)全部移到第3號(hào)柱子上,而且規(guī)定每次只能移動(dòng)一個(gè)

園盤(pán),任何時(shí)刻都不能使大園盤(pán)位于小園盤(pán)的上面。如果采

用狀態(tài)空間法求解，其狀態(tài)空間圖包括27個(gè)節(jié)點(diǎn)，每個(gè)節(jié)

點(diǎn)代表柱子上園盤(pán)的一個(gè)正確配置。

A

B

C

3

27

2.3.1問(wèn)題規(guī)約描述（續(xù)）

?問(wèn)題描述：

例3:采用三元組表示狀態(tài)：

S=（a,b,c）

其中，a,b,c是整數(shù)分別表示園盤(pán)A,B,C所

在的柱子號(hào)。

初始狀態(tài)：（1」」）

目標(biāo)狀態(tài)：（3,3,3）

28

2.3.1問(wèn)題規(guī)約描述(續(xù))

A扈

B

C

(a)移動(dòng)圓盤(pán)A

—

和B至柱子2123

(1JJ)Q21)

(b)移動(dòng)圓盤(pán)C

至柱子3

123

(221)

(c)移動(dòng)圓盤(pán)A

和B至柱子3

123

(2,2,3)(3,3,3)

2.3.2問(wèn)題規(guī)約的與或圖表示

?1.問(wèn)題的分解與等價(jià)變換

(1)分解：如果一個(gè)問(wèn)題P可以歸約為一組子

問(wèn)題P］，P2,…，Pn，并且只有當(dāng)所有子問(wèn)題

Pj(/=i,2,…，m都有解時(shí)原問(wèn)題p才有解，任

何一個(gè)子問(wèn)題P“=1,2,…，m無(wú)解都會(huì)導(dǎo)致

原問(wèn)題p無(wú)解,則稱此種歸約為問(wèn)題的分解。

即分解所得到的子問(wèn)題的"與"與原問(wèn)題p

等價(jià)。

30

2.3.2問(wèn)題規(guī)約的與或圖表示(續(xù))

在例3中：原問(wèn)題可分解為三個(gè)子問(wèn)題：

>①把園盤(pán)A及B移到2號(hào)柱子上的雙園盤(pán)移動(dòng)

問(wèn)題。[(1,1,1)H2,2,1)]

>②把園盤(pán)C移到3號(hào)柱子上的單園盤(pán)移動(dòng)問(wèn)

題。[(2,2,1)一(2,2,3)]

>③把園盤(pán)A及B移動(dòng)到3號(hào)園盤(pán)的雙園盤(pán)移動(dòng)

問(wèn)題。[(223)-(333)]

其中子問(wèn)題①和③還可以繼續(xù)進(jìn)行分解。而

子問(wèn)題②不需要再分解,稱為本原問(wèn)題。

31

232問(wèn)題規(guī)約的與或圖表示(續(xù))

(2)等價(jià)變換：如果一個(gè)問(wèn)題P可以歸約為一

組子問(wèn)題P］，P2,…，Pn,并且這些子問(wèn)題

Pi(/=1,2,…，")中只要有一個(gè)有解則原問(wèn)題P

就有解，只有當(dāng)所有子問(wèn)題pa3,2,…，m都

無(wú)解時(shí)，原問(wèn)題p才無(wú)解，則稱此種歸約為問(wèn)

題的等價(jià)變換,簡(jiǎn)稱變換，即變換所得到的子

問(wèn)題的"或“與原問(wèn)題p等價(jià)。

32

2.3.2問(wèn)題規(guī)約的與或圖表示(續(xù))

在例2中：原問(wèn)題(3,3,1)一(0,0,0)可變換為以下三個(gè)子問(wèn)題：

①一個(gè)野人先過(guò)河：

(3,3,1)一(3,2,0)和(3,2,0)—(0,0,0)

②一個(gè)修道士和一個(gè)野人先過(guò)河：

(3,3,1)—(2,2,0)和(2,2,0)一(0,0,0)

③兩個(gè)野人先過(guò)河：

(3,3,1)一(3,1,0)和(3,1,0)—(0,0,0)

其中：

＞只要有一個(gè)子問(wèn)題可解，則原問(wèn)題可解。

＞每個(gè)子問(wèn)題又分別由兩個(gè)“子”子問(wèn)題組成。只有這兩個(gè)”

子”子問(wèn)題都可解時(shí)，子問(wèn)題才可解。

＞有些"子”子問(wèn)題還可以進(jìn)行再變換或分解。直到變換或

分解為直接可解的本原問(wèn)題。

33

232問(wèn)題規(guī)約的與或圖表示（續(xù)）

從上例可以看出：

＞在實(shí)際問(wèn)題的歸約過(guò)程中，有可能需要同時(shí)采

用變換和分解的方法。無(wú)論是分解還是變換,

都是要將原問(wèn)題最終歸約為一系列本原問(wèn)題。

＞本原問(wèn)題：指那些不能（或不需要）再進(jìn)行分解

或變換，且可以直接解答的子問(wèn)題。

＞本原問(wèn)題可以作為對(duì)問(wèn)題進(jìn)行歸約的限制條

件（結(jié)束條件）。

＞問(wèn)題的變換或分解是通過(guò)操作符（算符）來(lái)實(shí)

現(xiàn)的。

34

232問(wèn)題規(guī)約的與或圖表示(續(xù))

?2.問(wèn)題歸約的與或圖表示

(1)與圖

把一個(gè)原問(wèn)題分解為若干個(gè)子問(wèn)題Pi，Pz，

P3,…可用一個(gè)”與圖”來(lái)表示。PrP2,

P3,…對(duì)應(yīng)的子問(wèn)題節(jié)點(diǎn)稱為“與節(jié)點(diǎn)”

例：設(shè)P可以分解為三個(gè)子問(wèn)題PqPo,P3的與，則

P和％P3之間的關(guān)系可用卡圖布示南一個(gè)”

與圖”表余

P

Plp2P3

35

2.3.2問(wèn)題規(guī)約的與或圖表示(續(xù))

(2)或圖

把一個(gè)原問(wèn)題變換為若干個(gè)子問(wèn)題P.P2,P3,

???，可用一個(gè)"或圖”來(lái)表示。子問(wèn)題P.P2,P3,

…對(duì)應(yīng)的節(jié)點(diǎn)稱為“或節(jié)點(diǎn)”。

例：設(shè)P可以變換為三個(gè)子問(wèn)題P.P2，P3的或，

則P和Pi，P2，P3下圖所示的一個(gè)“或圖”表示：

232問(wèn)題規(guī)約的與或圖表示(續(xù))

(3)與或圖

如果一個(gè)原問(wèn)題即需要通過(guò)分解又需要通過(guò)

變換才能得到其本原問(wèn)題,則其歸約過(guò)