资源描述：
《逢山开路问题(修改版)1.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、...华北科技学院课程设计说明书班级:计算B101:顾亚楠（0）成绩：______班级:计算B101:孔维文（9）成绩：______班级:计算B102:灏（4）成绩：______设计题目:逢山开路问题设计时间:十九周周四至二十周周一指导教师:慧评语:___________________________________________________________________________________________________________________________________________
2、_______________________________________________________________________________________评阅教师:_______________.......逢山开路问题摘要：本文是逢山开路问题的研究，主要研究特定两点之间的最短路，以及使得总成本最小。主要采用的方法是Dijkstra算法求两点间的最短路径，从而得到一条最优的路线，再对其进行细化获得更加精确的路线。最后再进行逐步定线，以局部最优为准则，逐步逼近目标点，得到较优解。由于在开路期间会遇到湖泊，
3、山脉，山谷等问题，所以要进行桥梁，隧道，一般路段的各种搭建与组合，在对这三种不同形式的选择是，仔细划分了三种形式在不同情况下应该满足的坡度条件，从而确定路径的权值。本问题保留了工程实际背景的一些基本特征,涉及到地貌环境等自然条件以及施工能力,费用系数等人为因素,这些在实际的工程设计上必须考虑的重要因素我们在解决本题时则须注意取舍,在用数学模型解题时,除了从数学角度上思考之外,适当的考虑有关实际因素,从总体上设计,这对于我们建立合理的数学模型提供了重要的依据,也会使我们得到的方案行之有效,本题在这方面表现得很明显通过分析我们
4、得出比较满意的结果，桥长：73米，位置为：（2900，1800）至（3000，1900）之间的一段，隧道长：300米，位置为（4000，2800）至（4000，3100）之间的一段，公路长：12083米，得出最优的解价格：375.8万。关键词：Dijkstra算法目标最优化模型逐步逼近动态规划一、问题重述公路的修建是近几年我们国家不断进行实施的工程，尤其在某些偏远地区，由于地理条件的影响，实施起来难度可能会很大，并且花费大量的资金。就目前的情况来看，我国路段形式主要有三种：一般公路，隧道，桥梁。当我们要为某地区修路时，可能
5、会遇到湖泊，山脉，山谷，在这种情况下，显然用一种形式是不能解决的，要对其进行组合。这时实施人员不仅仅要考虑资金问题，而且还要联系实际。我们通常会有一种想法：遇到湖泊绕道而走，遇到山谷搭建桥梁，遇到山峰就挖隧道。但实际情况不是这样的，根据实际情况要考虑坡度的问题，由于三种形式所用到的资金差距较大，因此要进行计算得出最优路线，从而使所用到的资金最小。也就是用最少的资金，达到实际的目标。.......本问题要：要在一山区修建公路,首先测得一些地点的高程,数据见附录B(平面区域0≤x≤5600,0≤y≤4800表中数据为坐标点的高
6、程,单位:米).数据显示:在y=3200处有一东西走向的山峰;从坐标(2400,2400)到(4800,0)有一西北——东南走向的山谷;在(2000，2800)附近有一山口湖,其最高水位略高于1350米,雨季在山谷中形成一溪流,经调查知,雨量最大时溪流最高水面宽度W与(溪流最深处的)x坐标的关系可近似表示为(2400≤x≤4000)公路从山脚(0,800)处开始,经居民点(4000,2000)至矿区(2000,4000),已知路段工程成本及对路段坡度(上升高程与水平距离之比)的限制见附录B本文将研究下列问题：（1）给出特定
7、两点之间的最短路线。（2）进一步给出精确的路线，包括隧道，桥梁，一般路段，再进行总成本的计算，找出最优解。（3）当两点之间改变为点到面之间时，我们进一步给出解法，求取最短路和总成本。（4）对于给出的模型，我们将进行评价与改进。二、问题分析首先我们看到题目中给出了好多的数据，面对这么多的数据，我们首先就要做出地形的三维图形（matlab软件）。但是我们要精确的测量，这些数据只能粗疏表现，因此可能要对这些数据进行插值，拟合。其次我们看到山脚到矿区要经过居民区，这样我们寻求最短路方可割裂成两部分，从山脚到居民区建立一个动态规划，
8、再从居民区到矿区建立一个动态规划，这样就形成了一个双阶段的动态规划。当建立好动态模型时，我们需要细化两个阶段，分别对两个阶段不同的地形进行三种道路形式的选择。最后我们要进行最短路的寻求，利用Dijkstra算法。进一步设计出第二种方案：逐步逼近方法寻求最优解。以上的分析我们可以看出Dijkstra算法，
