pacman吃豆人

一、解决方法与必要分析

任务一：在 search.py 的 aStarSearch 方法中按照 A 算法补充 A 搜索代码，myHeuristic 方法中补充启发式函数代码，启发式函数尝试了两种形式，分别为曼哈顿距离和欧氏距离。经过实际运行发现，曼哈顿距离的效果略好于欧氏距离，搜索中展开的节点数更少。分析可知，由于精灵只能上下左右移动，曼哈顿距离能更好地预估精灵离终点的距离，故效果会更好。

```python for newState, action, cost in nowSuccessors: newActions = nowActions + [action] stateQueue.push((newState, newActions), problem.getCostOfActions(newActions) + heuristic(newState, problem)) return actions def myHeuristic(state, problem=None): " YOUR CODE HERE " x,y = state goalX,goalY = problem.getGoalState()

使用当前位置与目标位置之间的曼哈顿距离作为启发式函数

                                            return abs(x - goalX) + abs(y - goalY)

使用当前位置与目标位置之间的欧氏距离作为启发式函数

return math.sqrt(math.pow(x - goalX, 2) + math.pow(y - goalY, 2))

```

任务二：对于 FoodSearchProblem，在 searchAgent.py 的 foodHeuristic 方法中补充对应的启发式函数代码。分析使用的三个地图，发现 food 均为线状分布，很自然会想到先走到食物构成的线上，再沿着线一路吃掉所有食物。故启发式函数设计的思路就是如果在线上，那沿着线走的启发式函数值最小，如果不在线上，则离线上最近的状态的启发式函数值最小。可以使用曼哈顿距离来统一定义，若在线上，下一个食物所在的位置到最近的食物曼哈顿距离是最小的；若不在线上，离线上越近的位置到最近的食物曼哈顿距离也越小。由于距离使用曼哈顿距离表示，该启发式函数满足满足 admissible 和 consistent。因为由于精灵只能上下左右移动，且可能会受到墙的阻隔，曼哈顿距离一定小于等于实际的距离，该启发式函数满足 admissible；还是因为精灵只能上下左右移动，原状态累计的开销加走一步的开销加上走过一步后的状态的启发式函数值不可能小于原状态累积的开销加原状态的启发式函数值，故该启发式函数也满足 consistent。

但运行以后发现实际效果并不是很好，怀疑是继续沿食物线走的状态与离开食物线的状态区分不明显所致，故在原来的算法上做了一些修改，将两种情况完全区分开了，算法效果大大提升，但修改后的启发式函数既不满足 admissible 也不满足 consistent，只能作为一种针对特定问题的特化算法。

任务三：将算法直接应用于新的三个布局即可，不需要改动代码

二、实验效果

由于同一个地图不同启发式函数运行的结果中 Score 均相同，故在表格中只展示 Search nodes expanded

	bigMaze	openMaze	smallMaze
空启发式	620	682	92
曼哈顿距离	549	535	53
欧氏距离	557	550	56

对比可知，使用非空启发式函数以后，搜索过程中扩展的节点数减少了 12%-43%，且对于越小越简单的地图，减少的幅度越大，对于大且复杂的地图，曼哈顿和欧氏距离启发式函数的效果比较有限。

Search3 运行后无响应，超过三分钟仍未出结果。

实现后的启发式函数（未特化）

Search3 运行后无响应，超过三分钟仍未出结果。

由于同一个地图不同启发式函数运行的结果中 Score 均相同，故在表格中只展示 Search nodes expanded

	Search1	Search2	Search3
h=0	14	707	——
实现后的启发式函数（未特化）	12	538	——
特化后的启发式函数	9	120	217

对比可知，使用实现后的启发式函数以后，搜索过程中扩展的节点数有所减少，但对于过大过复杂的地图，该算法拓展的节点仍然过多，无法在短时间内给出解。特化后的启发式函数效果更为明显，搜索过程中扩展的节点数大幅减少，且对于越大越复杂的地图，减少的幅度越大，对于在 h=0 和未特化时均无响应的 Search3，特化后的启发式函数依然可以在 0.1s 内找到路径，效果十分明显，但由于不满足 admissible 和 consistent，该算法并不能称为一个好的启发式算法。