《Matlab最优化理论中的最短路问题 》由会员分享，可在线阅读，更多相关《Matlab最优化理论中的最短路问题 （11页珍藏版）》请在金锄头文库上搜索。
1、-范文最新推荐-1 / 11Matlab 最优化理论中的最短路问题 摘要在日常生活和生产中，我们经常碰到各种各样的图，如交通图、管道系统图等等。在优化理论中所谓图就是上述各类图的抽象和概括，用图来描述我们所研究的对象，以及这些对象之间的相互联系。例如，许多生产管理、工程设施、计划安排、交通运输等问题都可以用图形来描述。所谓最短路问题就是在一个加权图中，寻找某一点到另一点之间的最短路径。本课题的最重要的研究内容就是最短路问题的基本理论和二种算法，选用计算机软件实现算法，并能运用这些理论解决实际生活中的某些实际问题。本课题论文涉及的最短路的算法有 Dijkstra 算法、Floyd 算法。其中 D
2、ijkstra 算法主要应用于求解某指定点到其他点的最短路，Floyd 算法是目前求解任意两点间的最短路径的最优方法。在实际网络中，权数还可以是时间、费用等等，如选址、管道铺设、投资、某些整数规划和动态规划等问题都可归结为最短路问题。所以研究最短路问题具有深远的现实意义。关键词：最短路问题；Dijkstra 算法；Floyd 算法；Matlab；10242ABSTRACTIn daily life and production, we often encounter a variety of maps, such as communication maps, ductwork maps, an
3、d so on. Optimization of the so-called theory of the map is the map of the above types of abstraction and generalization, using maps to describe our research targets and the affiliation between those objects. For example, some production management, engineering facilities, the arrangement, transport
4、ation and other issues can be described by graphics.The shortest path problem is that in a weighted graph, -范文最新推荐-3 / 11find the shortest path from some or other point to another point. The major content of the disquisition is to study the basic theory and algorithms of the shortest path.,then we c
5、an choose computer softwares to carry out those algorithms, and will be able to use these theories to solve real-life problems of certain. 为了便于读者对图论的基础知识有一个初步的了解，下面先介绍一下和本课题相关的概念。1.1 图的概念图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼斯堡的七座桥”。图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体
6、事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个&l
7、dquo;点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。-范文最新推荐-5 / 111.1.1 无向图无向图——设 是一个有 个顶点的非空集合： ； 是一个有 条无向边的集合： ，则称 和 这两个集合组成了一个无向图，记作无向图 。中任一条边 若连接点 和
8、 ，则记为，并称与 为无向边的两个端点；边 与顶点 及 相关联，顶点 与顶点 相邻。 1.1.2 有向图有向图——设 是一个有 个顶点的非空集合： ； 是一个有 条有向边的集合： ，则称 和 这两个集合组成了一个有向图，记作有向图 。若 ， 为有向边 的起点， 为有向边 的终点，则记 。例 1-2 给有向图 ，其中 ， ，边与顶点的关系情况由表 1-2 给出 对表 1-2，作几何图形，如图 1-2 所示。类似与无向图，有向图 也有下列术语。平行边——不同的有向边 的起点和终点相同，则称边 为有向图 的平行边。如图 1-2 中的 与 即为平行边。孤
9、立点—— 中不与 中任一条边关联的点称为 的孤立点。简单图——无平行边的有向图称为简单图。完备图——图中任意两个顶点 和 之间，恰有两条有向边 ，及 ，则称该有向图 为完备图。基本图——把有向图 的每条边除去定-范文最新推荐-7 / 11向就得到一个相关的无向图 ，称 为 的基础图。称 为 的定向图。子图——设 ， 都是有向图，且 则称 为 的子图，并记为 。导出子图——若 则称有向图 为有向图 中关于 的导出子图， 。链——若
10、 是有向图 的基础图 中的一条链，则 就称为 中一条链。路——若 是有向图 的基本图 中一条链，且有 ，则称 为 的 至 的单向路，简称为路。路径——若有向图 的路 中的每一个顶点都不相同，则称 为 的 至 的单向路径，并称 可达 。回路——若有向图 的单向路径 的第一个顶点与最后一个顶点相同，则称 为 的单向回路，简称回路。若 为链、路、路径、回路 中的边，则可写为 。在简单图中，可用顶点序列来表示相应的链、路、路径。1.2 图的矩阵表示如何把图的有关信息输入和存储到计算机里去呢？我们知道，图的最本质的内容是顶点和边,顶
11、点与顶点之间的关联关系，我们不难用矩阵来表示这种关联关系。 已知图 ,其中 ，且 为 的邻接矩阵，则 中的 行 列元素 是图 中从 到 且长度为的 链的数目。1.2.3 权矩阵定义：赋权图 ，其边 有权 。构造矩阵 ，其中：-范文最新推荐-9 / 11称矩阵 A 为图 G 的权矩阵。例 4 写出下面所示图的权矩阵。解：上图的权矩阵为 2 最短路问题算法2.1 最短路问题最优化技术研究对象是从众多方案中选择一个最优的方案。对这些方案，首先确定一个衡量方案优劣的标准，然后采取某种手段寻找该标准下的最好方案。解决最优化问题的方法称为最优化方法。网络分析是最优化技术中的一种重要的理论方法，而最短路问题
12、是网络理论中最典型的问题之一。许多优化问题可以使用网络理论中的最短路问题模型，如设备更新、管道铺设、线路安排、厂区布局等等。我们知道最短路问题可以用动态规划来解决，但某些最短路问题（如道路不能整齐分段者）构造动态规划方程比较困难，而图论方法则比较有效。 2.1.1 最短路问题的描述最短路问题的一般提法如下：设 为连通图，图中各边有权 （ = 表示 间无边） ， ， 为途中任意两点，求一条道路 ，使它是从 到 的所有路中总权最小的路。即：最小。有些最短路问题也可以是求网络中某指定点到其余所有结点的最短路，或求网络中任意两点间的最短路。最短路问题中常见的几类问题：（1）两指定点间的最短路问题；（2）从某指定点到其他所有点之间的最短路问题；（3）任意两点对之间的最短路径问题；2.1.2 算法的概述与比较-范文最新推荐-11 / 11在给定的某一赋权网络中，求始点到其它各点的最短路径算法通常分为两类：第一类是用于求解赋权网络中不存在负数边权，目前比较通用的是 Dijkstra 算法；第二类是用于求解赋权网络中存在负数边权，这类算法目前比较通用的是 Floyd 算法。
