猴子摘香蕉问题的宽度优先和有界深度优先算法

猴子摘香蕉问题的宽度优先搜索和最大深度为5的有界深度优先搜索（注意：括号中的斜体字是我做的说明，不是答案的内容）解：设一个状态由四元组（W,X,Y,Z）来表示，其中：1.W代表猴子的位置，其取值可为a，b和c；2.X代表猴子和箱子的位置关系，取值为0和1，其中0表示猴子在箱子下，而1表示猴子在箱子上面；3.Y代表箱子的位置，其取值可为a，b和c；4.Z代表是否摘得香蕉，取值为0和1，其中0表示未摘得香蕉而1表示已经摘到了香蕉。则本问题的初始状态为（a，0，c，0），而目标状态为（b，1，b，1）(注意：目标状态写为(U,V,H,1)也可以，因为我们只关心摘到香蕉)。本问题中涉及的算符有四个，分别为1.移动：Goto（U），其中U可取a，b和c，其执行条件为X＝0（即猴子不在箱子上），其效果如下式(,0,,)goto()(,0,,)WYZUUYZ，其中，U＝a，b，c且UW≠（注意：加UW≠是为了减少后面状态图中节点到自身的弧；(,0,,)goto()(,0,,)WYZUUYZ表示在状态(,0,,)WYZ上执行Goto（U）操作，使得原状态变为状态(,0,,)UYZ）2.推箱子：Pushbox(U)，其中U可取a，b和c，其执行条件为W＝Y（猴子和箱子在同一个位置）且X＝0（猴子不在箱子上），其效果如下式(,0,,)Pushbox()(,0,,)VVZUUUZ，其中U,V＝a，b，c，且UV≠（注意：加UV≠的作用同上UW≠）3.攀爬：Climb，其执行条件为W=Y（猴子和箱子在同一个位置）且X＝0（猴子不在箱子上），其效果如下(,0,,)Climb(,1,,)UUZUUZ，其中U＝a，b或c4.摘香蕉：Grasp，其执行条件为W＝Y＝b（猴子和箱子都在b位置）,X=1（猴子在箱子上）且Z＝0（猴子未摘得香蕉），其效果如下(,1,,0)Grasp(,1,,1)bbbb。设在同一状态下，检查并应用可应用的必要算符的次序如下：goto(a),goto(b),goto(c),pushbox(a),pushbox(b),pushbox(c),climb,grasp.则宽度优先搜索树如下图所示，其中状态左上角的数字代表该状态被扩展的顺序（是“生孩子”的顺序而不是“出生”的顺序）：（标号为2的状态是第二个被扩展的，但是在该状态下，goto(b),push的3个算符，climb和grasp不满足应用条件，而应用goto(a)和goto(c)产生重复的状态，所以在该状态下，没有可以被应用并且需要被应用的算符，结果是：虽然扩展了该状态，但是该状态没有任何“儿子”。标号为6，7，8，9，10，11的状态也一样）使用最大深度为5的有界深度优先搜索算法形成的搜索树如下图所示：（附送一个，作业中没有要去大家画）