人工智能_(马少平_朱小燕_著)_清华大学出版社_课(5)

3，初始状态：(5, 0)

4，结束条件：(x, 1)，其中x表示不定。当然结束条件也可以写成：(0, 1)

3、对梵塔问题给出产生式系统描述，并讨论N为任意时状态空间的规模。

相传古代某处一庙宇中，有三根立柱，柱子上可套放直径不等的N个圆盘，开始时所有圆盘都放在第一根柱子上，且小盘处在大盘之上，即从下向上直径是递减的。和尚们的任务是把所有圆盘一次一个地搬到另一个柱子上去（不许暂搁地上等），且小盘只许在大盘之上。问和尚们如何搬法最后能完成将所有的盘子都移到第三根柱子上（其余两根柱子，有一根可作过渡盘子使用）。

求N＝2时，求解该问题的产生式系统描述，给出其状态空间图。讨论N为任意时，状态空间的规模。 答： 1，综合数据库 定义三元组：(A, B, C)

其中A, B, C分别表示三根立柱，均为表，表的元素为1～N之间的整数，表示N个不同大小的盘子，数值小的数表示小盘子，数值大的数表示大盘子。表的第一个元素表示立柱最上面的柱子，其余类推。 2，规则集

为了方便表示规则集，引入以下几个函数：

first(L)：取表的第一个元素，对于空表，first得到一个很大的大于N的数值。 tail(L)：取表除了第一个元素以外，其余元素组成的表。 cons(x, L)：将x加入到表L的最前面。 规则集：

r1: IF (A, B, C) and (first(A) < first(B)) THEN (tail(A), cons(first(A), B), C) r2: IF (A, B, C) and (first(A) < first(C)) THEN (tail(A), B, cons(first(A), C)) r3: IF (A, B, C) and (first(B) < first(C)) THEN (A, tail(B), cons(first(B), C)) r4: IF (A, B, C) and (first(B) < first(A)) THEN (cons(first(B), A), tail(B), C) r5: IF (A, B, C) and (first(C) < first(A)) THEN (cons(first(C), A), B, tail(C)) r6: IF (A, B, C) and (first(C) < first(B)) THEN (A, cons(first(C), B), tail(C)) 3，初始状态：（（1，2，...，N），（），（）） 4，结束状态：（（），（），（1，2，...，N））

问题的状态规模： 每一个盘子都有三中选择：在A上、或者在B上、或者在C上，共N个盘子，所以共有

4、对猴子摘香蕉问题，给出产生式系统描述。

一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到处走动，推移箱子，攀登箱子等）。设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为a，箱子位置为b，香蕉位置为c），如何行动可摘取到香蕉。 答： 1，综合数据库

定义5元组：（M, B, Box, On, H） 其中：

M：猴子的位置

种可能。即问题的状态规模为

。