人工智能及其应用-推销员旅行问题

1、人工智能及其应用-推销员旅行问题一、问题描述:一个推销员计划出访推销产品。从一个城市（如A）出发, 访问每个城市一次，且最多一次，然后返回城市 A,要求寻找最短路线， 如图所示。、把图形建立成加权图形的邻接数组.如下1(A)2(B)3(C)4(D)5(E)1(A)07610132(B)OO0710103(C)OOOO0594(D)OOOOOO065(E)OOOOOOOO0/ 定义最大数/定义顶点数,A顶点重复2次/ 定义邻接边数/ 图形邻接数组/ 输入数据/ 查找记录 / 距离总和/ 最小边/ 最小边的顶点/ 边数/ 初始边数/ 初始顶点/ 计算初始距离之DistanceBegin=0;/ 起

2、始顶点的距离为printf(Vertice);for(i=1;iVertexNum;i+) printf(%5d,i); printf(n);printf(Step %d：,Edges);/ 输出顶点数据三、程序如下：（在程序中，将*设为一个极大值999）#define Max 999#define VertexNum 6#define EdgeNum 9 int GraphVertexNumVertexNum;int EdgeEdgeNum3= 1,2,7,1,3,6,1,4,10,1,5,13, 2,3,7,2,4,5,2,5,10, 3,4,5,3,5,9,;int VisitedVer

3、texNum;int DistanceVertexNum;void Dijkstra(int Begin)int MinEdge;int Vertex;int i,j;int Edges;Edges=1;VisitedBegin=1;for(i=1;iVertexNum;i+)和Distancei=GraphBegini;for(i=1;iVertexNum;i+) printf(%5d,Distancei); printf(n);/ 输出距离总和数据while(Edges(VertexNum-1)Edges+;MinEdge=Max;for(j=1;jDistancej)Vertex二j;找

4、出最小边的顶点MinEdge=Distancej; /找出最小边的距离总和 VisitedVertex=1;/将最小边的顶点设为已查找printf(Step %d:,Edges);for(j=1;jVertexNum;j+)/ 找出未查找顶点的最小距离总和if(Visitedj=0&(DistanceVertex+GraphVertexjDistancej)Distancej=DistanceVertex+GraphVertexj; printf(%5d,Distancej);printf(n); void Print_M_Graph()/ 输出邻接数组数据int i,j;printf(Ver

5、tice); for(i=1;iVertexNum;i+)printf(%5d,i);printf(n);for(i=1;iVertexNum;i+) printf(%5d ,i); for(j=1;jVertexNum;j+) printf(%5d,Graphij);printf(n);/ 以邻接数组建立图形void Create_M_Graph(int Vertice1,int Vertice2,int Weight) GraphVertice1Vertice2=Weight;/ 主程序void main()int BeginVertex=1;/ 清除查找记录/ 清除数组数据int i,j;for(i=0;iVertexNum;i+)Visitedi=0;for(i=0;iVertexNum;i+) for(j=0;jVertexNum;j+) Graphij=Max;for(i=0;iEdgeNum;i+)/ 调用建立邻接数组Create_M_Graph(Edgei0,Edgei1,Edgei