这就是图论的最短路问题。.ppt

我们现在的问题: 如果从中国馆到一个目的地，有好几种线路可供选择，怎样走法才能使花费的时间最省？ 如果要到好几个展馆游览，应该如何安排顺序，才能使花在路上的时间最短，游遍所有的展馆同时又不重复； 在一个区域内参观，应该怎样安排参观线路，既能走遍所有的展馆，又能使总的行走路线最短； 1、游览线路的选择 ——最短路问题 求最短路的方法 求最短路，图论中有很多方法。较为常用的是一种标号的方法—Dijkstra算法。该算法由狄克斯特拉(E.W.Dijkstra)于1959年提出，其基本思想是从起点出发，逐步找出距离最近的点。在此过程中，同时记录下可能作为最短路的方案。 例题：求下图中A点到其他个点的最 短路及其长度 2、游览展馆的顺序安排 ——旅行售货员问题 到某个展区游览，怎样走才能游遍所有的展馆?这就是图论中点的行遍性问题。 点的行遍性问题也称Hamilton问题。这是因为最早提出这类问题的是英国的Hamilton爵士。 在一个图中找一个总长度最短的哈密尔顿回路，这就是旅行售货员问题，简称TSP, 是一个非常著名的世界难题。 在TSP的近似算法中，最简单的方法称为“最近邻点法”：从出发点出发，先选择与其最接近的城市，然后再剩余的城市中选择与最近的……,依次得到各个城市的经过次序，最终回到。 3、展区内游览线路安排 ——欧拉回路与中国邮递员问题 构造一个图，使得每个展馆都分布在这个图的边上，问题就转化为从第一个点出发，走遍该图中的每条边，最后回到出发点。 最好的情况是所有路都走遍并且没有重复，这样的总路程数是最少的。这其实就是一笔画的问题，因为是欧拉找到解决此类问题的方法，所以也把此类问题称为欧拉回路。 然而，有些问题是做不到“一笔画”，也就是有些路必须重复经过，那应该重复那些路呢？才能使总距离最短？事实上也就是重复的路线长度最短。这就是“中国邮递员问题”了。 求解中国邮递员问题的口诀： 先分奇偶点，奇点对对联； 连线不重叠，重叠需改变； 圈上联线长，不得过半圈。 假如我们的展馆分布如下图所示 在图中从第一个点出发经过所有边至少一次，然后回到出发点，使得总长度最短。 答 案： 世博会的脚步声已经越来越近了，我们每一个上海人、中国人都应该为世博做一些我们力所能及的事情，让这个城市更加美好 * 游览路线中的图论问题 1、游览线路的选择—最短路问题 2、游览展馆顺序的安排—旅行售货员问题 3、展区内游览线路安排—欧拉回路与中国邮递员问题 如果从中国馆出发要到某地启他的展馆，如果有几种不同的旅游路线可供选择，自然希望选择总长度最短，或者所花费的时间最少，或者所化的费用最省的走法。这就是图论的最短路问题。 首先，对于图上的每一条边，都给出一个非负数，称为该条边的权，用以代表这条边的长度、或者走过这条边所花费的时间、费用等。每条路上各边的权的总和统称为路的“长度”，这样图称为非负赋权图。而在不同的路中选择总长度最小的，就是最短路问题。 求哈密顿圈的方法 在一个展区内游览，应该怎样安排游览线路，既能走遍所有的景点，又能使总的行走路线最短？ * * *