人工智能实验2 旅行商问题
实验课名称：人工智能原理与应用
实验项目名称：旅行商问题
专业名称：计算机科学与技术（交通信息）
班级：24020804
学号：2402080423
学生姓名：邢洪伟
教师姓名：慕晨
2010年12月20日
一、实验名称：旅行商问题
二、实验目的：用OPEN 表和CLOSED 表解决搜索问题 三、实验要求：
1、必须使用OPEN 表和CLOSED 表
2、明确给出问题描述、系统初始状态、目标状态和启发式函数
3、除了初始状态以外，至少搜索四层
4、给出解路径（解图）
四、实验原理：启发式搜索。

其基本思想是优先扩展路径耗散最小的节点，对于任意节点n ，用f(n)来表示n 到初始节点的路径耗散，即代价。

五、 实验内容：旅行商问题 1.问题描述
设西安、太原、北京、济南、郑州、南京、重 庆、武汉、上海、杭州十个城市，旅行者从西安 出发，到达城市上海，路径长度如下图图所示， 走怎样的路线路径最短？
2.启发式函数：f(n)=h(n)
其中h(n)表示相邻两城市间的路径长度 3．实验实现：
西安8
太原9 重庆7 郑州 5 武汉5.5
北京 8 武汉5.5 济南4.5 南京2 杭州 1.5
上海
西安
郑州
上海
北京
太原
武汉南京
杭州
重庆济南
OPEN 表
CLOSED 表
六、 实验体会：
通过本次用OPEN 表和CLOSED 表解决搜索问题的实验，让我对启发式搜索有了进一步的了解。

启发式搜索，也称为有信息搜索，借助问题的特定知识来帮助选择搜索方向；在搜索过程中对待扩展的每一个节点进行评估，得到最好的位置，再从这个位置进行搜索直到目标。

本次实验中采用的启发式函数为f(n)=h(n),巧妙地利用了旅行费最少这一点，使得搜索变得简单。