实验内容：

实验要求采用且不限于课程第四章内各种搜索算法此编写一系列吃豆人程序解决以下列出的问题1-8，包括到达指定位置以及有效的吃豆等。

代码下载地址：

search.zip

简介：

参考网址：http://ai.berkeley.edu/search.html内容，以下为实验简介。

基本代码和支持文件可以从search.zip中获取。其中，一些需要参考的文件如下：

需要编辑的文件：search.py和searchAgents.py

需要参考的文件：

pacman.py吃豆人游戏的程序。 文件包括一个描述”吃豆人”gamestate的类型。

game.py吃豆人游戏的运行逻辑. 文件包括以下类型AgentState, Agent, Direction, and Grid.

util.py搜索策略可以用到的数据结构.

可以忽略的支持性文件：graphicsDisplay.py graphicsUtils.py textDisplay.py ghostAgents.py keyboardAgents.pylayout.pyautograder.py   testParser.pytestClasses.py test_cases/ searchTestClasses.py

解压缩search.zip，在此目录下，运行以下指令可打开吃豆人游戏。

python pacman.py

运行python autograder.py可以帮助你对自己的程序打分。

searchAgents.py中最简单的Agent叫做GoWestAgent，一路向西，偶尔能实现目标：

python pacman.py --layout testMaze --pacman GoWestAgent

但是其不能实现转弯：

python pacman.py --layout tinyMaze --pacman GoWestAgent

如果程序卡死，可通过CTRL-c来终止。

此项目中用到的指令也都储存在commands.txt文件中，可用于复制和粘贴。

问题1：应用深度优先算法找到一个特定的位置的豆

首先，运行一下命令测试SearchAgent是不是正常工作：

python pacman.py -l tinyMaze -p SearchAgent -afn=tinyMazeSearch

然后，完成完整的通用算法帮助吃豆人规划路线。搜索算法的伪代码见附录。注意一个搜索节点不仅包含节点的状态，而且要包含构建搜索路径所需要的信息。

注意：所有的搜索函数必须返回一个从初始状态到目标状态的操作序列。所有操作必须合法（不能翻墙）。

注意：利用util.py文件中提供的Stack, Queue 和 PriorityQueue数据结构！这是自动评分系统的兼容性要求。

你的code应该能顺利解决以下问题：

python pacman.py -l tinyMaze -p SearchAgent

pythonpacman.py -l mediumMaze -p SearchAgent

python pacman.py -l bigMaze -z .5 -p SearchAgent

注意：因为不同的搜索方法的不同之处仅仅在于open表的排序不同，因此请定义一个通用的搜索算法解决问题1-4。提示：问题1-4的不同之处在于用不同的数据结构对open表进行排序。

问题2：宽度优先算法

利用宽度优先算法实现解决以上问题。并利用以下命令测试你的code：

pythonpacman.py -l mediumMaze -p SearchAgent -a fn=bfs

pythonpacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

问题3：代价一致算法

很多情况下，路径中的代价是可以改变的。完成代价一致搜索方法(search.py文件中的uniformCostSearch函数)，并用以下命令测试你得code：

pythonpacman.py -l mediumMaze -p SearchAgent -a fn=ucs

pythonpacman.py -l mediumDottedMaze -p StayEastSearchAgent

pythonpacman.py -l mediumScaryMaze -p StayWestSearchAgent

问题4：A* 算法

完成A*搜索方法(search.py文件中的aStarSearch函数)，利用曼哈顿距离作为启发函数，用以下命令测试你得code：

pythonpacman.py -l bigMaze -z .5 -p SearchAgent -afn=astar,heuristic=manhattanHeuristic

问题5：找到所有的角落

在角落迷宫的四个角上面有四个豆。这个搜索问题要求找到一条访问所有四个角落的最短的路径。

完成searchAgents.py文件中的CornersProblem搜索问题，你需要重新定义状态，使其能够表示角落是否被访问。用以下命令测试你得code：

pythonpacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem

pythonpacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem

提示：新的状态只包含吃豆人的位置和角落的状态。

问题6：角落问题（启发式）

构建合适的启发函数，完成searchAgents.py文件中的cornersHeuristic角落搜索问题。用以下命令测试你得code：

pythonpacman.py -l mediumCorners -p AStarCornersAgent -z 0.5

问题7：吃掉所有的豆子

用尽可能少的步数吃掉所有的豆子。完成searchAgents.py文件中的FoodSearchProblem豆子搜索问题。此问题利用之前A*算法可以很容易找到解，可用以下命令测试：

pythonpacman.py -l testSearch -p AStarFoodSearchAgent

构建合适的启发函数，完成searchAgents.py文件中的foodHeuristic豆子搜索（启发式）问题。用以下命令测试你得code：

pythonpacman.py -l trickySearch -p AStarFoodSearchAgent

问题8：次最优搜索

定义一个优先吃最近的豆子函数是提高搜索速度的一个好的办法。补充完成searchAgents.py文件中的AnyFoodSearchProblem目标测试函数，并完成searchAgents.py文件中的ClosestDotSearchAgent部分，在此Agent当中缺少一个关键的函数：找到最近豆子的函数。用以下命令测试你得code：

pythonpacman.py -l bigSearch -p ClosestDotSearchAgent -z .5

深度优先搜索：

   深度优先搜索采用堆栈寻找路径，首先从起始结点出发，判断是否为目标结点，若否，寻找与该结点的邻接点，先搜索一条分支上的所有节点，然后再去搜索起始节点的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否，则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则返回失败。

广度优先搜索：

属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止，且搜索出来的路径为最短路径。

代价一致算法：

扩展的是路径消耗g(n)最小的节点n,用优先队列来实现，对解的路径步数不关心，只关心路径总代价。即使找到目标节点也不会结束，而是再检查新路径是不是要比老路径好，确实好，则丢弃老路径。

A*算法：

公式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取：首先将起始结点S放入OPEN表，CLOSE表置空，算法开始时：

1、如果OPEN表不为空，从表头取一个结点n，如果为空算法失败。

2、n是目标解吗？是，找到一个解（继续寻找，或终止算法）。

3、将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表，并把S放入CLOSE表，同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法，回到1。