运筹学2资料文档.docx
- 文档编号:1987152
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:17
- 大小:84.07KB
运筹学2资料文档.docx
《运筹学2资料文档.docx》由会员分享,可在线阅读,更多相关《运筹学2资料文档.docx(17页珍藏版)》请在冰点文库上搜索。
(ps:
老师,我们最后解决从终点回到起点的最短问题存在瑕疵,从大区间之间最短问题,请多多指教,谢谢)
问题的提出
利用附件P2中所列的陕西区县公路里程表,寻求旅行者由碑林区出发的路线,并绘制线路图:
1..仅有一个旅行者,在拜访每个区县一次且仅一次后再回到起点碑林区的最短路径。
2..有两个旅行者,合计拜访每个区县一次且仅一次的最短路径。
问题的分析
1..总共有107个地区,以每个区的区中心为一个小点,则有107个点,但是这样的话计算量
工作量太大,所以我们尝试把每个区中心相互距在某一范围内看作是一个大点,然后整个所有区域可以看成是若干个大点(大点有若干个小点组成)
2..初步设想使用动态规划跟神经网络线法,并且逐个尝试“某个范围”的距离指标长度,因
为动态规划是适用于小数目点数的问题,最后选择80公里。
然后把107个区划分为9个大点,这样就可以使用动态规划来解决问题了
3..货郎担问题
对于货郎担问题的一个解序列,可以通过换位、移位和倒位三种基本的次序变换操作,改变原来解序列的排列次序,得到新的解序列。
其它游路改进的启发式操作.都可以
由这三种基本操作组合而成。
设旅行商问题中的个城市为f1If2I,,用d表示q和cj之间的距离。
一条游路表示为解序列f:
{C1,f2',l,q表示解序列c中的第个元素。
1.1.1换位操作(exchange)如图1所示,将解序列中第个元素C。
与第J个元素c,的
位置交换。
换位操作的性能指标为:
△D换位=(d(c,一1,C,)+d(f。
,Ci+1)+d(勺1,ci)+d(勺,q+1))一(d(c,一1,cj)+d(cj,cf+1)+d(cj一1,c,)+d(C,,f,+1))
(1)其中,D表示游路的长度,下同。
图1换位操作示意图如对一个10城市解序列进行换位操作:
8—35672—94O1城市C2与城市c7的位置交换8—95672—3401则
△lD换位=(d(fl,2)+d(2,3)+d(6,C7)+d(7,8))一
(d(fl,f7)+d(C7.3)+d(6,C2)+d(f2,8))=
(d8.3+d3。
5+d2。
9+d9.4)一(d8。
9+d9。
5+d2.3+d3.4)
1.1.2移位操作move移位操作相当于选择(Or.opt)操作,如图2所示,
列中第个元素q移动到第j个元素c,之后的位置上。
移位操作的性能指标为:
△D咎位=(d(C。
一l,f。
)+d(CC1)+d(cj,c=f+1))一
word文档可自由复制编辑
(d(Ci—l,q+1)+d(ci,C)+d(C。
,q+1))图2移位操作示意图如对一个10城市解序列进行移位操作t
程序说明
任给一个城市与城市间的道路图,求一个旅行商访问每个城市并回到出发
点的最短路程。
如本实验中,城市间均有道路的五个城市的地图可以表示成下面的图1:
B
7
A 7 10 10
6 13
10 C 5 9 E
6
D
图1城市间均有道路的五个城市的地图在旅行商的地图中,五个城市用节点表示, 两城市间的距离用弧线上的数字表
示。
设旅行商从A城市出发,到B、C、D、E等城市去推销商品,要寻找一条从A
出发, 包括B、C、D、E,且仅包含一次,最后回到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*算法。
模型建立
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旅行商问题的旅程表
A
6(A,C)
7
5
9
(A,C,B)
(A,C,D)
(A,C,E)
图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给出了五城市旅行商问题的一个部分搜索图:
27.3
B
7
26.1
C
A
13
6 1030 33
D E
7 5 9
28 26.2 30
B D E
10 6
31 27
B E
图5五城市旅行商问题的一个部分搜索图
(图中节点旁两个数字, 前一个为f(n)估计值,后一个表示扩展的先后顺
序)
其中K=5,满足h<=h*,故图是A*算法的搜索图。
图中弧线上的数字是两城市
间的实际距离,即图中两节点间的实际耗散值;节点的标示也作了简化,不是用状态表,而仅仅标出所到的城市。
由于是A*算法,则结束在一条最佳路径上,既A—>B—>E—>D—>C—>A.该路径的f*=34。
算法实现 本实验设计了两个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值int level;
//层
structnode*parent;//父节点
structnode*next;//后继structnode*front;//前驱
};
定义一个结构体path表示Open表和Bestpat
h表structpath
{
structnode*head;
struct node*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.输出最佳路径。
模块分析
在无向完全图中,对于任意两个顶点vi 和 vj,我们可以在多项式时间内找
到vi和vj这两个顶点之间的所有路径,选择其中路程最短的一条,令S[i,j]表示
vi和vj这两个顶点之间最短距离的那条路径。
搜索路径S[i,j],找到vi到达的在
S[i,j]上的第一个顶点,记该顶点为vk,将其记录在数组中R[][],递归查找vi到
vk和vk到vj的最短路径及其相应权值,最后将数组D[]中的顶点和权值之和打
印出来即为所求,并用画图函数将行经过程画出。
intExp(intk)/计算2的k次方:
二进制数左移一位实现*2
{
k=1< returnk; } 该函数用以计算2的k次方(二进制数左移一位实现*2计算)。 设计思想: 用一个二进制数来表示顶点集,其各位数值表示的含义为: 当该位为i=1时表示顶点i+1在集合s中,否则若i=0顶点i+1不在集合s中。 例如k=1表示顶点2在集合s中。 对给定n个顶点,共需要用n-1位二进制位来记录它的全部顶点。 intReadfile()/读入测试文件 { intspace,i,j;chars[10]; printf("请输入数据文件名: ");gets(s);if(freopen(s,"r",stdin)==NULL) { printf("数据文件读取失败! \n"); return0; } scanf("%d",&n);printf("经过城市的个数为: n=%d\n",n); G=(int**)malloc(sizeof(int*)*(n+1));/开辟空间,用以存储图的邻接矩阵 for(i=0;i<=n;i++) G[i]=(int*)malloc(sizeof(int)*(n+1));/为邻接矩阵分配空间 space=Exp(n-1); D=(int**)malloc(sizeof(int*)*(n+1));for(i=0;i<=n;i++) D[i]=(int*)malloc(sizeof(int)*(space)); R=(int**)malloc(sizeof(int*)*(n+1));for(i=0;i<=n;i++) R[i]=(int*)malloc(sizeof(int)*(space)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&G[i][j]); return1; } 该函数从当前目录下读入测试文件。 该函数还可以实现对用户输入的文件名的判断。 若输入的文件名在当前目录下存在,那么程序继续运行,否则直接退出以节省程序运行时间。 另外,在函数体内实现了对邻接矩阵的空间分配。 voidFillTable()/采用自底向上填表 { inti,k; unsignedintmax,s2;max=Exp(n-1)-1;for(s=1;s<=max;s++) { for(i=1;i<=n;i++) if((s&1<<(i-2))==0)/如果第i个顶点不属于集合s { D[i][s]=MAXNUM; for(k=2;k<=n;k++) { if((s&1<<(k-2))! =0) { s2=s&~(1<<(k-2));if(G[i][k]+D[k][s2] { D[i][s]=G[i][k]+D[k][s2];R[i][s]=k; } } } } } } 在程序运行过程中用该函数来记录添加到集合s中的顶点,本函数采用自底 向上来填写。 voidTsp()/动态规划求解 { inti;s=s&0; for(i=2;i<=n;i++) { D[i][s]=G[i][1]; R[i][s]=1; } FillTable(); } 函数voidTsp()实现采用动态规划对问题进行求解。 unsignedintDeletes(intk)/从s中将第k个顶点删除 { unsignedintts;ts=1;ts=ts<<(k-2);ts=~ts; returns&ts; } 第2步实现的对邻接矩阵空间的分配,但是有些开辟的空间在程序后续步骤中因不需要用到,或者是已经没有再利用而成为占用空间的垃圾。 为了节省空间,该函数用来实现从s中将第k个顶点删除。 voidReconstruct()/构造最优解,输出最短路程和最短路径 { inti,k; s=Exp(n-1)-1; printf("最短路程是: %d\n",D[1][s]); printf("最短路径为: \n"); printf("1->"); for(i=1,k=R[1][s];i<=n;i++,k=R[k][s]) { if(i printf("%d->",k); else printf("%d",k); s=Deletes(k); } printf("\n"); } 系统测试本实验成功实现了两个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),满足单调限制 动态规划 源程序清单 #include structnode { intnum; intfvalue;//f值intgvalue;//g值inthvalue; //h值int level; //层 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<<"不能打开文件! "< exit (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]; } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 资料 文档