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

（8）B向右跳过了一个W（可能同时包含一个B），此时： h(i)-h(j)=1, C(i,j)=1或2； （9）B向右跳过了两个W，此时： h(i)-h(j)=2, C(i,j)=2；

（10）B向左跳过了一个W（可能同时包含一个B），此时： h(i)-h(j)=-1, C(i,j)=1或2； （11）B向左跳过了两个W，此时： h(i)-h(j)=-2, C(i,j)=2； 纵上所述，无论是哪一种情况，具有: h(i)-h(j)≤C(i,j)

且容易验证h(t)=0，所以该h是单调的。由于h满足单调条件，所以也一定有h(n)≤h*(n)，即满足A*条件。

3、对1.4节中的旅行商问题，定义两个h函数（非零），并给出利用这两个启发函数用算法A求解1.4节中的五城市问题。讨论这两个函数是否都在h*的下界范围及求解结果。

答： 定义h1=n*k，其中n是还未走过的城市数，k是还未走过的城市间距离的最小值。 h2＝其中n是还未走过的城市数，ki是还未走过的城市间距离中n个最小的距离。 显然这两个h函数均满足A*条件。

，

4、2.1节四皇后问题表述中，设应用每一条规则的耗散值均为1，试描述这个问题h*函数的一般特征。你是否认为任何h函数对引导搜索都是有用的？

提示：对于四皇后问题，如果放一个皇后的耗散值为1的话，则任何一个解的耗散值都是4。因此如果h是对该耗散值的估计，是没有意义的。对于像四皇后这样的问题，启发函数应该是对找到解的可能性的评价。比如像课上讲到的，利用一个位置放皇后后，消去的对角线的长度来进行评价。

5、对N＝5，k≤3的M－C问题，定义两个h函数（非零），并给出用这两个启发函数的A算法搜索图。讨论用这两个启发函数求解该问题时是否得到最佳解。

答： 定义h1=M+C-2B，其中M，C分别是在河的左岸的传教士人数和野人人数。B＝1表示船在左岸，B＝0表示船在右岸。 也可以定义h2=M+C。

h1是满足A*条件的，而h2不满足。

要说明h(n)＝M+C不满足A*条件是很容易的，只需要给出一个反例就可以了。比如状态(1, 1, 1)，h(n)=M+C=1+1=2，而实际上只要一次摆渡就可以达到目标状态，其最优路径的耗散值为1。所以不满足A*的条件。

下面我们来证明h(n)＝M+C-2B是满足A*条件的。

我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要

摆渡次。其中分子上的"－3"表示剩下三个留待最后一次运过去。除以"2"是因为一

个来回可以运过去2人，需要个来回，而"来回"数不能是小数，需要向上取整，

这个用符号

表示。而乘以"2"是因为一个来回相当于两次摆渡，所以要乘以2。而最后的"＋1"，则表示将剩下的3个运