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

《人工智能及其应用-推销员旅行问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、人工智能及其应用-推销员旅行问题一、问题描述:一个推销员计划出访推销产品。从一个城市(如A)出发,访问每个城市一次,且最多一次,然后返回城市A,要求寻找最短路线,如图所示。ACBDE7101071369106105二、把图形建立成加权图形的邻接数组.如下1(A)2(B)3(C)4(D)5(E)1(A)07610132(B)∞0710103(C)∞∞0594(D)∞∞∞065(E)∞∞∞∞0三、程序如下:(在程序中,将∞设为一个极大值999)#defineMax999//定义最大数#defineVertexNum6//定义顶点数,A顶点重复2次#defineEdgeNum9//定义

2、邻接边数intGraph[VertexNum][VertexNum];//图形邻接数组intEdge[EdgeNum][3]=//输入数据{{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},};intVisited[VertexNum];//查找记录intDistance[VertexNum];//距离总和voidDijkstra(intBegin){intMinEdge;//最小边intVertex;//最小边的顶点inti,j;intEdges;//边数Edges=1;//初始

3、边数Visited[Begin]=1;//初始顶点for(i=1;i

4、;while(Edges<(VertexNum-1))//当边数少于顶点数执行{Edges++;MinEdge=Max;//将最小边设到最大值for(j=1;jDistance[j]){Vertex=j;//找出最小边的顶点MinEdge=Distance[j];}//找出最小边的距离总和}Visited[Vertex]=1;//将最小边的顶点设为已查找printf("Step%d:",Edges);for(j=1;j

5、Num;j++){//找出未查找顶点的最小距离总和if(Visited[j]==0&&(Distance[Vertex]+Graph[Vertex][j]

6、i=1;i

7、;i