实验一：搜索算法问题求解
一、实验目的
1. 了解4种无信息搜索策略（宽度优先搜索、一致代价搜索、深度优先搜索、迭代加深的深度优先搜索）和2种有信息搜索策略（贪婪优先最佳优先搜索、A*搜索）的算法思想以及基本原理； 2. 能够运用计算机语言实现这几种搜索算法； 3. 应用搜索算法解决罗马尼亚问题；
4. 能够通过实验比较分析各种搜索算法的优劣； 5. 能够设计新的启发式函数并进行性能分析；
二、实验的硬件、软件平台 硬件：计算机
软件：操作系统；WINDOWS 2000 应用软件：C,Java或者MATLAB
三、实验内容及步骤
图一：罗马尼亚地图
3.1：无信息搜索算法
1、根据图一创建搜索树，以Arad为初始状态，Bucharest为目标状态； 2、实现深度优先搜索的树搜索算法并记录搜索路径；
3、迭代加深的深度优先搜索算法并记录搜索路径 4、实现一致代价搜索的图搜索算法并记录搜索路径。
3.2：有信息搜索算法
1、根据图一以Arad为初始状态，Hirsova为目标状态实现A*搜索，其中已知Bucharest为从Arad到Hirsova的必经之路，设计一个启发式函数并分析该函数的可采纳性和优势(与启发式函数定义为“Arad到Hirsova的直线距离”相比较)；
四、思考题
1、根据实验结果分析深度优先搜索，一致代价搜索，迭代加深的深度优先搜索算法的时间和空间复杂度。
2、根据实验结果分析A*搜索的性能。
3、指出无信息搜索策略和有信息搜索策略的不同并比较其性能。 4、分析3.2中的启发式函数的可采纳型与优势。
五、实验结果提交
实验结果主要包括如下部分：
1、
实验代码 1.1
对实验中每种算法单独对应一个程序文件(.cpp或者.java); 1.2
无信息搜索算法和有信息搜索算法各对应一个主函数(main),主函数中必须要有注释； 1.3
实验的中间结果必须在代码中显示出来(比如每种算法访问结点的顺序)，可以使用printf打印在命令行中，也可以用可视化窗口表示(可视化显示加分)
2、
实验报告
2.1 各种算法的基本原理 2.2 各中算法的实验结果
2.3 实验分析和思考题
实验结果采用电子版的提交方式发送至yuanjin@hnu.edu.cn，包括一个word文档的实验报告和实验代码，请按照如下方式和命名提交 ”智能1201高洁05.zip”或者”智能1201高洁05.rar”,提交时间为实验结束后的一周内，比如周二晚上实验，下周三之前必须提交.
六、实验成绩评定 实验代码 50%
1. 深度优先搜索代码 15%
2. 迭代加深的深度优先搜索算法 5% 3. 一致代价搜索代码 15% 4. A*搜索 15%
实验代码在课程时间内完成且正确给于满分，实验代码正确但带回家完成得分70%，实验代码不正确得分0%-50%(酌情给分)
实验报告 50%
1. 算法原理分析 10% 2. 实验结果正确性 20% 3. 实验分析与思考题 20%