文档介绍：人工智能技术
课程设计报告
学号：
姓名：
年 月 日
课程设计题目：
货郎担（旅行商）问题：
设有个城市，城市之间均有道路，一个旅行商从某城市出发，经过其余个城市一次且仅一次，最后回到出发的城市，他如何走才能使他所走的路程最短？
用*算法实现，语言不限
算法实现：
本程序使用*算法实现
*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而*算法最为核心的部分，就在于它的一个估值函数的设计上：
()()()
其中()是每个可能试探点的估值，它有两部分组成：一部分为()，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。另一部分，即()，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。
一种具有()()()策略的启发式算法能成为*算法的充分条件是：
)      搜索树上存在着从起始点到终了点的最优路径。
)      问题域是有限的。
） 所有结点的子结点的搜索代价值>。
） ()<*() （*()为实际问题的代价值）。
在旅行商问题中
节点（）的代价起始城市到城的代价城到城的代价
其中的代价可以是距离，费用或者时间等
节点（…）的启发值（城市总数已访问的城市数）*{所有两城之间的代价}
在程序中的实现：
>>[>][];
>*(>);
>>>;
其中()
()
()
>:起始城市到城的代价
[>][]:一个二维数组，城到城的代价
: {所有两城之间的代价}
: 城市总数
>:城市节点所处于搜索树的层次，和已访问的城市数同值
在本程序中
定义一个结构体用于表示城市节点：
{
;
值
值
值
; 层
*父节点
*后继
*前驱
};
定义一个结构体表示表和表
{
*;
*;
};
其中
表用于存放扩展出来的节点
表用于在程序的末尾存放最佳路径
测试数据的输入使用邻接矩阵表示完全图
使用二维数组[][]存放
程序流程：
将数组中元素值置下标值：[]
按要求输入邻接矩阵
默认从第一个点开始搜索，并将[]，表示该点已被纳入路径
扩展刚刚被纳入路径的节点，扩展的方法为在数组中搜索值不为的元素，为之创建节点写入数据（包括值值值节点）并纳入表中
在表中搜索值最小的节点确定为当前的最优路径点,并且将上一次的最优路径点所在的路径上所有节点的表中的元素值改为其下标值，表示删除原路径，同时将所在的路径上所有节点的表中元素值改为，表示创建新路径。
回第步循环，直至表中所有的元素值均为退出循环
由此获得最后一次的最优路径点，利用结构体中的指针得到最佳路径，并将路径存放在表中
输出最佳路径
程序退出。
程序缺陷：
由于专注于算法的实现，没有设置输入不合法的报错。
所以若要获得正确的结果，在输入路径点个数和邻接矩阵时要正确输入
程序截图：（以个路径点为例）
测试用例：
提供四组测试用例（邻接矩阵表示完全图），路径点个数分别是，，，
第一组：
路径如下:
>>>>
第二组：
路径如下:
>>>>>