最短路问题的实际应用论文文档格式.docx
《最短路问题的实际应用论文文档格式.docx》由会员分享，可在线阅读，更多相关《最短路问题的实际应用论文文档格式.docx（7页珍藏版）》请在冰点文库上搜索。
问题总假设：
分别设置双龙洞，冰壶洞，朝真洞，桃源洞，黄大仙祖宫五个景点为A,B,C,D,E五点，根据现实及假设，可以得到如图所示的路线图：
再利用用Dijkstra算法求解无负权网络的最短路。
同时也可以利用此法算出最长路程。
问题一的解决：
以A为景点出口，E为出口。
故A点标号为P（a）=0给其余所有的T标号T（i）=+∞
考虑与A相邻的两个顶点BC，两个顶点为T标号，故修改这两个点的标号为：
T（b）=min[T（b）,P（a）+l12]=min[+∞,0+3]=3
T（c）=min[T（c）,P（a）+l13]=min[+∞,0+2]=2
比较所有T标号，T（c）最小，所以令P（c）=2
再考察（C,B）（C,D）（C,E）的端点：
同理可得
T（b）=6T（d）=6.8T（e）=10.2（显然已经到终点但还需要看看其余路线长短）
故又令P（b）=6.综合分析只有一条线路即Aà
Cà
Bà
Dà
E此时总路程为2+4+3+8.4=16.4>
10.2
所以，最短路程为Aà
E。
即当游客不想再看双龙洞时或者因为脚伤等因素需以最小路程离开时，可以路线Aà
E离开景区。
特殊情况的处理：
游客一定要去B景点则在一开始就应该先选择
B，而非C。
才能使路线最短。
因此，对于特殊问题，我们应当具体问题，具体分析。
总结Dijkstra法:
实施步骤大体分为三步:
标号à
比较T标号à
修改标号
设图的顶点数为n，则最多经过n-1步得到起点到终点的最短路。
问题二的解决：
同样以A为景点出口，E为出口。
但由于是最长的路线.可以利用似Dijkstra算法进行计算。
故A点标号为P（a）=0给其余所有的T标号T（i）=-∞。
T（b）=max[T（b）,P（a）+l12]=max[-∞,0+3]=3
T（c）=max[T（c）,P（a）+l13]=max[-∞,0+2]=2
比较所有T标号，T（b）最大，所以令P（b）=3
再考察（B，C）（B,D）的端点：
T（c）=7>
T（d）=6故令P（c）=7再继续考察（C,D）（C,E）
显然经过D，再经过E路程最长。
所以最长路程为Aà
即一些游客喜欢自然风光，喜欢走走看看，可以采用这条最长路程进行游玩。
同样也是观看所有景点的路线之一。
对于最短路程的解法，我们还可以通过Floyd算法，1962年（矩阵算法）进行运算：
得到邻接矩阵：
邻接矩阵
A
B
C
D
E
3
2
∞
4
4.8
8.2
8.4
由于自己对编程语言不太了解，参考资料后，给出一段关键部分：
fork:
=1tondo
fori:
forj:
ifa[i,k]+a[j,k]>
a[i,j]thena[i,j]:
=a[i,k]+a[k,j];
end;
以此可利用编程语言进行求解，运行程序得到弗洛伊德矩阵。
从而找到最短路的路线。
【其方法为：
从起点开始：
找出弗洛伊德矩阵中以该点为行坐标的最小的列坐标的指向的目标点
再找出指向点行坐标最小的列坐标的再次指向点（注意：
每次找指向点过程中应先去掉已到过的点和自己本身。
）如此循环直到找到终点为止就找到了最短路】
现在，我们还可利用lingo对最短路问题进行求解，其程序如下：
model:
sets:
c/1..5/:
u;
l（c,c）:
d,x;
endsets
data:
完成数据输入。
（将邻接矩阵中不可达两点间的权只设为10^5.）
d=03210000010000
3043100000
2404.88.2
10000034.808.4
1000001000008.28.40;
enddata
n=@size（c）;
min=@sum（l:
d*x）;
@for（c（k）|k#gt#1:
@sum（c（i）|j#ne#k:
x（i,k））>
=1;
@for（c（j）|j#gt#1#and#j#ne#k:
u（j）>
=+u（k）+x（k,j）-（n-2）*（1-x（k,j））+
（n-3）*x（j,k）））;
@sum（c（j）|j#gt#1:
x（1,j））>
@for（l:
@bin（x））;
@for（c（k）|k#ge#1:
@bnd（1,u（k）,9999）;
u（k）<
=n-1-（n-2）*x（1,k））;
end
通过利用lingo的计算，同样我们可以解出原最短路线的解。
问题三的探究：
建立的模型是否满足一次性不重复地经过所有路线回到起点（古典图论问题）
我们需要以下几个规律：
如果一个图一次性可以走完各个点，它必须有偶数个奇点。
如果还要回到起点，并且不重复地走完所有的路，则所有顶点必须都是偶点。
因此，我们可以看见：
景点中：
存在着奇点B，D。
故还是不可能一次性不重复地走过所有路线回到原起点。
但奇点的个数是偶数，故所有景点可以一次性游完，而不需要再考虑反复地问题。
总结：
对于一个图（简单图）来说满足上面规律2，即可一次性不重复地走完全部路线;
但如果只要走完一次性所有点，则只要满足规律1。
三、总论：
1.对于在双龙洞中的最短路问题，解得路线为：
双龙洞à
朝真洞à
黄大仙祖宫。
2.本问题的求解使用了图论中的最短路的方法求解。
主要采用的解法有3种：
Dijkstra算法Floyd算法Lingo解法。
从中可以看见，这次的论文，我主要讨论的是关于图与网络分析部分中最短路问题的解法。
同时，还对上课内容中引题部分欧拉七桥问题进行了总结。
3.对于这次问题的研究，意义在于：
①对于最短路问题有了进一步的了解和认识，初步掌握了对最短路问题的求解过程。
可以采用3种算法进行求解。
对此，对于我们生活中很多问题有一定的指导意义。
正如旅游的规划，邮递员送信，从一个地方到另一个地方最快的方案，设备更新等问题都利用这次研究的结果，进行分析与优化。
因此，
②学会了用lingo解决最短路问题的编程，扩展了自己的能力。
③是对运筹学知识内容的进一步理解，通过自己找问题，建立模型，解决问题，总结的过程，让自己对运筹学充满了兴趣。
4.不足之处：
①对于这次的论文，不足之处在于所构建的模型数目不多，只有5个点，为得是讨论简单。
但做下来才知道，其实更多的点，谈论过程还是一样的。
因此，如果最短路问题比较复杂，还是可以通过上述几种方法进行解决。
比如，有8个点，利用lingo解决的话，只需要将c/1..5/:
改为c/1..8/:
再将其余的内容进行修改。
因此还是具有一定的通用性。
②由于资料不是很全面，把实际地图抽象为网络图时不够精确，没有考虑其他方面（比如地势高低）等的影响。
所有在距离上存在一定偏差。
因此，以后在解决此类问题中，我们应当做好资料搜集工作，尽量使模型与实际接近。
参考内容：
[1]甘应爱等.运筹学（第三版）.清华大学出版社.2005
[2]Lingo+运筹学实训指导书【例7.6】
升级会员 