#include<iostream.h>
#include<stdlib.h>
struct stack
{
int n;
int L;
int c;
int fx;
stack* p;//父接点
stack*NEXT;
};
stack *Tsp1,*Tsp2;
int cycle[100]={0};
void pause()//暂停函数
{
char s;
cout<<"press <Enter> key to continue……";
cin.unsetf(ios::skipws);
cin>>s;
cin.setf(ios::skipws);
}
int find(stack *p,stack *Headopen,stack* Headclosed)//展开接点在OPEN 和CLOSED是否出现
{
stack *p1,*p2;
p1=Headopen;
p2=Headclosed;
Tsp1=Tsp2=NULL;
while(p1!=NULL)
{
if(p->c==p1->c)
{
Tsp1=p1;
return 1;
}
p1=p1->NEXT;
}
while(p2!=NULL)
{
if(p->c==p2->c)
{
Tsp2=p2;
return 1;
}
p2=p2->NEXT;
}
return 0;
}
int f(stack *s,int L,stack* Headclosed,int citynum)//计算估价函数
{
int length=0,i=0;
while(s!=NULL)
{
length=length+s->L;
s=s->p;
i++;
}
length=length+(citynum-1-i)*L;
return length;
}
stack* sortopen(stack *p3,stack*p)//升序排列OPEN表
{
stack*p1,*p2;
if(p3==NULL)
{
p3=p;
p->NEXT=NULL;
return p3;
}
if(p3->fx>=p->fx)
{
p->NEXT=p3;
p3=p;
return p3;
}
p2=p1=p3;
while(p2->NEXT&&(p2->fx)<(p->fx))
{
p1=p2;p2=p2->NEXT;
}
if((p2->fx)<(p->fx))//插入链表尾部
{
p2->NEXT=p;
p->NEXT=NULL;
}
else//插入P2之前
{
p->NEXT=p2;
p1->NEXT=p;
}
return p3;
}
void tsp(int **a,int start,int citynum,int Len)//TSP主体函数
{
int i=1,k,j;
stack*sp1,*sp2,*Headopen,*Headclosed,*s0;
s0=new stack;
s0->L=a[start-1][start-1];
s0->c=start;
s0->p=NULL;
Headopen=s0;
Headopen->NEXT=NULL;
sp1=Headopen;
Headclosed=NULL;
while(sp1!=NULL)
{
if(Headclosed==NULL)
{
Headclosed=Headopen;
Headopen=Headopen->NEXT;
Headclosed->n=i++;
Headclosed->fx=f(Headclosed,Len,Headclosed,citynum);
j=Headclosed->c-1;
sp2=Headclosed;
}
else//
{
if(Headopen!=NULL)
{
sp2->NEXT=Headopen;
Headopen=Headopen->NEXT;
sp2=sp2->NEXT;
sp2->NEXT=NULL;
sp2->n=i++;
j=sp2->c-1;
}
else break;
}
for(k=0;k<citynum;k++)//扩展N接点
{
if(k!=j)
{
stack *p0;
p0=new stack;
p0->p=sp2;
p0->L=a[j][k];
p0->c=k+1;
p0->fx=f(p0,Len,Headclosed,citynum);
if(find(p0,Headopen,Headclosed)==1)
{
if(sp2->p->c!=p0->c)
{
if(Tsp1!=NULL&&(p0->fx<Tsp1->fx))
{
Tsp1->p=p0->p;
Tsp1->L=p0->L;
}
else if(Tsp2!=NULL&&(p0->fx<Tsp2->fx))
{
Tsp2->p=p0->p;
Tsp2->L=p0->L;
}
}
}
else
Headopen=sortopen(Headopen,p0);
}
}
}
int length=0;
i=0;
while(Headclosed!=NULL)
{
cycle[i]=Headclosed->c;
length=length+Headclosed->L;
Headclosed=Headclosed->NEXT;
i++;
}
cycle[i+1]=length;
}
int find3(int**a,int num)//找出最小权值
{
int c=a[0][1];
for(int i=0;i<num;i++)
{
for(int j=0;j<num;j++)
{
if(a[i][j]<c&&a[i][j]!=0) c=a[i][j];
}
}
return c;
}
void display(int p[],int k,int **a)//显示函数
{
int L=0;
for(int j=0;j<k-2;j++)
{
L=L+a[p[j]-1][p[j+1]-1];
}
p[k-1]=L;
for( int i=0;i<k-1;i++)
{
if(p[i]==0) break;
else
cout<<p[i]<<"--->";
}
cout<<endl;
cout<<"所走的总路程是:"<<p[k-1];
cout<<endl;
}
void main()
{
int start=1,Len,citynum,count;
cout<<"旅行商问题的A算法解答:"<<endl;
cout<<"旅行商问题:有叫TSP问题,假设有N个可以互相"<<endl;
cout<<" 直达的城市,某旅行商准备从其中的A城出发,"<<endl;
cout<<" 周游个城市一周,最后又回到A城市,要求所走路程最短"<<endl;
cout<<"**********************************************"<<endl;
cout<<"**********************************************"<<endl;
pause();
system("cls");//清屏函数
cout<<"5个城市为默认状态,你也可以输入其他城市数目"<<endl;
cout<<"其中A城市到B城市的距离看作相等,所以,"<<endl;
cout<<"你只需要输入citynum*(citynum-1)/2个权值就可以了!"<<endl;
cout<<endl;
pause();
system("cls");//清屏函数
cout<<"请输入城市数目(默认为5个城市):"<<endl;
cin>>citynum;
int **a=new int*[citynum];
int b[5][5]={0,1,2,7,5,1,0,4,4,3,2,4,0,1,2,7,4,1,0,3,5,3,2,3,0};
for(int k=0;k<citynum;k++)
{
a[k]=new int[citynum];
}
if(citynum==5)
{
cout<<"执行默认状态:"<<endl;
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
a[i][j]=b[i][j];
}
}
else
{
cout<<"请输入"<<citynum*(citynum-1)/2<<"条航路的权值:"<<endl;
for(int i=0;i<citynum;i++)
{
for(int j=i;j<citynum;j++)
{
if(i==j) a[i][j]=0;
else
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
}
cout<<"用二维数组a[i][j]表示你所输入的状态图为:"<<endl;
cout<<"=================================="<<endl;
for(int i=0;i<citynum;i++)
{
count=1;
for(int j=0;j<citynum;j++)
{
cout<<a[i][j]<<" ";
if(count==citynum) cout<<endl;
count=count+1;
}
}
cout<<"================================="<<endl;
cout<<"*********************************"<<endl;
cout<<"a[i][j]的值表示i到j的路程"<<endl;
cout<<"*********************************"<<endl;
cout<<endl;
Len=find3(a,citynum);
cout<<"输入起始城市:"<<endl;
cin>>start;
if(start>citynum)
cout<<"只有"<<citynum<<"个城市,你的输入非法!"<<endl;
else
{
cycle[citynum]=start;
tsp(a,start,citynum,Len);
display(cycle,citynum+2,a);
}
}
TSP.rar_人工智能
版权申诉
4 浏览量
2022-09-19
14:57:15
上传
评论
收藏 2KB RAR 举报
weixin_42653672
- 粉丝: 94
- 资源: 1万+
最新资源
- 藏区特产销售平台源代码+论文+毕业设计.zip
- B297C8EC5A69641DB3E681E1B3F894E5.mp4
- PrimitivesPro v2.2.unitypackage
- 财务管理系统源代码+论文.zip
- 高级信息通信运行管理员第七套试卷
- UModeler v2.11.6 (May 10, 2024).unitypackage
- 基于Selenium的Java爬虫实战(内含谷歌浏览器Chrom和Chromedriver版本127.0.6486.0)
- 基于FPGA的CORDIC算法旋转模式实现
- bilibili视频解析下载源码
- 基于Selenium的Java爬虫实战(内含谷歌浏览器Chrom和Chromedriver版本124.0.6367.60)
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈