《A 算法实现旅行商问题 人工智能报告付代码.doc》由会员分享，可在线阅读，更多相关《A 算法实现旅行商问题 人工智能报告付代码.doc（17页珍藏版）》请在三一文库上搜索。
1、A 算法实现旅行商问题 人工智能报告，付代码一、问题描述旅行商问题常被称为旅行推销员问题，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。旅行商问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。二、知识表示1、A*算法概述A*算法是N.Nillson于1971年提出的一种有序搜索算法,该算法被认为是求解人工智能问题的最成功的技术理论之一。Nillson指出对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,
2、应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值，并有f*(n)=g*(n)+h*(n)。假设f函数是对f*函数的一种估计,并有f(n)=g(n)+h(n)，其中g函数是对g*的估计，h函数是对h*的一种估计。f(n)包括两个部分，其中g(n)表示到达n节点时，已付出代价的估计；而h(n)表示从n节点到达目标节点ti将要付出代价的估计。按f(n)
3、=g*(n)+h*(n)的值来排序OPEN表的节点，f值小者优先。通常称这种算法为A算法。在A算法的基础上，进一步限制h(n)函数，使得搜索图中的每一个节点n，能满足h(n)=h*(n)、称h函数取h*的下界。这种算法叫A*算法。2、A*算法的状态所谓状态,是指在一定的时空范围内，问题所涉及的人、物、时间等的布局关系。通常把问题的初始布局关系称为初始状态，问题解决时到达的状态叫目标状态。这两个状态之间存在差异，如何从初始状态到达目标状态就是对问题求解。在状态空间法中问题的求解通常是从初始状态到达目标状态的一条最佳路径，这条路径依靠搜索算法在状态空间中寻找，这就是状态空间法的核心所在。在旅行商问
4、题中，初始状态就是旅行商在A城市准备出发送货，目标状态就是旅行商将所有的货送出归来到A城市。状态空间就是旅行商可以走的所有路径，本实验的解就是最短距离的路径。3、估计函数的意义对于某一已到达的现行状态,假设现在的现行状态是从A走到C(一共五个城市，需走过B、C、D、E)，那么下面可以走B、D、E，如果继续走B就表示为A-C-B，那么在OPEN表里，即可选定活路径就有六种选择：(1)A-C-B；(2)A-C-D；(3)A-C-E；(4)A-B；(5)A-D；(6)A-E。为什么有的是B、B?在这里B的层数是2层，就是第二步走的是B；而B的层数是3层，就是第三步走的是B。在OPEN表了的一个节点代
5、表一条路径，而非简单的代表一个城市结点，所以在里面你会看到不同B的表现形式。对OPEN里的每一个节点做评估函数F分为两部分G和H：G=未走的城市数目前的最小距离；未走的的城市数=(总城市数+1)-目前城市的层数。为什得加1，因为最后得走回初始城市，所以总路径的城市数为总城市数+1。假设从A城市走到X城市，又走到Y城市，所以H可表示为：H=A到X的距离+X到Y的距离；F=G+H；计算OPEN表里每个节点的F值，F值最小的节点作为活路径，从OPEN表中删除，放到CLOSE表里。三、算法实现1、数据结构typedef struct _nodeint f；/f值int g；/g值int h；/h值in
6、t level；/第几次走到这个点(important)int parent；/父城市；int city；/city num；node；使用node结构体表述每一个城市。typedef struct _liststruct _list*next；struct _list*pre；struct _list*parent；/父城市节点指针node city_node；nodelist,*nodeptr；使用nodelist,*nodeptr描述路径，城市结点与城市结点的关系。typedef struct _ttablestruct _ttable*_this；/this指针nodelist ope
7、n；/open表,nodelist close；/close表,(仓库)/一些操作nodeptr(*add_to_open)(int)；nodeptr(*find_least_f)(void)；void(*move_to_close)(nodeptr ptr)；void(*print_path)(nodeptr ptr)；ttable；Ttable相当一个总表，相当于面向对象的一个类，成员变量有OPEN表和CLOSE表，成员函数有nodeptr(*add_to_open)(int)、nodeptr(*find_least_f)(void)、void(*move_to_close)(nodept
8、r ptr)、void(*print_path)(nodeptr ptr)。2、程序流程(1)读取输入的城市距离的临界矩阵。(2)构造ttable,初始化，调用ttable*table_constructor()函数，申请空间，将OPEN、CLOSE表设为NULL；(3)默认第一个城市A放到OPEN表，将A城市标识设为-1，表示在当前最短路径里，A的层数设为1，A的F，H，G值初始化为0，更新最优路径临时指针指向A节点。(4)OPEN表F值最小的节点作为新的最优节点城市。搜索与最优节点相邻且不在当前最短路径里的城市放到OPEN表，并将其父指针指向最优节点，把此时的最优节点城市放到CLOSE表里
9、。(5)判断最优路径临时指针是否指向前最优路径节点，如果不同，将最优路径临时指针指向当前最优节点，并撤销旧的最优路径，根据新的最优临时指针新建最优路径。(6)循环第四部，直到最优路径上的节点数为城市数+1。(7)输出最短路径，析构ttable。四、实验结果分析(1)(2)(3)经过多种测试，结果为最优解。五、程序清单#include stdio.h#include malloc.h#include stdlib.h#include memory.h#define MAX_INT 99999999 typedef struct _nodeint f；/f值int g；/g值int h；/h值in
10、t level；/第几次走到这个点(important)int parent；/父城市；int city；/city num；node；typedef struct _liststruct _list*next；struct _list*pre；struct _list*parent；/父城市节点指针node city_node；nodelist,*nodeptr；nodeptr _add_to_open(int)；nodeptr _find_least_f()；void _print_path(nodeptr ptr)；void _move_to_close(nodeptr ptr)；nod
11、eptr _remove_from_open(nodeptr ptr)；void _add_to_close(nodeptr ptr)；typedef struct _ttablestruct _ttable*_this；/this指针nodelist open；/open表,nodelist close；/close表,(仓库)/一些的操作nodeptr(*add_to_open)(int)；nodeptr(*find_least_f)(void)；void(*move_to_close)(nodeptr ptr)；void(*print_path)(nodeptr ptr)；ttable；
12、int map100100；int b_path100；/best_path；ttable*table=NULL；ttable*table_constructor()/构造一个table实体table=(ttable*)malloc(sizeof(ttable)；memset(table,0,sizeof(ttable)；table-open.next=NULL；table-close.next=NULL；table-open.city_node.parent=-1；table-open.city_node.city=-1；table-close.city_node.parent=-1；tab
13、le-close.city_node.city=-1；table-add_to_open=_add_to_open；table-find_least_f=_find_least_f；table-move_to_close=_move_to_close；table-print_path=_print_path；table-_this=table；return table；void*table_destructor(ttable*table)/析构一个类if(table！=NULL)nodeptr p=table-_this-open.next；nodeptr q=NULL；while(p)q=p
14、-next；free(p)；p=q；p=table-_this-close.next；while(p)q=p-next；free(p)；p=q；free(table)；table=NULL；nodeptr _add_to_open(int i)/添加到OPEN表/放在第一个位置nodeptr p=NULL；p=(nodeptr)malloc(sizeof(nodelist)；memset(p,0,sizeof(nodelist)；if(p=NULL)return p；p-next=NULL；p-parent=NULL；p-city_node.parent=-1；p-city_node.city
15、=i；p-city_node.level=0；p-city_node.f=0；p-city_node.g=0；p-city_node.h=0；p-next=table-_this-open.next；p-pre=&table-_this-open；if(table-_this-open.next)table-_this-open.next-pre=p；table-_this-open.next=p；return p；void _add_to_close(nodeptr ptr)/添加到close表ptr-next=table-_this-close.next；ptr-pre=&table-_t
16、his-close；if(table-_this-close.next)table-_this-close.next-pre=ptr；table-_this-close.next=ptr；nodeptr _remove_from_open(nodeptr ptr)/从OPEN表中移除，不删除ptr-pre-next=ptr-next；if(ptr-next)ptr-next-pre=ptr-pre；return ptr；nodeptr _find_least_f()/在OPEN表中找出最小的F节点int least=MAX_INT；nodeptr p,q=NULL；p=table-_this-
17、open.next；q=p；while(p)if(p-city_node.f least)q=p；least=p-city_node.f；p=p-next；return q；void _move_to_close(nodeptr ptr)/从OPEN移到CLOSE _remove_from_open(ptr)；_add_to_close(ptr)；void _print_path(nodeptr ptr)/打印路径int least；if(ptr=NULL)return；least=ptr-city_node.f；printf(the best path is：)；printf(A)；ptr=
18、ptr-parent；while(ptr)printf(%c,ptr-city_node.city+65)；ptr=ptr-parent；printf(nthe shortest length is%dn,least)；int main()int num,min=MAX_INT；int i,j,k,count；int tmpf,tmph,tmpg；ttable*table=(ttable*)table_constructor()；/构造nodeptr ptr=NULL,ptr_p=NULL,ptr_c=NULL；nodeptr l_ptr=NULL；/the pointer of last b
19、est path；/input city doprintf(请输入城市节点个数：2=节点个数99n)；scanf(%d,&num)；while(num=99|num=1)；printf(请输入节点之间的距离矩阵：n)；for(i=0；i num；i+)for(j=0；j num；j+)scanf(%d,&mapij)；if(i！=j&min mapij)min=mapij；/最后回到A mapnumnum=map00；for(i=0；i num；i+)mapnumi=map0i；mapinum=mapi0；table-add_to_open(0)；while(1)ptr_p=table-fin
20、d_least_f()；/当前最好节点,从最好节点回退肯定是最好路径table-move_to_close(ptr_p)；/move to close table and save it；if(l_ptr&l_ptr！=ptr_p)/更新最好路径while(l_ptr！=NULL)b_pathl_ptr-city_node.city=0；l_ptr=l_ptr-parent；l_ptr=ptr_p；while(l_ptr！=NULL)b_pathl_ptr-city_node.city=1；l_ptr=l_ptr-parent；l_ptr=ptr_p；for(i=0,count=0；i=num
21、；i+)if(b_pathi)count+；if(count=num+1)/all city in best path,A in twice：First And Last.break；if(count=num)/left one,which?Last A.Because we have never changed the value of b_pathnum.ptr_c=table-add_to_open(num)；/把它添加进开启列表中ptr_c-city_node.parent=ptr_p-city_node.city；/把当前作为这的父节点ptr_c-city_node.level=pt
22、r_p-city_node.level+1；/他是父节点的下一层。ptr_c-parent=ptr_p；ptr_c-city_node.g=ptr_p-city_node.g+mapnumptr_p-city_node.city；/g ptr_c-city_node.h=min*(num-ptr_c-city_node.level)；/h ptr_c-city_node.f=ptr_c-city_node.g+ptr_c-city_node.h；/felsefor(i=0；i num；i+)/对邻近的路径计算if(i！=ptr_p-city_node.city&mapij！=-1)if(！b_
23、pathi)/如果它不在最短路径中ptr_c=table-add_to_open(i)；/把它添加进开启列表中ptr_c-city_node.parent=ptr_p-city_node.city；/把当前作为这的父节点ptr_c-city_node.level=ptr_p-city_node.level+1；/他是父节点的下一层。ptr_c-parent=ptr_p；ptr_c-city_node.g=ptr_p-city_node.g+mapiptr_p-city_node.city；/g ptr_c-city_node.h=min*(num-ptr_c-city_node.level)；/h ptr_c-city_node.f=ptr_c-city_node.g+ptr_c-city_node.h；/ftable-print_path(l_ptr)；table_destructor(table)；return 0；MSN空间完美搬家到新浪博客！