实验报告旅行商问题.docx
《实验报告旅行商问题.docx》由会员分享，可在线阅读，更多相关《实验报告旅行商问题.docx（18页珍藏版）》请在冰点文库上搜索。
实验报告旅行商问题
1、实验题目
人工智能实验报告
——旅行商问题
旅行商问题：
从某个城市出发，每个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。
请定义两个h函数（非零），讨论这两个函数是否都在h*的下界范围，是否满足单调限制？
你认为哪个会产生比较有效的搜索？
2、实验目的及要求
旅行商问题是图论中的一个重要的经典问题，本次实验要求学生要求自行定义两个h函数（非零），独立编写程序解决旅行者问题，语言不限，工具不限，独立完成实验报告。
通过本次实验，使学生加深对图搜索策略的理解和认识，对启发式搜索、估价函数有更深入的理解认识，并学会灵活掌握及解决实际问题。
3、实验设备
装有Office软件的微机一台，本次实验使用Visualstudio6.0开发环境
4、实验内容
本实验首先对旅行商问题进行了学习了解，之后结合人工智能课堂内容，设计了两个h函数，使用C语言编写实现。
具体说明及步骤如下。
4.1、旅行商问题
旅行商问题是图论中的一个重要的经典问题:
任给一个城市与城市间的道路图,求一个旅行商访问每个城市并回到出发点的最短路程。
如本实验中,城市间均有道路的五个城市的地图可以表示成下面的图1:
B
7
A71010
613
10CE
5
6
D
图1城市间均有道路的五个城市的地图
在旅行商的地图中,五个城市用节点表示,两城市间的距离用弧线上的数字表示。
设旅行
商从A城市出发,到B、C、D、E等城市去推销商品,要寻找一条从A出发,包括
B、C、D、E,且仅包含一次,最后回到A的一条最短路径。
4.2、A*算法
A*算法是N.Nillson于1971年提出的一种有序搜索算法,该算法被认为是求解人工智能问题的最成功的技术理论之一。
Nillson指出对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数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）=g*（n）+h*（n）的值来排序OPEN表的节点，f值小者优先。
通常称这种算法为A算法。
在A算法的基础上，进一步限制h（n）函数，使得搜索图中的每一个节点n，能满足h（n）<=h*（n）、称h函数取h*的下界。
这种算法叫A*算法。
4.3、模型建立
1、状态描述和状态空间
所谓状态,是指在一定的时空范围内，问题所涉及的人、物、时间等的布局关系。
通常把问题的初始布局关系称为初始状态，问题解决时到达的状态叫目标状态。
这两个状态之间存在差异，如何从初始状态到达目标状态就是对问题求解。
在求解过程中可能到达的所有状态统称为状态空间。
包括初始状态、中间状态、目标状态。
在状态空间法中问题的求解通常是从初始状态到达目标状态的一条最佳路径，这条路径依靠搜索算法在状态空间中寻找，这就是状态空间法的核心所在。
2、产生式系统是状态空间法的基本系统结构
一个产生式系统模型包括三个基本的组成部分，即一个综合数据库，一组产生式规则和一个控制系统，通常称为产生式系统的三个基本要素。
产生式系统的工作过程如图2：
图2产生式系统的工作过程
3、A*算法对旅行商问题的解决方法
图3给出了旅行商问题的旅程表。
两城市间的距离用数字表示，其中最小距离为5。
A
B
C
D
E
A
0
7
6
10
13
B
7
0
7
10
10
C
6
7
0
5
9
D
10
10
5
0
6
E
13
10
9
6
0
图3旅行商问题的旅程表
A6
（A,C）
图4城市状态图
设旅行商已从A城市到达了C城市，现行状态描述为（A,C），即状态表中已有两个元素。
下一步是到B、还是D、E则要看f（B）、f（D）、f（E）的大小，小者优先。
其中f（B）=g（B）+h（B）
f（D）=g（D）+h（D）
f（E）=g（E）+h（E）
已知如图4。
关键是各后继节点h函数的估价值如何计算。
从上图还可以看出,无论下一步是到B、到E还是到D，旅行商都是已到过三个城市，即现行状态表的元素数均为3，与目标状态相比，还有3个城市没有去，包括最后回到A城市。
如果我们假设剩下的3个城市间的平均距离等于最小距离5，则从B或从E、D到达目标状态将要付出的代价不会小于3*5=15，即至少还要走3*5=15的距离，这就是h函数的估价值,即h（B）=15、h（D）=15、h（E）=15,将他们代入f（n）函数,得
f（B）=13+15=28f（D）=11+15=26f（E）=15+15=30
由此得出,旅行商下一步由C城市走到D城市。
所设置的h函数可用下式表示:
h=（目标状态表的元素数—现行状态表的元素数）*K
K是一个系数,如K取两城市间的最小问题。
所设置的h,满足h<=h*。
图5给出了五城市旅行商问题的一个部分搜索图:
图5五城市旅行商问题的一个部分搜索图
（图中节点旁两个数字,前一个为f（n）估计值,后一个表示扩展的先后顺序）
其中K=5，满足h<=h*，故图是A*算法的搜索图。
图中弧线上的数字是两城市间的实际距离，即图中两节点间的实际耗散值；节点的标示也作了简化，不是用状态表，而仅仅标出所到的城市。
由于是A*算法，则结束在一条最佳路径上，既A—>B—>E—>D—>C—>A.该路径的f*=34。
4.4、算法实现
本实验设计了两个h函数，使用A*算法编写程序实现解决旅行者问题。
在旅行商问题中节点（A...XY）的代价=起始城市到X城的代价+X城到Y城的代价
其中的代价可以是距离，费用或者时间等。
本实验设置的代价为距离，启发值用h表示，设计两种h函数，分别为：
1）、h1（n）=当前最短*未走路段数
2）、h2（n）=全程最短*未走路段数在程序中的实现：
p->gvalue=p_min->gvalue+relation[p_min->num-1][i];p->hvalue=min*（number-p->level）;//h2（n）
//p->hvalue=c_min*（number-p->level）;//h1（n）p->fvalue=p->gvalue+p->hvalue;
其中gvalue:
g（n）
hvalue:
h（n）fvalue:
f（n）
p_min->gvalue:
起始城市到X城的代价
relation[p_min->num-1][i]:
一个二维数组，X城到Y城的代价min:
min{全程最短路径代价}
c_min:
min{当前最短路径代价}number:
城市总数
p->level:
城市节点所处于搜索树的层次，和已访问的城市数同值
在本程序中
定义一个结构体node用于表示城市节点：
structnode
{
intnum;
intfvalue;//f值intgvalue;//g值inthvalue;//h值intlevel;//层
structnode*parent;//父节点structnode*next;//后继structnode*front;//前驱
};
定义一个结构体path表示Open表和Bestpath表
structpath
{
structnode*head;structnode*tail;
}Open,Bestpath;
其中Open表用于存放扩展出来的节点、Bestpath表用于在程序的末尾存放最佳路径
测试数据的输入使用邻接矩阵表示完全图使用二维数组relation[100][100]存放
程序流程：
1．将path数组中元素值置下标值：
path[i]=i+1
2．从文本中读出邻接矩阵
3．默认从第一个点开始搜索，并将path[0]=-1，表示该点已被纳入路径
4．扩展刚刚被纳入路径的节点，扩展的方法为在path数组中搜索值不为-1的元素，为之创建节点写入数据（包括g值,h值,f值,parent节点）并纳入Open表中
5．在Open表中搜索f值最小的节点确定为当前的最优路径点p_min,并且将上一次的最优路径点所在的路径上所有节点的path表中的元素值改为其下标值，表示删除原路径，同时将p_min所在的路径上所有节点的path表中元素值改为-1，表示创建新路径。
6．回第4步循环，直至path表中所有的元素值均为-1退出循环
7．由此获得最后一次的最优路径点，利用结构体中的parent指针得到最佳路径，并将路径存放在Bestpath表中
8．输出最佳路径
9．程序退出。
5、实验结果
本实验成功实现了两个h函数的A算法，结果证明算法正确。
两种方法对给出问题求解图如下所示（左h1、右h2）：
为增强对比，两种h函数分五组实例分别求解，对比效果截图如下所示（左h1、右h2）：
第一组4点TSP问题
第二组5点TSP问题
第三组5点TSP问题
第四组6点TSP问题
第五组6点TSP问题
由五组对比可以看出，h1函数和h2函数对于不同的情况解的结果不一定相同，从求解循环次数上也不定义相同，但都能找到最优解。
分析：
1、h1（n）=当前最短*未走路段数，在寻找最佳路径至A—>C—>D—>E—>B时，h1（B）
=10*1=10，h*（B）=7，所以h1不在h*的下界范围；
h2（n）=全程最短*未走路段数，很明显h2（n）<=h*（n），在h*的下界范围；
2、h1（n）=当前最短*未走路段数，在寻找最佳路径至A—>C—>D时，h1（C）=6*4=24,h1（D）=5*3=15,C（C,D）=5,即h1（C）-h1（D）>C（C,D）,不满足单调限制
h2（n）=全程最短*未走路段数，很明显对所有节点ni和nj，nj是ni的一个后继节点，h（ni）-h（nj）=5≤C（ni,nj），满足单调限制
6、心得体会
在这实验中，我第一次使用A*算法，确实遇到了不少问题。
旅行商问题在上学期的算法与程序设计课程中也接触过，但当时解决的时候使用的是另外一种算法。
实验中根据老师给出的h1（n）、h2（n）、h3（n）提示发现h3（n）满足h（n）选择好函数之后发现h1（n）中的当前最短是不断变化的，这个变化值的设计费了我不少时间，不过最终结果是好的。
通过实验结果我发现A*算法并不一定是最优的，针对不同的问题，算法的优劣也不同，但A*算法一定能够求出最佳解这个是毫无疑问的。
主要程序代码：
全部程序详见附件。
#include#include#include
structnode
{
intnum;
intfvalue;//f值intgvalue;//g值inthvalue;//h值intlevel;//层
structnode*parent;//父节点structnode*next;//后继
structnode*front;//前驱
};
structpath
{
structnode*head;structnode*tail;
}Open,Bestpath;
voidmain（）
{
inttotal=0;
intrelation[100][100];//邻接矩阵intpath[100];//路径点集合
inti,j,number;//number路径点的数目
intmax=0;//存放最大值,用于计算h值
intmin;//存放最小值,用于计算h值
intc_min=0;//存储当前最小,用于计算h值
intcount;//用于计数
ifstreamfin（"experimentaldata.txt"）;if（!
fin）
{
cerr<<"不能打开文件!
"<（1）;
}
fin>>number;
cout<<"Thereare"<"<{
for（intn=0;n{
fin>>relation[m][n];if（relation[m][n]>max）max=relation[m][n];cout<}
cout<}
for（i=0;i<=number;i++）
{
path[i]=i+1;//用1，2，3，4.来表示路径点
}
min=max;//初始化min
for（i=0;i{
for（j=0;j{
if（relation[i][j]==0）continue;else
{
if（min>relation[i][j]）min=relation[i][j];
}
}
}
structnode*p0=newstructnode;p0->level=0;
p0->num=1;//A点
p0->parent=NULL;
path[0]=-1;//默认从第一个路径点开始搜索
Open.head=newstructnode;Open.tail=newstructnode;Open.head->next=Open.tail;
Open.tail->front=Open.head;//初始化Open表
structnode*p1,*p2;structnode*p_min;structnode*p_temp;p1=Open.head;p2=Open.tail;
//p1,p2用于确定节点插入Open表的位置
c_min=relation[0][1];for（i=2;i{
if（relation[0][i]==0）continue;else{
if（c_min>relation[0][i]）c_min=relation[0][i];
}
}//计算当前最短for（i=1;i{//插入节点
structnode*p;p=newstructnode;
p->num=path[i];
p->level=1;//第一层
p->gvalue=relation[0][i];//A点到其他点的距离
//p->hvalue=min*（number-p->level）;
p->hvalue=c_min*（number-p->level）;//当前最短*未走路段数p->fvalue=p->gvalue+p->hvalue;
p->parent=p0;
p1->next=p;p->front=p1;p->next=p2;p2->front=p;p1=p;
if（i==1）p_min=p1;else
{//寻找最优路径点
if（p_min->fvalue>p1->fvalue）p_min=p1;
}
}
p_temp=p_min;
//在Open中删除找到的路径点p_min->front->next=p_min->next;
p_min->next->front=p_min->front;
path[p_min->num-1]=-1;
//扩展找到的路径点（从第二层level=2开始进入循环）while
（1）
{
total++;for（i=0,count=0;i<=number;i++）
{
if（path[i]==-1）
{
count++;
}
}
if（count>number）break;//path数组中所有元素均为-1,则退出
elseif（count{
p1=Open.tail->front;p2=Open.tail;
c_min=max;for（i=0;i{
if（relation[p_min->num-1][i]==0）continue;if（path[i]==-1）continue;
else
{
if（c_min>relation[p_min->num-1][i]）c_min=relation[p_min->num-1][i];
}
}
//计算当前最短for（i=0;i{
if（path[i]!
=-1）
{
level
}
}
else
{
structnode*p;p=newstructnode;p->num=path[i];
p->level=p_min->level+1;//由最优路径点的level确定子节点的
p->gvalue=p_min->gvalue+relation[p_min->num-1][i];
//p->hvalue=min*（number-p->level）;p->hvalue=c_min*（number-p->level）;p->fvalue=p->gvalue+p->hvalue;
p->parent=p_min;
p1->next=p;p->front=p1;p->next=p2;p2->front=p;p1=p;
}
structnode*p;p=newstructnode;
p->num=path[number];
p->level=p_min->level+1;
p->gvalue=p_min->gvalue+relation[p_min->num-1][0];
p->fvalue=p->gvalue;//最后一个节点，未走段数为0，故f值等于g值p->parent=p_min;
p1->next=p;p->front=p1;p->next=p2;p2->front=p;p1=p;
}
//structnode*p=Open.head->next;
structnode*p=Open.tail->front;//从尾部开始着最优路径点i=1;
while（p!
=Open.head）
{//从Open表中寻找if（i==1）p_min=p;else
{//寻找最优路径点
if（p_min->fvalue>p->fvalue）p_min=p;
}i++;
p=p->front;
}//找到最优路径点
p=p_temp;//上一次的最优路径点while（p!
=NULL）
{//撤销上一次路径
path[p->num-1]=p->num;p=p->parent;
}
p=p_min;//新找到的最优路径点while（p!
=NULL）
{//重配置新路径
path[p->num-1]=-1;p=p->parent;
}
p_temp=p_min;//再次使得p_temp指向最优路径点，为下一次所用
//在Open中删除找到的路径点p_min->front->next=p_min->next;
p_min->next->front=p_min->front;
}
//循环结束
//初始化Bestpath表Bestpath.head=newstructnode;Bestpath.tail=newstructnode;Bestpath.head->next=Bestpath.tail;Bestpath.tail->front=Bestpath.head;
p1=Bestpath.head;p2=Bestpath.tail;
structnode*p;p=p_min;while（p!
=NULL）
{//将路径顺序存入Bestpath表中
p1->next=p;p->front=p1;p->next=p2;p2->front=p;p2=p;
p=p->parent;
}
p=Bestpath.head->next;cout<";while（p!
=Bestpath.tail->front）
{//从Bestpath表中输出路径
cout<num+64）<<"-->";p=p->next;
}
cout<<"A"<cout<"<front-
>fvalue<cout<"<}
升级会员 