人工智能技术课程设计报告.doc

人工智能技术人工智能技术课程设计报告课程设计报告学号：学号：姓名：姓名：课程设计题目：课程设计题目：货郎担（旅行商）问题：货郎担（旅行商）问题：设有设有 n n 个城市，城市之间均有道路，一个旅行商从某城市出发，经过其余个城市，城市之间均有道路，一个旅行商从某城市出发，经过其余 n-1n-1 个城市个城市 一次且仅一次，最后回到出发的城市，他如何走才能使他所走的路程最短？一次且仅一次，最后回到出发的城市，他如何走才能使他所走的路程最短？ 用用 A*A*算法实现，语言不限算法实现，语言不限算法实现算法实现：本程序使用 A*算法实现 A*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策 略设计的问题中。而 A*算法最为核心的部分，就在于它的一个估值函数的设计上： f(n)=g(n)+h(n) 其中 f(n)是每个可能试探点的估值，它有两部分组成：一部分为 g(n)，它表示从起始 搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示） 。另一部分，即 h(n)，它 表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。 一种具有 f(n)=g(n)+h(n)策略的启发式算法能成为 A*算法的充分条件是： 1) 搜索树上存在着从起始点到终了点的最优路径。 2) 问题域是有限的。 3） 所有结点的子结点的搜索代价值>0。 4） h(n)=gvalue=p_min->gvalue+relationp_min->num-1i;p->gvalue=p_min->gvalue+relationp_min->num-1i; p->hvalue=min*(number-p->level-1);p->hvalue=min*(number-p->level-1); p->fvalue=p->gvalue+p->hvalue;p->fvalue=p->gvalue+p->hvalue; 其中 gvaluegvalue:g(n)hvaluehvalue:h(n) fvaluefvalue:f(n) p_min->gvaluep_min->gvalue:起始城市到 X 城的代价 relationp_min->num-1irelationp_min->num-1i:一个二维数组，X 城到 Y 城的代价minmin: min所有两城之间的代价 numbernumber: 城市总数 p->levelp->level:城市节点所处于搜索树的层次，和已访问的城市数同值在本程序中 定义一个结构体 node 用于表示城市节点：struct node int num;int fvalue;/f 值 int gvalue;/g 值 int hvalue;/h 值 int level; /层 struct node *parent;/父节点 struct node *next;/后继 struct node *front;/前驱; 定义一个结构体 final_pathfinal_path 表示 Open 表和 Bestpath 表struct final_path struct node *head; struct node *tail; Open,Bestpath; 其中 OpenOpen 表用于存放扩展出来的节点 BestpathBestpath 表用于在程序的末尾存放最佳路径测试数据的输入使用邻接矩阵表示完全图 使用二维数组 relation100100relation100100存放程序流程：程序流程： 1 将 path 数组中元素值置下标值：pathi=i+1 2 按要求输入邻接矩阵 3 默认从第一个点开始搜索，并将 path0=-1，表示该点已被纳入路径 4 扩展刚刚被纳入路径的节点，扩展的方法为在 path 数组中搜索值不为-1 的元 素，为之创建节点写入数据（包括 g 值,h 值,f 值,parent 节点）并纳入 Open 表中 5 在 Open 表中搜索 f 值最小的节点确定为当前的最优路径点 p_min,并且将上一 次的最优路径点所在的路径上所有节点的 path 表中的元素值改为其下标值， 表示删除原路径，同时将 p_min 所在的路径上所有节点的 path 表中元素值改 为-1，表示创建新路径。 6 回第 4 步循环，直至 path 表中所有的元素值均为-1 退出循环 7 由此获得最后一次的最优路径点，利用结构体中的 parent 指针得到最佳路径， 并将路径存放在 Bestpath 表中 8 输出最佳路径 9 程序退出。程序缺陷：程序缺陷： 由于专注于算法的实现，没有设置输入不合法的报错。 所以若要获得正确的结果，在输入路径点个数和邻接矩阵时要正确输入 程序截图：（以程序截图：（以 5 5 个路径点为例）个路径点为例）测试用例测试用例：提供四组测试用例（邻接矩阵表示完全图） ，路径点个数分别是 4，5，5，6 第一组： 0 2 1 3 2 0 4 1 1 4 0 1 3 1 1 0 路径如下: ACDBA第二组：0 1 2 7 5 1 0 4 4 3 2 4 0 1 2 7 4 1 0 3 5 3 2 3 0 路径如下:ABECDA第三组：0 5 3 4 4 5 0 3 5 4 3 3 0 5 4 4 5 5 0 3 4 4 4 3 0路径如下:ACBEDA第四组：0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 路径如下:ABCDEFA心得体会：心得体会：在这次课程设计中，我第一次使用 A*算法，遇到的问题还是不少的 旅行商问题在以前接触过，当时解决的时候使用的是另外一种算法。 A*算法中最让我头疼的地方就是 h(n)的设计，要满足 h(n)level-1),出来的结果并不一定是最优路径，后来我发现问题处在 max 上面，使用 max 使得算法变得很简单，但也不完善，使得搜索树是一路往下走，没有 了回溯的可能性，我将 max 换成了 min，这样就可以满足 h(n)>number; for(i=0;i>relationij; if(relationij>max)max=relationij; min=max;/初始化 min，使其为所有路径中的最大值for(i=0;irelationij) min=relationij; /设置 min 为所有路径中的最小值struct node *p0=new struct node; p0->level=0; p0->num=1;/A 点p0->parent=NULL; path0=-1;/默认从第一个路径点开始搜索Open.head=new struct node; Open.tail=new struct node; Open.head->next=Open.tail; Open.tail->front=Open.head;/初始化 Open 表struct node *p1,*p2; struct node *p_min; struct node *p_temp; p1=Open.head; p2=Open.tail; /p1,p2 用于确定节点插入 Open 表的位置for(i=1;inum=pathi; p->level=1;/第一层 p->gvalue=relation0i;/A 点到其他点的距离p->hvalue=min*(number-p->level-1); p->fvalue=p->gvalue+p->hvalue; p->parent=p0;p1->next=p; p->front=p1; p->next=p2; p2->front=p; p1=p;if(i=1)p_min=p1; else /寻找最优路径点if(p_min->fvalue>p1->fvalue)p_min=p1; p_temp=p_min; /在 Open 中删除找到的路径点，因为下面将要对它进行扩展p_min->front->next=p_min->next; p_min->next->front=p_min->front;pathp_min->num-1=-1; /path 中不为-1 的个数为未到达路径点/扩展找到的路径点（从第二层 level=2 开始进入循环）while(1) for(i=0,count=0;ifront; p2=Open.tail; for(i=0;inum=pathi; p->level=p_min->level+1;/由最优路径点的 level 确定子节点的level p->gvalue=p_min->gvalue+relationp_min->num-1i; p->hvalue=min*(number-p->level-1); p->fvalue=p->gvalue+p->hvalue; p->parent=p_min;p1->next=p; p->front=p1; p->next=p2; p2->front=p; p1=p; struct node *p=Open.head->next; i=1; while(p!=Open.tail) /从 Open 表中寻找if(i=1)p_min=p; else/寻找最优路径点if(p_min->fvalue>p->fvalue)p_min=p; i+; p=p->next; /找到最优路径点p=p_temp;/上一次的最优路径点while(p!=NULL) /撤销上一次路径pathp->num-1=p->num; p=p->parent; p=p_min;/新找到的最优路径点while(p!=NULL) /重配置新路径pathp->num-1=-1; p=p->parent; p_temp=p_min;/再次使得 p_temp 指向最优路径点，为下一次所用/在 Open 中删除找到的路径点p_min->front->next=p_min->next; p_min->next->front=p_min->front; /循环结束/初始化 Bestpath 表Bestpath.head=new struct node; Bestpath.tail=new struct node; Bestpath.head->next=Bestpath.tail; Bestpath.tail->front=Bestpath.head;p1=Bestpath.head; p2=Bestpath.tail;struct node *p; p=p_min; while(p!=NULL) /将路径顺序存入 Bestpath 表中p1->next=p;p->front=p1; p->next=p2; p2->front=p; p2=p;p=p->parent; /省略输出