逢山开路问题(修改版)1

《逢山开路问题(修改版)1》由会员分享，可在线阅读，更多相关《逢山开路问题(修改版)1（21页珍藏版）》请在金锄头文库上搜索。

1、. . . 华 北 科 技 学 院课程设计说明书班级: 计算B101 :顾亚楠（0）成绩：_班级: 计算B101 :孔维文（9） 成绩：_班级: 计算B102 : 灏（4）成绩：_设计题目: 逢山开路问题 设计时间: 十九周周四 至 二十周周一 指导教师: 慧 评 语:_ _评阅教师: _ 逢山开路问题 摘要：本文是逢山开路问题的研究，主要研究特定两点之间的最短路，以及使得总成本最小。主要采用的方法是Dijkstra算法求两点间的最短路径，从而得到一条最优的路线，再对其进行细化获得更加精确的路线。最后再进行逐步定线，以局部最优为准则，逐步逼近目标点，得到较优解。 由于在开路期间会遇到湖泊，山脉

2、，山谷等问题，所以要进行桥梁，隧道，一般路段的各种搭建与组合，在对这三种不同形式的选择是，仔细划分了三种形式在不同情况下应该满足的坡度条件，从而确定路径的权值。 本问题保留了工程实际背景的一些基本特征,涉及到地貌环境等自然条件以及施工能力,费用系数等人为因素,这些在实际的工程设计上必须考虑的重要因素我们在解决本题时则须注意取舍,在用数学模型解题时,除了从数学角度上思考之外,适当的考虑有关实际因素,从总体上设计,这对于我们建立合理的数学模型提供了重要的依据,也会使我们得到的方案行之有效,本题在这方面表现得很明显 通过分析我们得出比较满意的结果，桥长：73米，位置为：（2900，1800）至（30

3、00，1900）之间的一段，隧道长：300米，位置为（4000，2800）至（4000，3100）之间的一段，公路长：12083米，得出最优的解价格：375.8万。 关键词：Dijkstra算法 目标最优化模型 逐步逼近 动态规划 一、问题重述 公路的修建是近几年我们国家不断进行实施的工程，尤其在某些偏远地区，由于地理条件的影响，实施起来难度可能会很大，并且花费大量的资金。就目前的情况来看，我国路段形式主要有三种：一般公路，隧道，桥梁。当我们要为某地区修路时，可能会遇到湖泊，山脉，山谷，在这种情况下，显然用一种形式是不能解决的，要对其进行组合。这时实施人员不仅仅要考虑资金问题，而且还要联系实际

4、。 我们通常会有一种想法：遇到湖泊绕道而走，遇到山谷搭建桥梁，遇到山峰就挖隧道。但实际情况不是这样的，根据实际情况要考虑坡度的问题，由于三种形式所用到的资金差距较大，因此要进行计算得出最优路线，从而使所用到的资金最小。也就是用最少的资金，达到实际的目标。 本问题要：要在一山区修建公路,首先测得一些地点的高程,数据见附录B(平面区域0x5600,0y4800表中数据为坐标点的高程,单位:米). 数据显示:在y=3200处有一东西走向的山峰;从坐标(2400,2400)到(4800,0)有一西北东南走向的山谷;在(2000，2800)附近有一山口湖,其最高水位略高于1350米,雨季在山谷中形成一溪

5、流,经调查知,雨量最大时溪流最高水面宽度W与(溪流最深处的)x坐标的关系可近似表示为 (2400x4000)公路从山脚(0,800)处开始,经居民点(4000,2000)至矿区(2000,4000),已知路段工程成本及对路段坡度(上升高程与水平距离之比)的限制见附录B 本文将研究下列问题：（1） 给出特定两点之间的最短路线。（2） 进一步给出精确的路线，包括隧道，桥梁，一般路段，再进行总成本的计算，找出最优解。（3） 当两点之间改变为点到面之间时，我们进一步给出解法，求取最短路和总成本。（4） 对于给出的模型，我们将进行评价与改进。2、 问题分析 首先我们看到题目中给出了好多的数据，面对这么多

6、的数据，我们首先就要做出地形的三维图形（matlab软件）。但是我们要精确的测量，这些数据只能粗疏表现，因此可能要对这些数据进行插值，拟合。 其次我们看到山脚到矿区要经过居民区，这样我们寻求最短路方可割裂成两部分，从山脚到居民区建立一个动态规划，再从居民区到矿区建立一个动态规划，这样就形成了一个双阶段的动态规划。当建立好动态模型时，我们需要细化两个阶段，分别对两个阶段不同的地形进行三种道路形式的选择。 最后我们要进行最短路的寻求，利用Dijkstra算法。进一步设计出第二种方案：逐步逼近方法寻求最优解。 以上的分析我们可以看出Dijkstra算法，逐步逼近，绘制三维图等都需要对其进行编程，因此

7、编程在此问题中占得比重很大。3、 基本假设（1） 地貌假设：山区各处高度变化是连续的，不存在断崖，断层；（2） 路段假设：忽略公路、桥梁、隧道的宽度，路段按几何线来处理；（3） 设计假设：不考虑修建分岔路，不考虑急转弯，缓急的限制；（4） 几何假设：除溪流处外，四个相邻的测量点近似构成矩形，因为相邻两点的高度差远小于它们的水平距离，实测点数据准确无误。（5） 环境假设：该地区工程地质条件满足工程建设的要求,不存在对工程建设有害因素,如地震带、溶岩地区等因素，并且该地区无原公路可用；4、 基本符号说明 A 起始点（0，800） B 居民点（4000，2000） X 矿区（2000，4000）di

8、j 网格中V i点和V j点间的径向距离；Wij V i点和V j点连线的边的权值；dist 两点间的最短路； 坡度控制点 线路必须经过的点A，B, C5、 模型的建立与求解1、由题目中的数据绘制三维图形： 为了对该山区有一个立体形象,我们做出它的三维图,读者可以轻易的辨别河谷及山脉走势，在matlab软件中输入代码（见附录A地貌代码），进一步进行插值拟合方可得到精确的三维图图1山区立体图我们对地貌进行等势线的描绘，在matlab软件中输入代码（见附录A等势线代码），进一步进行插值拟合得到精确的等势线。图2等势线2 、 动态模型建立： 画出三维图形后我们要建立双阶段动态规划，具体见下： （1）

9、代表意义： ：整段路的总成本 ：公路的长度 ：桥梁的长度 ：隧道的长度。 进一步地，对各个阶段有： 阶段1： （从A到B，经过溪流） （2） =3002000 阶段2： （从B到C，经过山脉） 3、不同的地形道路选择方式分析： 由、的表达式可知，不同的道路形式具有不同的权值。山区地形复设计线路要综合考虑山脉、湖泊、溪流以及地形起伏的影响。故对不同的地形应有不同的道路形式： (1)公路由于公路的修建成本远小于桥梁和隧道，所以在0.125的情况下可以考虑修建“Z”形路。 “Z”形路的每一段的斜率都为0.125，所以，“Z”形路的总长度为L8h。 图3： Z形公路 (2) 隧道 在坡度较大的情况下，

10、可以修建“Z”形路或隧道，而修建隧道的成本较高，只有在坡度满足一定条件（见下面说明）时，修隧道比修“Z”形路节省资金。1 隧道长度300米 修建隧道的条件为： 1500（x1x2）300米3 当隧道垂直穿过山脉，即=90（见图3）时，隧道长度最短 ,我们按这种方式修建隧道 。(3) 桥梁 在两种情况下可以修建桥梁：线路经过溪流、湖泊，且满足坡度相等的条件时；两座相邻高地的坡度满足条件时，修建桥梁比修建公路节省资金。在本题中，不存在满足这样条件的相邻高地，因此，在以下的讨论中不考虑此情况。4、最优路径的选取：由2、3式可知，都较短时，能得到较优的、。此时，问题已转变为求两点间的最短路。对于从山脚

11、至居民区的AB段规划，以溪谷为对称轴，对溪岸的可修桥点进行搜索，便可以从多个可能的最短路中找出最优路径；对于从居民区至矿区的BC段规划，则有多种可选性：1 仅修建“Z”形公路。2 2修隧道。以山脊为对称轴，对可修隧道点进行搜索，就可以从多个可能的最短路中找出最优路径； 至于最短路径的搜索，给出以下两种方法：4.1最短路法采用Dijkstra算法(见算法说明)与边界搜索相结合的方法求两点间的最短路径。分两段进行搜索。 4.1.1从起始点A到居民点B。 从A到B经过一条溪流，要在溪流两岸的等高点处修建桥梁。由于溪流各处的宽度不同，因此桥所在的位置不同，将导致桥和公路的长度同时变化，在这种情况下，无

12、法直接确定桥的最佳位置。Dijkstra算法用于搜索两固定点间的最短路，在桥梁位置不确定的情况下，先将桥设在溪流上的任一位置，搜索到桥在这一位置时对应的最短路，改变桥的位置，即在溪流岸边进行遍历，每一位置都对应着一条最短路， 再找出所有最短路中最短的一条，得到段最佳路径。由图，可以观察出：谷底成一条直线，且山谷两岸的等高线关于谷底对称。因此，我们将溪流和溪流两岸都看作是关于谷底对称。所以，桥梁与谷底沿线是垂直的。AB段的搜索步骤： a 取P0是溪流西岸的一点； b 找到P0关于谷底的对称点Q0；c 用Dijkstra算法分别求出AP0段、P0Q0段和BQ0段的最短路distA,P0 , distB,Q0 , distP0,Q0; d dist0=distA,P0distP0,Q0distB,Q0; e 对溪流西岸的另一点P1，用上述方法的点的最短路dist1; f dist0=min(dist0,dist1)； g 对溪流西岸的所有点，执行步骤e和f，最后得到的dist0为AB间的最短路。 4.1.2 从居民点B到矿区X 从等势图中可以看出，在居民点和矿区之间有一条东西走向的山脉，首先,不考虑修隧道，