人工智能课后习题.doc

2.18,语义网络2.72.12 解：首先建立棋盘变换的产生式规则。如果把棋盘的每一种布局看做是一个状态矩阵，本题就变成了从初始状态矩阵到目标状态矩阵的一种变化。 所谓棋盘状态的变化就是希望棋盘上空格周围的棋子能走进空格，这也可以理解为移动空格，只要实现空格的上、下、左、右四种移动即可。可通过建立四个条件一操作型的产生式规则，来实现这四种移动。 设Sij为状态矩阵中的第i行和第j列的数码，i0、j0表示空格所在的行和列，如果在状态矩阵中用0来表示空格的话，则建立如下四条产生式规则： R1:if (jo 11) then begin Siojo: = Sio(jo-1); Sio(jo-1): =0 end 空格左移 R2:if (io 11) then begin Siojo: = S(io-l)jo; S(io-l)jo: =0 end 空格上移 R3:if (Jo + 13) then begin Siojo: = Sio(jo+1); Sio(jo+1): = 0 end 空格右移 R4: if (io + 13) then begin Siojo: = S(io+l)jo; S(io+l)jo: = 0 end 空格下移 然后,建立综合数据库。将棋盘的布局表示为状态距阵的形式存入综合数据库，例如，可以将本题的初始布局和目标布局以矩阵形式表示为： 综合数据库中,存放着初始状态矩阵和目标状态矩阵以及变换过程中的中间矩阵。 在建立了规则集和综合数据库后，就可以按照产生式规则进行状态变换，实现推理求解。在进行推理时，可能会有多条产生式规则的条件部分和综合数据库中的已有事实相符，这样就有可能激活多条规则。究竟采用哪一条规则作为启用规则，这就是冲突解决策略问题。解决冲突的策略有专一性排序、规则顺序等多种，也可以使用一些启发性的信息，根据具体问题选择。在本题中，我们采用一个启发式函数h(x)，它表示节点x所对应的棋盘中与目标节点对应的棋盘中棋子位置不同的个数。这里，综合数据库中的初始状态矩阵，能满足规则R1、R2、R4的条件，所以有三条匹配规则。利用启发式函数决定哪一条规则为启用规则。因为规则R4的启发式函数值h(x)=5，规则R1的h(x)=6，规则R2的h(x)=7，也就是说，规则R4所得到的新状态与目标状态差距最小，所以启用规则R4，依此类推，可以得到到达目标状态的规则执行序列如下： R4，R1，R2，R2，R1，R4，R3 其执行过程如图2.19所示。226解：用状态空间法进行表示。根据状态空间表示问题的步骤，问题求解如下： 第一步，定义问题状态的描述形式。 设Sk=(Nx，Ny，C)表示修道士和野人在河的左岸的状态。其中，Nx表示修道士在左岸的实际人数，Ny表示野人在左岸的实际人数，C用来指示船是否在左岸(C=1表示在左岸，C=0表示不在左岸)。 第二步，用所定义的状态描述形式把问题的所有可能状态都表示出来，并确定出问题的初始状态集和目标状态集。 对于状态Sk=(Nx，Ny，C)来说，由于Nx、Ny的取值有0、1、2、3四种可能，C的取值有0和1两种可能，所以，本问题所有可能的状态共有4*4*2=32种。各状态的形式描述如下： So=(3，3，1)， S1=(3，2，1)， S2=(3，1，1)， S3=(3，0，1)， S4=(3，3，0)， S5=(3，2，0)， S6=(3，1，0)， S7=(3，0，0)， S8=(2，3，1)， S9=(2，2，1)， S10=(2，1，1)，S11=(2，0，1)， S12=(2，3，0)，S13=(2，2，0)，S14=(2，1，0)，S15=(2，0，0) S16=(1，3，1)，S17=(1，2，1)，S18=(1，1，1)，S19=(1，0，1)， S20=(1，3，0)，S21=(1，2，0)，S22=(1，1，0)，S23=(1，0，0)， S24=(0，3，1)，S25=(0，2，1)，S26=(0，1，1)，S27=(0，0，1)， S28=(0，3，0)，S29=(0，2，0)，S30=(0，1，0)，S3l=(0，0，0)。 在这些状态中，由于有安全约束条件任何岸边野人的数量都不得超过传教士的数量(即NxNy)，所以只有20个状态是合法的，像(1，2，1)、(1，3，1)和(2，3，1)等都是不合法的状态。而由于这些不合法状态的存在，又会导致某些合法状态是不可到达的。这样，此问题总共只有16种可到达的合法状态，以下划线表示。 问题的初始状态集为：S=S0=(3，3，1)，目标状态集为：G=S31=(0，0，0) 第三步，定义一组用于状态变换的算符F。 定义算符L（i,j)表示划船将i个传教士和j个野人送到右岸的操作；算符R(i,j)表示划船从右岸将i个传教士和j个野人带回左岸的操作。由于过河的船每次最多载两个人，所以，i十j2，这样定义的算符组F中只可能有如下10个算符： F： L(1，0)，L(2，0)，L(1，1)，L(0，1)，L(0，2) R(1，0)，R(2，0)，R(1，1)，R(0，1)，R(0，2) 至此，该问题的状态空间(S，F，G)构造完成。这就完成了对问题的状态空间表示。 为了求解该问题，根据该状态空间的16种可到达合法状态和10种算符，构造它的状态转换图，如图226所示。 在图2.26所示的状态空间图中,每个节点只能取L、R操作之一，这取决于变量C的取值，即船是在左岸还是在右岸。若船在左岸(即C=1)，则只能取L操作，若船在右岸，则只能取R操作。 从初始节点(3，3，1)(状态So)到目标节点(0，0，0)(状态S31)的任何一条通路都是问题的一个解。其中： L(1，1)，R(1，0)，L(0，2)，R(0，1)，L(2，0)，R(1，1)，L(2，0)，R(0，1)，L(0，2)，R(0，1)，L(0，2) 是算符最少的解之一。227解：用状态空间法进行表示。根据状态空间表示问题的步骤，问题求解如下： 第一步，定义问题状态的描述形式。 以四元组Sk=(f，h，j，m)作为状态变量，表示农夫、狐狸、鸡和小米是否在左岸。每个元素可有两个取值1或0，1表示在左岸，0表示不在左岸。 第二步，用所定义的状态变量把问题的所有可能状态都表示出来，并确定出问题的初始状态集和目标状态集。 由于状态变量有4个元素，每个元素有2种取值，所以共有16种可能状态。各状态的形式描述如下： So =(1，1，1，1)，Sl =(1，1，1，0)，S2 =(1，1，0，1)，S3 =(1，1，0，0)， S4 =(1，0，1，1)，S5 =(1，0，1，0)，S6 =(1，0，0，1)，S7 =(1，0，0，0)， S8 =(0，1，1，1)，S9 =(0，1，1，0)，S10=(0，1，0，1)，S11=(0，1，0，0)， S12=(0，0，1，1)，S13=(0，0，1，0)，S14=(0，0，0，1)，S15=(0，0，0，0)。 问题的初始状态集为：S=S0=(1，1，1，1)， 目标状态集为：G=S15=(0，0，0，0)。 第三步，定义一组用于状态变换的算符F。 由于船上除了农夫外，每次只能载狐狸、鸡和小米中的一样，且每次农夫都必须在船上，故定义算符如下： L(f，j)表示从左岸将第j样东西送到右岸(j=1表示狐狸，j=2表示鸡，j=3表示小米，j=0表示除农夫外不载任何东西)，f表示农夫始终在船上。 R(f，j)表示从右岸将第j样东西带回左岸。 所以，所定义的算符组F中可能有8种算符： F：L(f，0)，L(f，1)，L(f，2)，I(f，3)，R(f，0)，R(f，1)， R(f，2)，R(f，3)。 这里要指出的是，操作算符中的f可以不要，也就是说，完全可以把操作算符定义成L(j)和R(j)。这里加上f是为了表示农夫总是在船上划船。 至此，该问题的状态空间(S，F，G)构造完成。这就完成了对问题的状态空间表示。 为了求解该问题，根据该状态空间的16种状态和8种算符，构造它的状态转换图，如图227所示。 在图227所示的状态转换图中，每个节点只能取L、R操作之一，这取决于状态变量中第一个元素f的取值。若f=1，表明农夫在