精选优质文档-倾情为你奉上传教士与野人问题：传教士（M）与野人（C）数目均为五人，渡船（B）最多可乘3人，请定义一个启发函数，并给出相应的搜索树。解：定义启发函数h（n）=0; h（n）=M+C; h（n）=M+C-2B 只有h（n）=M+C-2B可满足h（n）h*（n），是满足A*条件的。分两种情况来讨论：先考虑船在左岸的情况，如果不考虑限制条件，至少需要（M+C-3）/2*2+1次，其中分子上的“-3”表示剩下的3个留待最后一次运过去。除以2是因为一个来回可以运过去2人，需（M+C-3）/2个来回，而来回数不能是小数，所以要取整。一个来回是两次，所以“*2”，而最后的“+1”，则表示将剩下的3个运过去需要一次摆渡。化简后为：（M+C-3）/2*2+1=M+C-2再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要一个人将船运往左岸，因此，对于状态（M，C，0），需要的摆渡数，相当于船在左岸的（M+1，C，1）或（M，C+1，1），所以需要的最少摆渡数为M+C+1-2+1=M+C。综合条件，需要的最少摆渡数为M+C-2B。
