人工智能交大題目及答案

人工智能交大題目及答案《人工智能導(dǎo)論》全真試題

7、某問(wèn)題的狀態(tài)空間圖如下圖所示，其中括號(hào)內(nèi)標(biāo)明的是各節(jié)點(diǎn)的h值，弧線邊的數(shù)字是該弧線的耗散值，試用A算法求解從初始節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)T的路徑。要求給出搜索圖，標(biāo)明各節(jié)點(diǎn)的f值，及各節(jié)點(diǎn)的擴(kuò)展次序，并給出求得的解路徑。三、問(wèn)答題答案第1題

答：得解圖：第3題

答：綜合數(shù)據(jù)庫(kù)：

(m1,m5,m9,b)設(shè)從河的左岸到右岸，其中m1,m5,m9分別表示過(guò)河時(shí)間需要1分鐘，5分鐘和9分鐘的人，在河左岸的人數(shù)。b＝1表示船在左岸，b＝0表示船在右岸。規(guī)則集：初始狀態(tài)：

(2,1,1,1)

結(jié)束狀態(tài)

(0,0,0,0)

h函數(shù)：

h(n)=m-b，其中m為在左岸的人數(shù)，b為船是否在左岸。

對(duì)于任意兩個(gè)節(jié)點(diǎn)ni和nj，其中nj是ni的子節(jié)點(diǎn)。

當(dāng)ni中b＝1時(shí)，則nj中b＝0，因此：max(h(ni)-h(j))=(m-1)-(m-1)=0,而C(ni,nj)最小為1，因此h(ni)-h(nj)<C(ni,nj);

當(dāng)ni中b＝0時(shí)，則nj中b＝1，因此：max(h(ni)-h(j))=m-m=0,而C(ni,nj)最小為1，因此h(ni)-h(nj)<C(ni,nj)。

而對(duì)于目標(biāo)節(jié)點(diǎn)t，h(t)=0。

因此該h函數(shù)滿足單調(diào)性條件。所以h滿足A*條件。

第4題

答：對(duì)事實(shí)和規(guī)則進(jìn)行skolem化：

（1）(s)

~P(a)

（2）(s)(P(g(s)))

P(g(s))

（3）(x)(s)(y)((P(s)∧Q(b，x，s))→H(y)

(P(s)∧Q(b，c，s))→H(f(s))

（4）(x)(s)(Q(b，x，s)→Q(b，x，g(s)))

Q(b，x，s)→Q(b，x，g(s))

（5）(x)(s)(y)(~P(s)→Q(b，x，y))

~P(s)→Q(b，x，h(x,s))

經(jīng)變量換名后，有事實(shí)和規(guī)則如下：

~P(a)

P(g(s1))

r1:(P(s2)∧Q(b，c，s2))→H(f(s2))

r2:Q(b，x3，s3)→Q(b，x3，g(s3))

r3:~P(s4)→Q(b，x4，h(x4,s4))

用對(duì)偶形式對(duì)目標(biāo)skolem化：

(x)H(x)

H(x)

演繹圖如下圖(這里只給出了一個(gè)一致解圖)。由置換集構(gòu)造U1和U2：

U1=(x,s2,x3,s2,x4,s3,s4)

U2=(f(s2),g(s1),c,g(s3),c,h(x4,s4),a)

由于U1和U2是可合一的，因此該解圖是一致解圖。合一復(fù)合為：

{f(g(h(c,a)))/x,g(h(c,a))/s2,c/x3,h(c,a)/s3,c/x4,h(c,a)/s1,a/s4}}將該合一復(fù)合帶入目標(biāo)中，得到解答：

x=f(g(h(c,a)))

第5題

答：

1、由于修正的A*算法對(duì)與OPEN表中f值小于fm的節(jié)點(diǎn)按照g值的大小排序，優(yōu)先擴(kuò)展g值小的節(jié)點(diǎn)。對(duì)于這部分節(jié)點(diǎn)來(lái)說(shuō)，相當(dāng)于h＝0。而h＝0滿足單調(diào)條件，因此至少對(duì)于這部分節(jié)點(diǎn)來(lái)說(shuō)，減少了重復(fù)擴(kuò)展節(jié)點(diǎn)的可能性。因此修正的A*算法有可能減少重復(fù)節(jié)點(diǎn)的擴(kuò)展。2、由于A*擴(kuò)展的節(jié)點(diǎn)，其f值總是小于等于f*(s)，而fm是到目標(biāo)為止擴(kuò)展過(guò)的節(jié)點(diǎn)的最大f值，因此必有fm小于等于f*(s)。又由于OPEN表中f值小于f*(s)的節(jié)點(diǎn)，總是被A*擴(kuò)展的，因此從OPEN表中選擇那些f值小于fm的節(jié)點(diǎn)（這些節(jié)點(diǎn)的f值也必然小于f*(s)），按照g值的大小優(yōu)先擴(kuò)展，只是改變了部分節(jié)點(diǎn)的擴(kuò)展次序，不會(huì)多擴(kuò)展節(jié)點(diǎn)第6題答：如下的知識(shí)可以幫助求解該問(wèn)題：（1）序列中，偶數(shù)在偶數(shù)位置，奇數(shù)在奇數(shù)位置；（2）第五個(gè)數(shù)為5。綜合數(shù)據(jù)庫(kù)：用一個(gè)1到9的序列表示：N={x}，其中x為1到9的數(shù)字之一。規(guī)則集：r1:IFlen(N)=4THEN{x}∪{5}r2:IFlen(N)為偶數(shù)andn=In(1,3,7,9)THEN{x}∪{n}r3:IFlen(N)為奇數(shù)andn=In(2,4,6,8)THEN{x}∪{n}其中l(wèi)en(N)為求序列的長(zhǎng)度，In(a,b,c,d)為取a、b、c、d之一。初始