便宜算法实验报告

实验报告实验目的：掌握图论算法的设计与实现实验内容：用便宜算法求解旅行商问题实验环境VC++实验过程与结果：便宜算法与旅行商问题简介：①、旅行商问题简介：在哈密顿回路中（每条边都有它的权）挑选一条总长最短（或总花费最省，旅途时间最少）的一条哈密顿回路②、便宜算法描述：置点的集合S={2，3，、、、n}，w(1,1)0,k1,序列T=（1，1），w(i,k)=w(i,1),i∈S。在S中，令w(j,t)=minw(i,k)i∈S,k∈T对回路T中的边（t,t1）,(t,t2),若w(j,t1)-w(t,t1)<=w(j,t2)-w(t,t2),则j插入到T的t,t1之间，否则j插入到T的t,t2之间，SSj,若S=Ǿ，结束。否则转C。对全部i∈S,置w(i,k)min(w(i,k),w(i,j)),转到B。算法框图：3、数据结构：ADTList{数据对象：D=（ai|ai∈ElemSet,i=1,2,、、、，n,n>=0）数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2，、、、，n}}4、运行结果：分析与总结：本程序主要用循环链表实现，路线的矩阵数据存储在二维数组中，然后将找到的最短路线所对应得城市放在循环链表中，程序中总共定义了两个一样的数组，一个用于操作（将用过的路线全部置为0）一个用于调用其中的路程距离用于最后的总路程的计算，最后输出最短路线中的城市和总路程长度。此程序共用了5个多小时，因为之前老师讲解得比较清楚，所以程序编起来思路比较清楚，主要就是把算法实现，及调试程序，没有遇到太麻烦的问题。五、源程序：#include"iostream.h"#include"stdlib.h"#include"iomanip.h"typedefstructLNode{ intdata; structLNode*next;}LNode,*LinkList;voidCreatroute(intCitynum,intRoute[100][100])//创建路线{for(intj=0;j<Citynum;j++){for(inti=0;i<j;i++) {cout<<"请输入一个城市距离:"; cin>>Route[i][j]; } Route[i][j]=0;}cout<<endl;cout<<"输入完毕,下面将数组填满";for(j=0;j<Citynum;j++){for(inti=0;i<Citynum;i++) {Route[i][j]=Route[j][i];} } cout<<endl;cout<<"全部设定好"<<endl;for(j=0;j<Citynum;j++){for(inti=0;i<Citynum;i++) {cout<<setw(5)<<Route[i][j]; cout<<endl;}}}voidCopy(intRoute[100][100],intRRoute[100][100],intCitynum){for(inti=0;i<Citynum;i++) {for(intj=0;j<Citynum;j++) {RRoute[i][j]=Route[i][j];} }}voidVisitList(LinkList&L)//遍历{LNode*p;p=L->next; while(p->next!=L->next){ cout<<p->data; p=p->next;} cout<<p->data; cout<<endl;}voidcreast(LinkList&Lc)//创建一个空的循环链表{ Lc=newLNode; Lc->next=NULL;}LNode*findlast(LinkList&L)//找出最后一个结点{LNode*p; p=L->next; while(p->next!=L->next) {p=p->next;} returnp;}voidthrust(LinkList&Lc,inte)//将e插入一个新的链表中{LNode*p,*q;if(Lc->next==NULL) {q=Lc; p=newLNode; p->data=e; q->next=p; q=p;} else{ q=findlast(Lc); p=newLNode; p->data=e; p->next=q->next; q->next=p; q=p;} q->next=Lc->next;}intCompare(intRoute[100][100],inti,intCitynum)//比较一个城市与其他城市的距离并返回此城市的号码{intj=0;intk;intmin=Route[i][j]; for(j=0;j<Citynum;) {if(Route[i][j]==0) {j++;} else{ min=Route[i][j]; k=j; break;} }j=0; while(j<Citynum) {while(j!=i&&Route[i][j]!=0) {if(Route[i][j]>=min) {j++;} else{min=Route[i][j];k=j; j++;} if(j==Citynum) {break;} } if(j==i||Route[i][j]==0) {j++; if(j==Citynum){break;} } } returnk+1;}voidDelete(intRoute[100][100],LNode*Prior,LNode*Cur)//删除已经比较过的城市距离{Route[Prior->data-1][Cur->data-1]=0; Route[Cur->data-1][Prior->data-1]=0; Route[Cur->next->data-1][Cur->data-1]=0; Route[Cur->data-1][Cur->next->data-1]=0;}voidInsert(LinkList&TR,LNode*p,intcity)//将某个城市插入指定指针后边{LNode*q; q=newLNode; q->data=city; q->next=p->next; p->next=q;}intTotalroute(LinkList&T,intRRoute[100][100]){ LNode*p=T->next;inttotal=0; while(p->next!=T->next) {LNode*q=p->next;total+=RRoute[p->data-1][q->data-1]; p=q; q=q->next;} returntotal;}voidmain(){ LinkListTR;//定义一个循环链表 creast(TR); intCitynum;//定义城市的总数 intRoute[100][100];//定义距离矩阵 cout<<"请输入城市的数目:"; cin>>Citynum; cout<<"构造一个路线数组:"; cout<<endl; Creatroute(Citynum,Route);//创建各城市间的距离 intRRoute[100][100];//定义相同的距离矩阵 Copy(Route,RRoute,Citynum);//将Route复制到RRoute LNode*Cur=TR;//定义当前指针（一直指向新插入到链表中的城市） intCur_City=1; thrust(TR,Cur_City);//先在循环链表中插入两个代表第一个城市的节点 LNode*Prior=Cur;//定义当前指针的前一个指针，用于插入操作 Cur=Cur->next; thrust(TR,Cur_City);//先在循环链表中插入两个代表第一个城市的节点intk=1;//操作符，标志已经处理过几个城市intshort_City=Compare(Route,Cur_City-1,Citynum);//通过调用函数找出与当前城市最近的城市 Insert(TR,Cur,short_City);//将该城市插入链表中 Prior=Cur; Cur=Cur->next; Delete(Route,Prior,Cur);//在Route数组中将处理过的城市间的距离变为0 Cur_City=short_City; k++; while(k!=Citynum)//算法描述中已介绍其下操作的含义 {intFront,Back; short_City=Compare(Route,Cur_City-1,Citynum); if(Front=(RRoute[Prior->data-1][short_City-1]-RRoute[Prior->data-1][Cur->data-1])<0) {Front=RRoute[Prior->data-1][Cur->data-1]-RRoute[Prior->data-1][short_City-1];} else {Front=RRoute[Prior->data-1][short_City-1]-RRoute[Prior->data-1][Cur->data-1];}//Front和Back为距离的差 if(Back=(RRoute[Cur->next->data-1][short_City-1]-RRoute[Cur->data-1][Cur->next->data-1])<0) {Back=RRoute[Cur->data-1][Cur->next->data-1]-RRoute[Cur->next->data-1][short_City-1];} else {Back=RRoute[Cur->next->data-1][short_City-1]-RRoute[Cur->data-1][Cur->next->data-1];}if(Front>=Back) {Insert(TR,Cur,short_City); Prior=Cur; Cur=Cur->next; Delete(Route,Prior,Cur); Cur_City=short_City; } else {In