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

人工智能技术课程设计报告学号：姓名：课程设计题目：货郎担（旅行商）问题：设有n个城市，城市之间均有道路，一个旅行商从某城市出发，经过其余n-1个城市一次且仅一次，最后回到出发的城市，他如何走才能使他所走的路程最短？用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)=<h*(n)（h*(n)为实际问题的代价值）。 在旅行商问题中 节点（A...XY）的代价=起始城市到X城的代价+X城到Y城的代价其中的代价可以是距离，费用或者时间等 节点（A…XY）的启发值=（城市总数-已访问的城市数-1）*min{所有两城之间的代价} 在程序中的实现： p->gvalue=p_min->gvalue+relation[p_min->num-1][i]; p->hvalue=min*(number-p->level-1); p->fvalue=p->gvalue+p->hvalue;其中gvalue:g(n)hvalue:h(n)fvalue:f(n)p_min->gvalue:起始城市到X城的代价relation[p_min->num-1][i]:一个二维数组，X城到Y城的代价min:min{所有两城之间的代价}number:城市总数p->level:城市节点所处于搜索树的层次，和已访问的城市数同值 在本程序中定义一个结构体node用于表示城市节点： structnode{ intnum; intfvalue;//f值 intgvalue;//g值 inthvalue;//h值 intlevel;//层 structnode*parent;//父节点 structnode*next;//后继 structnode*front;//前驱};定义一个结构体final_path表示Open表和Bestpath表structfinal_path{ structnode*head; structnode*tail;}Open,Bestpath;其中Open表用于存放扩展出来的节点Bestpath表用于在程序的末尾存放最佳路径测试数据的输入使用邻接矩阵表示完全图使用二维数组relation[100][100]存放程序流程：将path数组中元素值置下标值：path[i]=i+1按要求输入邻接矩阵默认从第一个点开始搜索，并将path[0]=-1，表示该点已被纳入路径扩展刚刚被纳入路径的节点，扩展的方法为在path数组中搜索值不为-1的元素，为之创建节点写入数据（包括g值,h值,f值,parent节点）并纳入Open表中在Open表中搜索f值最小的节点确定为当前的最优路径点p_min,并且将上一次的最优路径点所在的路径上所有节点的path表中的元素值改为其下标值，表示删除原路径，同时将p_min所在的路径上所有节点的path表中元素值改为-1，表示创建新路径。回第4步循环，直至path表中所有的元素值均为-1退出循环由此获得最后一次的最优路径点，利用结构体中的parent指针得到最佳路径，并将路径存放在Bestpath表中输出最佳路径程序退出。程序缺陷： 由于专注于算法的实现，没有设置输入不合法的报错。 所以若要获得正确的结果，在输入路径点个数和邻接矩阵时要正确输入程序截图：（以5个路径点为例） 测试用例： 提供四组测试用例（邻接矩阵表示完全图），路径点个数分别是4，5，5，6 第一组：0213204114013110路径如下:A-->C-->D-->B-->A第二组：0127510443240127410353230路径如下:A-->B-->E-->C-->D-->A第三组：0534450354330544550344430路径如下:A-->C-->B-->E-->D-->A第四组：011111101111110111111011111101111110路径如下:A-->B-->C-->D-->E-->F-->A心得体会： 在这次课程设计中，我第一次使用A*算法，遇到的问题还是不少的 旅行商问题在以前接触过，当时解决的时候使用的是另外一种算法。 A*算法中最让我头疼的地方就是h(n)的设计，要满足h(n)<h*(n),在最初，我使用了H(n)=max*(number-p->level-1),出来的结果并不一定是最优路径，后来我发现问题处在max上面，使用max使得算法变得很简单，但也不完善，使得搜索树是一路往下走，没有了回溯的可能性，我将max换成了min，这样就可以满足h(n)<h*(n)，使之得到正确的结果。 在写程序中，定义的Bestpath表本来目的是存放每次搜索出来的当前最优路径点，后来发现因为不可避免出现算出的最优路径点与前一个路径点不在同一分支上，造成回溯，所以放弃使用Bestpath实时存放最优路径点，而是在结构体node中增加了parent指针，利用该指针构成链表存放路径，并且在每次找到新节点的时候删除原路径，同时创建新路径。最终只要得到最优路径即可。核心代码：structnode{ intnum; intfvalue;//f值 intgvalue;//g值 inthvalue;//h值 intlevel;//层 structnode*parent;//父节点 structnode*next;//后继 structnode*front;//前驱};structfinal_path{ structnode*head; structnode*tail;}Open,Bestpath;voidmain(){ intrelation[100][100];//邻接矩阵 intpath[100];//路径点集合 inti,j,number;//number路径点的数目 intmax=0; //存放最大值,用于计算h值 intmin;//存放最小值,用于计算h值 intcount;//用于计数 cout<<"输入路径点的数目："; cin>>number; for(i=0;i<number;i++) { path[i]=i+1;//用1，2，3，4.....来表示路径点 } for(i=0;i<number;i++) {//输入邻接矩阵 for(j=0;j<number;j++) { cin>>relation[i][j]; if(relation[i][j]>max)max=relation[i][j]; } } min=max;//初始化min，使其为所有路径中的最大值 for(i=0;i<number;i++) { for(j=0;j<number;j++) { if(relation[i][j]==0)continue; else { if(min>relation[i][j]) min=relation[i][j]; } } }//设置min为所有路径中的最小值 structnode*p0=newstructnode; p0->level=0; p0->num=1;//A点 p0->parent=NULL; path[0]=-1;//默认从第一个路径点开始搜索 Open.head=newstructnode; Open.tail=newstructnode; Open.head->next=Open.tail; Open.tail->front=Open.head;//初始化Open表 structnode*p1,*p2; structnode*p_min; structnode*p_temp; p1=Open.head; p2=Open.tail; //p1,p2用于确定节点插入Open表的位置 for(i=1;i<number;i++)//对A节点进行扩展，建立搜索树的第一层 {//插入节点 structnode*p; p=newstructnode; p->num=path[i]; p->level=1;//第一层 p->gvalue=relation[0][i];//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; path[p_min->num-1]=-1;//path中不为-1的个数为未到达路径点 //扩展找到的路径点（从第二层level=2开始进入循环） while(1) { for(i=0,count=0;i<number;i++) { if(path[i]==-1) { count++; } } if(count==number)break;//path数组中所有元素均为-1,则退出 else { p1=Open.tail->front; p2=Open.tail; for(i=0;i<number;i++) { if(path[i]!=-1) { structnode*p; p=newstructnode; p->num=path[i]; p->level=p_min->level+1;//由最优路径点的level确定子节点的level p->gvalue=p_min->gvalue+relation[p_min->num-1][i]; 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; } } } structnode*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) {//撤销上一次路径 path[p->num-1]=p->num; p=p->parent; } p=p_min;//新找到的最优路径点 while(p!=NULL) {//重配置新路径 path[p->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=newstructnod