初中数学［最短路径问题］典型题型及解题技巧 最短路径问题中, 关键在于，我们善于作定点关于动点所在直线的对称点，或利用平移和展开图来处理。这对于我们解决此类问题有事半功倍的作用。理论依据：“两点之间线段最短” ，“垂线段最短”，“点关于线对称”，“线段的平移”“立体图形展开图”。教材中的例题“饮马问题”，“造桥选址问题”“立体展开图”。考的较多的还是“饮马问题” 。 知识点：“两点之间线段最短”，“垂线段最短”，“点关于线对称”，“线段的平移”。“饮马问题”，“造桥选址问题”。考的较多的还是“饮马问题” ，出题背景变式有角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等。解题总思路：找点关于线的对称点实现“折”转“直” ，近两年出现“三折线”转“直”等变式问题考查。 一、两点在一条直线异侧例：已知：如图，A，B在直线L的两侧，在L上求一点P，使得PA+PB 最小。 解：连接AB,线段AB 与直线L 的交点P ，就是所求。（根据：两点之间线段最短.） 二、两点在一条直线同侧 例：图所示，要在街道旁修建一个奶站，向居民区A 、B 提供牛奶，奶站应建在什么地方，才能使从A、B 到它的距离之和最短． 解：只有A、C 、B在一直线上时，才能使AC +BC最小．作点A 关于 直线“街道”的对称点A′，然后连接A ′B，交“街道”于点C，则 点C 就是所求的点． 、一点在两相交直线内部 例：已知：如图A 是锐角∠ MON 内部任意一点，在∠ MON 的两边 OM ，ON 上各取一点B，C ，组成三角形，使三角形周长最小.
解：分别作点A 关于OM ，ON 的对称点A ′，A OM ，ON 于点B、点C ，则点B、点C 即为所求分析：当AB 、BC 和AC 三条边的长度恰好能够体现在一条直线上时，三角形的周长 最小 例：如图，A.B 两地在一条河的两岸，现要在河 上建一座桥MN ，桥造在何处才能使从A 到B 的路径AMNB 最短？（假设河的两岸是平行的直线，桥要与河垂直） 解：1.将点B 沿垂直与河岸的方向平移一个河宽到E， 2.连接AE 交河对岸与点M, 则点M 为建桥的位置，MN 为所建的桥证明：由平移的性质，得 BN∥EM 且BN=EM, MN=CD, BD ∥CE, BD=CE, 所以A.B 两地的距:AM+MN+BN=AM+MN+EM=AE+MN, 若桥的位置建在CD 处，连接AC.CD.DB.CE, 则AB 两地的距离为： AC+CD+DB=AC+CD+CE=AC+CE+MN, 在△ACE 中，∵ AC+CE >AE, ∴AC+CE+MN >AE+MN, 即AC+CD+DB >AM+MN+BN 所以桥的位置建在CD 处，AB 两地的路程最短。 例：如图，A、B 是两个蓄水池，都在河流a 的同侧，为了方便灌溉作物，?要在河边建一个抽水站，将河水送到A、B 两地，问该站建在 连接A ′，A ″，分 别交 B
对“造桥选址问题”的再认识 问题A和B两地在一条河的两岸，现要在河上造一座桥MN.桥造在何处可使从A到B 的路径AMNB最短? (假定河的两岸是平行的直线，桥要与河垂直.) 教科书的分析是: 把河的两岸看成两条平行线a和b (图1),N为直线b上的一个动点，MN垂直于直线b，交直线a于点M.这样，上面的问题可以转化为: 当点N在直线b的什么位置时，AM＋MN＋NB最小? 由于河岸宽度是固定的，因此当AM + NB最小时，AM+MN+NB最小.这样，问题就进一步转化为:当点N在直线b的什么位置时，AM＋NB最小? 这两段分析我们能看懂、能理解，也指明了解题的方向.而接下来的一段分析让我们费解: 如图2，将AM沿与河岸垂直的方向平移，点M移动到点N，点A移动到点A'，则AA'=MN ,AM+NB = A' N+NB.这样，问题就转化为:当点N在直线b的什么位置时，A'N+NB 最小? 我们经过认真的辩论后认为:此时桥MN并未确定，只是任意的一个位置，所以平移AM 的目的只是将点A移动到点A'.事实上，将“点A移动到点A'”即是忽略河宽，将河的两岸重合 在这种认识下，我们提出了一种新的解题思路，供同学们参考，将河岸a向b平移，直至重合，如图3.相应地，点A也平移到A'，由平移性质，AA'长即为河宽，根据两点之间线段最短，连结A' B，与直线b相交于点N，点N即为造桥处. 作法如图4，过点A作河岸a的垂线，在垂线上截取AA' 等于河宽， 连结A'B交b于点N，作MN垂直于b并交a于点M，则MN为所造之
桥.此时路径AMNB是最短 证明在河上任架一座异于MN的桥M'N' (显然M'N'与MN相等)，连结AM'、BN'、A'N'.由AA'MN，可知四边形AMN A'是平行四边形，所以AM＝A'N.同理四边形AM'N'A'也是平行四边形，所以AM'=A'N'.故AM+MN+NB＝A' N+MN+NB＝A'B＋MN＜A' N'+N' B+M' N'＝AM'+M'N'+N'B，即AM+MN+NB最小. 拓展思考若A与B之间有两条河(如图5)，你能找出使A到B路径最短的造桥地点吗? 同学们自己试一试吧.
13.4课题学习最短路径问题 六街中学：罗云膑1．最短路径问题 (1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求． 如图所示，点A，B分别是直线l异侧的两个点，在l上找一个点C，使CA＋CB最短，这时点C是直线l与AB的交点． (2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求．如图所示，点A，B分别是直线l同侧的两个点，在l上找一个点C，使CA＋CB最短，这时先作点B关于直线l的对称点B′，则点C是直线l与AB′的交点． 为了证明点C的位置即为所求，我们不妨在直线上另外任取一点C′，连接AC′，BC′，B′C′，证明AC＋CB＜AC′＋C′B.如下： 证明：由作图可知，点B和B′关于直线l对称， 所以直线l是线段BB′的垂直平分线． 因为点C与C′在直线l上， 所以BC＝B′C，BC′＝B′C′. 在△AB′C′中，AB′＜AC′＋B′C′， 所以AC＋B′C＜AC′＋B′C′， 所以AC＋BC＜AC′＋C′B. 【例1】在图中直线l上找到一点M，使它到A，B两点的距离和最小．
分析：先确定其中一个点关于直线l的对称点，然后连接对称点和另一个点，与直线l 的交点M即为所求的点． 解：如图所示：(1)作点B关于直线l的对称点B′； (2)连接AB′交直线l于点M. (3)则点M即为所求的点． 点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题. 2.运用轴对称解决距离最短问题 运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长，是解决距离之和最小问题的基本思路，不论题目如何变化，运用时要抓住直线同旁有两点，这两点到直线上某点的距离和最小这个核心，所有作法都相同． 警误区利用轴对称解决最值问题应注意题目要求根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法．解决这类最值问题时，要认真审题，不要只注意图形而忽略题意要求，审题不清导致答非所问． 3．利用平移确定最短路径选址 选址问题的关键是把各条线段转化到一条线段上．如果两点在一条直线的同侧时，过两点的直线与原直线的交点处构成线段的差最大，如果两点在一条直线的异侧时，过两点的直线与原直线的交点处构成的线段的和最小，都可以用三角形三边关系来推理说明，通常根据最大值或最小值的情况取其中一个点的对称点来解决． 解决连接河两岸的两个点的最短路径问题时，可以通过平移河岸的方法使河的宽度变为零，转化为求直线异侧的两点到直线上一点所连线段的和最小的问题． 在解决最短路径问题时，我们通常利用轴对称、平移等变换把不在一条直线上的两条线段转化到一条直线上，从而作出最短路径的方法来解决问题． 【例2】如图，小河边有两个村庄A，B，要在河边建一自来水厂向A村与B村供水． (1)若要使厂部到A，B村的距离相等，则应选择在哪建厂？ (2)若要使厂部到A，B两村的水管最短，应建在什么地方？ 分析：(1)到A，B两点距离相等，可联想到“线段垂直平分线上的点到线段两端点的距离相等”，又要在河边，所以作AB的垂直平分线，与EF的交点即为符合条件的点． (2)要使厂部到A村、B村的距离之和最短，可联想到“两点之间线段最短”，作A(或 B)点关于EF的对称点，连接对称点与B点，与EF的交点即为所求． 解：(1)如图1，取线段AB的中点G，过中点G画AB的垂线，交EF于P，则P到A，
有趣的造桥选址问题 江苏 刘东升 有一道有趣的造桥选址问题，充分体现了利用平移变换实现问题转化，从而有效求解．我们一起关注： 问题：如图1，A 和B 两地在一条河的两岸，现要在河上造一座桥MN ，桥造在何处才能使从 A 到 B 的路径AMNB 最短（假设河两岸1l 、2l 平行,桥MN 与河岸垂直,A 到1l 的 距离大于河宽.） 图1 图2 方法探究：读懂题意后发现，这个问题要求的“路径AMNB 最短”实际是就是“AM +BN ”最短，因为本题中附加条件是“桥要与河垂直”，也就是说桥的长度就是河两岸的距离了（题中假定了河的两岸是平行的直线）．怎样保证“AM +BN ”最短呢如果不是中间有条河隔着，直接连接AB 就可以了！由于河两岸平行,故桥长MN 是一个定值,无论桥架在何处,MN 是必经路线,要使从A 到B 的折线最短,只需AM+BN 最短即可.为此我们不妨将桥MN 平移到A A '处,且M 与A 重合,则N 与A '重合,由平移性质知AM=N A '.由“两点之间,线段最短”的性质知,要使AM+BN 最短(即N A '+BN 最短),只要点N 在线段B A '上即可．为了更为清楚图4 1l 2l A B C A ' M N
的表达这种方法，我们构造出如图2的作图后，再加以说明． 图2的操作步骤是，过点A作AC⊥1l于点C，在线段AC上截取A A'=桥长，然后连接B A'交2l于点N，最后过点N作MN⊥1l于点M.则MN即为所求的架设桥的地点. 很显然，从上面的分析与作图来看，通过平移把桥的固定长度巧妙的化解开去，分析出“AM+BN”最短距离为A`N+BN（也就是点A`到点B之间的线段最短），从而实现了问题的求解．解后反思：这个问题有着非好的实际背景，情境贴近生活实际．从上面的求解方法来看，平移只是问题实现转化中的一个重要策略，怎么联想到平移的其本质还是对“两点之间，线段最短”公理的深刻理解．从这点上说，同学们是值得认真体会和积累的．
图论最短路径问题 在消防选址中的应用 【摘 要】 最短路径问题是图论解决的典型实际问题之一，可用来解决管路铺设、线路 安装、厂区布局和设备更新等实际问题。介绍了图论最短路径问题及其算法，并应用图论最短路径问题的分析方法，解决城市消防站的选址问题。 【关键词】 最短路径；Floyd 算法；消防 1 引言 图论是运筹学的一个重要分支，旨在解决离散型的优化问题，近年来发展十分迅速。在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一。图论中的“图”，并不是通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统。也就是说，几何图形是表述 物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系。它是数学中经常采用的抽象直观思维方法的典型代表。 2 图论基本概念 2.1 图的定义 有序三元组),,(?E V G =称为一个图，其中： (1)),,,(21n V V V V =是有穷非空集，称为顶点集，其元素叫做图的顶点； (2)E 称为边集，其元素叫做图的边； (3)?是从边集E 到顶点集V 的有序或者无序对集合的影射，称为关联函数。 2.2 图的分类 在图G 中，与V 中的有序偶),(j i V V 对应的边e 称为图的有向边(或弧)，而与V 中顶点的无序偶对应的边e 称为图形的无向边，每一条边都是无向边的图，叫做无向图，记为 ),(E V G =；每一条边都是有向边的图叫做有向图，记为),(E V D =；既有无向边又有有 向边的图叫做混合图。 2.3 权 如果图G 中任意一条边),(j i V V 上都附有一个数ij W ，则称这样的图G 为赋权图， ij W 称为边),(j i V V 上的权。
最短路径问题 （导学案） 洪湖市龙口镇和里中学 龚宝金 教学目标： 1知识与技能：理解和掌握解决最短距离问题的一般思想方法 2.过程与方法：培养学生转化思想和数形结合思想 3.情感态度与价值观: 通过专项讲解，归纳出方法和规律，消除学生对此类问题的陌生感 和畏惧感，提高学生解决问题的信心和解决问题的能力。 教学重点：利用轴对称作图确定使距离最短的点 教学难点：数形结合思想与数学建模思想的培养 教学过程 一． 温故而知新1. 在公路l 两侧有两村庄，现要在公路l 旁修建一所候车亭P ，要使候车亭到两村庄的 距离之和最短，试确定候车亭P 的位置。 ★思考：本题运用了 。 随堂练习一. 1. 造桥选址问题：如图，A 、B 两地在一条河的两岸，现要在河上造一座桥MN ，桥造在何 处可使从A 到B 的路径AMNB 最短？（假定河的两岸是平行的直线，桥要与河垂直。） ★思考：本题运用了 。 二．温故而知新2. 如图，在河的同侧有两村庄，现要在河边L 建一泵站P 分别向A 、B 两村庄同时供水，要使泵站P 到A 村、B 村的距离之和最短，确定泵站P 的位置。 ★思考：本题运用了 。 A B
随堂练习二： 1. 如图,已知正方形ABCD ，点M 为BC 边的中点， P 为对角线BD 上的一动点，要 使PM+PC 的值最小，请确定点P 的位置。 2. 如图，已知菱形ABCD ，M 、N 分别为AB 、BC 边的中点，P 为对角线AC 上的一动点，要使 PM+PN 的值最小，试确定点P 的位置。 三．合作探究——拓展与延伸. 1.如图，点P 在∠AOB 内部，问如何在射线OA 、OB 上分别找点C 、D ， 使PC+CD+DP 之和最小？ 2. 饮马问题: 如图牧马人从A 地出发，先到草地边某一处牧马，再到河边饮马，然后回 到B 处，请画出最短路径。 第1题图 第2题图 B A
13.4课题学习最短路径问题(2) 造桥选址问题 教师:朱巧 一、教学目标 1、知识与技能 理解利用平移的方法,解决最短路径问题。 2、过程与方法 (1)在观察、操作、归纳等探索过程中,培养学生的实际动手能力; (2)在运用知识解决有关问题的过程中,体验并掌握探索、归纳最短路径选取的方法。 3、情感态度与价值观 (1)体会数学与现实生活的联系,增强克服困难的勇气与信心; (2)会应用数学知识解决一些简单的实际问题,增强应用意识; (3)使学生进一步形成数学来源于实践,反过来又服务于实践的辩证唯物主义观点。 二、教学重点与难点 1、教学重点 理解如何利用平移,解决造桥选址中的最短路径问题。 2、教学难点 理解路径最短的证明方法。 三、教具:多媒体、三角板 四、教学过程 （一）、知识点回顾 1、两点所有的连线中,线段最短。 2、连接直线外一点与直线上各点的所以线段中,垂线段最短。 应用1:利用轴对称的方法解决最短路径选取问题。 利用轴对称 的方法把已 知问题转化 为容易解决 的问题,这 就是“两点 的所有连线 中,线段最短”的应用。 (二)、提出问题 如果把一条直线l变成两条直线,会变成生活中的什么问题呢？ (三)、新课学习
图(1) 图(2) 环节一:(情境设置)简单介绍著名桥梁专家茅以升、 环节二:把实际问题转化为数学问题、 如上图(1),A 与B 两地在一条河的两岸,现要在河上造一座桥MN 、桥造在何处可使从A 到B 的路径AMNB 最短？(假定河的两岸就是平行的直线,桥要与河垂直、) 分析图(2):把河的两岸瞧成两条平行线 a 与b ,N 为直线b 上的一个动点,MN 垂直于直线b,交直线a 于点M,这样,上面的问题可以转化为下面的问题,当点N 在直线b 的什么位置时,AM+MN+NB 最小？ 引导学生发现,由于河宽就是固定的,即MN 不变,求AM+MN+NB 的最小值只要求AM+NB 的最小值即可。 环节三:请同学们各抒己见如何求AM+MN+NB 的最小值、 环节四:用几何画板展示造桥选址问题、 通 过 几 何 画 板 的 动 画 演 示, 让 学 生找到动点N 在什么位置时, AM+MN+NB 最小。 环节五:如何证明AM+MN+NB<1111AM M N N B ++ ? 环节六:引导学生归纳方法:利用平移变化把已知问题转化为容易解决的问题,从而做出最短路径的选择。 (四)、拓展应用 拓展1:如图,如果A 、B 两地之间有两条平行的河, 我们要建的桥都就是与河岸垂直的。我们如何找到这个 最短的距离呢？ (请学生分组讨论,如何作图,并请学生代表上台演示) 拓展2:如图,荆州古城河在CC`处直角拐弯,从A 处到 达B 处,需经两座桥:DD`,EE`(桥宽不计),设护城河以 及两座桥都就是东西、南北方向的,如何架桥可使 ADD`E`EB 的路程最短？ (请学生分组讨论,如何作图,并请学生代表上台演示) (五)、小结:造桥选址问题,要使所得到的路径最短,就就是 要通过平移,使得除桥长不变外,把其它路径平移在一条直 线上,从而做出最短路径的选择。这就是“两点所有的连 线中,线段最短”的第二个应用。
最短路径问题（珍藏版） 【问题概述】最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结 点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查． 【十二个基本问题】 【问题 1】 作法 图形 原理 在直线 l 上求一点 P ，使 PA +PB 值最小． 连 AB ，与 l 交点即为 P ． 两点之间线段最短． PA +PB 最小值为 AB ． 【问题 2】“将军饮马” 作法 图形 原理 在直线 l 上求一点 P ，使 PA +PB 值最小． 作 B 关于 l 的对称点 B ＇ 连 A B ＇，与 l 交点即为 P ． 两点之间线段最短． PA +PB 最小值为 A B ＇． 【问题 3】 作法 图形 原理 在直线l 1 、l 2 上分别求点 M 、N ，使△PMN 的周长最小． 分别作点 P 关于两直线的 对称点 P ＇和 P ＇，连 P ＇P ＇与两直线交点即为 M ，N ． ， 两点之间线段最短． PM +MN +PN 的最小值为线段 P ＇P ＇＇的长． 【问题 4】 作法 图形 原理 在直线l 1 、l 2 上分别求点 M 、N ，使四边形 PQMN 的周长最小． 分别作点 Q 、P 关于直线 l 1 、l 2 的对称点 Q ＇和 P ＇ 连 Q ＇P ＇，与两直线交点即为 M ，N ． 两点之间线段最短． 四边形 PQMN 周长的最小值为线段 P ＇P ＇＇的长．
“PA+k·PB”型的最值问题 当k 值为1时，即可转化为“PA+PB”之和最短问题，就可用我们常见的“将军饮马”模型来处 理，即可以转化为轴对称问题来处理。 当k 取任意不为1的正数时，通常以动点P 所在图像的不同来分类，一般分为2类研究。 其中 点P 在直线上运动的类型称之为“胡不归”问题； 点P 在圆周上运动的类型称之为“阿氏圆”问题。 一、“将军饮马”模型 “将军饮马”：把河岸看作直线L ，先取A （或B ）关于直线L 的对称 点A′（或B′），连接A′B （或B′A ），并与直线交于一点P ，则点P 就是 将军饮马的地点，即PA+PB 即为最短路线。 例1. 如图，在锐角△ABC 中，AB=4，∠BAC=45°，∠BAC 的平分线 交BC 于点D ，M 、N 分别是AD 和AB 上的动点，则BM+MN 的最小 值是 。 例2. 如图，在矩形ABCD 中，AB ＝10，AD ＝6，动点P 满足S △PAB ＝ 31S 矩形ABCD ，则点P 到A ，B 两点距离之和PA+PB 的最小值为 ． 例3. 如图，∠AOB=30°，点M 、N 分别是射线OA 、OB 上的动 点，OP 平分∠AOB ，且OP=6，△PMN 的周长最小值为 ； 当△PMN 的周长取最小值时，四边形PMON 的面积为 。 变式：“造桥选址”模型 例4. 如图，已知直线a ∥b ，且a 与b 之间的距离为4，点A 到直线a 的距离为2，点B 到直线b 的距离为3，AB=302．试在直线a 上找 一点M ，在直线b 上找一点N ，满足MN ⊥a 且AM+MN+NB 的长度 和最短，则此时AM+NB 的值为 。 例5. 如图，CD 是直线y=x 上的一条定长的动线段，且CD=2，点A （4，0），连接AC 、AD ，设C 点横坐标为m ，求m 为何值时，△ACD 的周长最小，并求出这个最小值。
2020年中考数学专题突破专题十一：最短路径——造桥选址问 题
专题十一：最短路径——造桥选址问题 【导例引入】 导例：如图1，已知正方形ABCD 边长为3，点E 在AB 边上且BE=1，点P ，Q 分别是边BC ，CD 的动点（均不与顶点重合），当四边形AEPQ 的周长取最小值时，四边形AEPQ 的面积是 ． 【方法指引】 （1）如图，在直线l 上找M 、N 两点（M 在左），使得AM+MN+NB 最小，且MN=d 。 方法：将点A 向右平移d 个单位到A ′，作A ′关于直线l 的对称点A"，连接A"B 交直线l 于点N ，将点N 向左平移d 个单位到M ，点M 、N 即为所求，此时AM+MN+NB 最小为A"B 。 （2）如图，1l ∥2l ，1l ，2l 之间距离为d ，在1l ，2l 分别找M 、N 两点，使得MN ⊥1l ，且AM+MN+NB 最小。
l于点N，将点N向上平方法：将点A向下平移d个单位到A′，连接A′B交直线 2 移d个单位到M，点M，N即为所求，AM+MN+NB的最小值为A′B+d。 （3）如图，点P，Q在∠AOB内，分别在OA，OB上找点C，点D，使四边形PCDQ的周长最小. 方法：分别作P，Q关于OA，OB的对称点P′，Q′,连接P′Q′分别交OA，OB与点C，D，则此时四边形PCDQ的周长最小 本质为转化思想： （1）化同侧为异侧（对称变换）， （2）平移定距离（平移变换）， （3）化折线为直线（两点之间线段最短） “将军饮马”问题主要利用构造对称图形解决求两条线段和差、三角形周长、四边形周长等一类最值问题，会与直线、角、三角形、四边形、圆、抛物线等图形结合，在近年的中考和竞赛中经常出现，而且大多以压轴题的形式出现。【例题精讲】 类型一：两定点两动点形成最短路径型
初二数学最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题- 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题- 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题- 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题- 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．
在直线l 上求一点P ，使PB PA -的值最大． 作直线AB ，与直线l 的交 点即为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ． PB PA -的最大值＝AB ． 【问题11】 作法 图形 原理 在直线l 上求一点P ，使PB PA -的值最大． 作B 关于l 的对称点B ＇作直线A B ＇，与l 交点即为 P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ＇． PB PA -最大值＝AB ＇． 【问题12】“费马点” 作法 图形 原理 △ABC 中每一内角都小于120°，在△ABC 内求一点P ，使P A +PB +PC 值最小． 所求点为“费马点”，即满足∠APB ＝∠BPC ＝∠APC ＝120°．以AB 、AC 为边向外作等边△ABD 、△ACE ，连CD 、BE 相交于P ， 点P 即为所求． 两点之间线段最短． P A +PB +PC 最小值＝CD ． 【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有一 点P ，使PD +PE 的和最小，则这个最小值为（ ） A ．3 B ．26 C ．3 D 6 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 l B A l P A B l A B l B P A B' A B C P E D C B A A D E P B C
中考压轴题突破：几何最值问题大全（将军饮马、造桥选址、胡不归、阿波罗尼斯圆等） 一、基本图形 最值问题在几何图形中分两大类： ①[定点到定点]：两点之间，线段最短； ②[定点到定线]：点线之间，垂线段最短。 由此派生：③[定点到定点]：三角形两边之和大于第三边； ④[定线到定线]：平行线之间，垂线段最短； ⑤[定点到定圆]：点圆之间，点心线截距最短（长）； ⑥[定线到定圆]：线圆之间，心垂线截距最短； ⑦[定圆到定圆]：圆圆之间，连心线截距最短（长）。 举例证明：[定点到定圆]：点圆之间，点心线截距最短（长）。 已知⊙O半径为r，AO=d，P是⊙O上一点，求AP的最大值和最小值。 证明：由“两点之间，线段最短”得AP≤AO+PO，AO≤AP+PO，得d-r≤AP ≤d+r，AP最小时点P在B处，最大时点P在C处。即过圆心和定点的直线截得的线段AB、AC分别最小、最大值。(可用“三角形两边之和大于第三边”，其实质也是由“两点之间，线段最短”推得）。
上面几种是解决相关问题的基本图形，所有的几何最值问题都是转化成上述基本图形解决的。 二、考试中出现的问题都是在基本图形的基础上进行变式，如圆与线这些图形不是直接给出，而是以符合一定条件的动点的形式确定的；再如过定点的直线与动点所在路径不相交而需要进行变换的。 类型分三种情况：（1）直接包含基本图形；（2）动点路径待确定；（3）动线（定点）位置需变换。 （一）直接包含基本图形 例1.在⊙O中，圆的半径为6，∠B=30°，AC是⊙O的切线，则CD的最小值是。 简析：由∠B=30°知弧AD一定，所以D是定点，C是直线AC上的动点，即为求定点D到定线AC的最短路径，求得当CD⊥AC时最短为3。 （二）动点路径待确定 例2.，如图，在△ABC中，∠ACB=90°，AB=5，BC=3，P是AB边上的动点（不与点B重合），将△BCP沿CP所在的直线翻折，得到△B′CP，连接B′A，则B′A长度的最小值是。 简析：A是定点，B'是动点，但题中未明确告知B'点的运动路径，所以需先确定B'点运动路径是什么图形，一般有直线与圆两类。此题中B'的路径是以C为圆心，BC为半径的圆弧，从而转化为定点到定圆的最短路径为AC-B'C=1。
第11讲：轴对称 【问题概述】初中数学最值问题是每年中考必出题，更是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．一．【十二个基本问题】 在直线l上求一点 +PB 值最小。 【问题2】作图 在直线l上求一点 A+PB 值最小． 【问题3】“将军饮马”作图 在直线l1 、l2 上分别 求点M、N，使△PMN 周长最小． 【问题 4】作图 在直线l1、l2上分别求 M 、N ，使四 PQMN的周长最小。
直线m∥ n，在m、 上分别求点M、N，使 m，且AM+MN+BN 值最小。 【问题 6】作图 在直线l上求两点M、 在左），使MN a，并使 +MN+NB 的值最小 作图 l1上求点A，在l2 B，使P A+AB值最小． 【问题 8】作图 A 为l1上一定点，B 上；A 为l1上一定点， B 为l2上一定点，在 上求点M在l1上求点N 作图 在直线l上求一点 PA－的值最小 PB
二．“一次对称”常见模型:在直线 l 上求一点 PB PA －的值最大作图 在直线 l 上求一点 PB －的值最大 .【问题 12】“费马点”作图 ABC 中每一内角都小120°，在△ABC 内求一点P ，使 P A +PB +PC 最小．
选址问题数学模型 摘要 本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立3个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题 针对问题1：0-1规划的穷举法模型。该模型首先采用改善的Floyd-Warshall 算法计算出城市间最短路径矩阵见附录表一；然后，用0-1规划的穷举法获得模型目标函数的最优解，其煤气缴费站设置点分别在Q、W、M社区，各社区居民缴费区域见表7-1，居民与最近的缴费点之间平均距离的最小值11.7118百米。 针对问题2：为避免资源的浪费，且满足条件，建立了以最少分组数为目标函数的单目标最优化模型，用问题一中最短路径的Floyd算法，运用LINGO软件编程计算,得到个社区之间的最短距离，再经过计算可得到本问的派出所管辖范围是2.5千米。最后采用就近归组的搜索方法，逐步优化，最终得到最少需要设置3个派出所，其所在位置有三种方案，分别是：（1）K区，W区，D区；（2）K区，W区，R区；（3）K区，W区，Q区。最后根据效率和公平性和工作负荷考虑考虑，其第三种方案为最佳方案，故选择K区，W区，Q区，其各自管辖区域路线图如图8-1。 针对问题3：建立了双目标最优化模型。首先将问题三转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径Floyd算法，并用MATLAB和LINGO软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为11.8km、11km和12.5km，三组巡视的总路程达到35.3km，路程均衡度为12%,具体巡视路线安排见表9-1和图9.2 。 关键词Floyd-Warshall算法穷举法最小生成树最短路径 1问题重述 1.1问题背景 这是一个最优选址问题，是一种重要的长期决策，它的好坏直接影响到服务方法，服务质量，服务效率，服务成本，所以选址问题的研究有着重大的经济社
13.4 课题学习最短路径问题 1．最短路径问题 (1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求． 如图所示，点A，B分别是直线l异侧的两个点，在l上找一个点C，使CA＋CB最短，这时点C是直线l与AB的交点． (2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求． 如图所示，点A，B分别是直线l同侧的两个点，在l上找一个点C，使CA＋CB最短，这时先作点B关于直线l的对称点B′，则点C是直线l与AB′的交点．
为了证明点C的位置即为所求，我们不妨在直线上另外任取一点C′，连接AC′，BC′，B′C′，证明AC＋CB＜AC′＋C′B.如下：证明：由作图可知，点B和B′关于直线l对称， 所以直线l是线段BB′的垂直平分线． 因为点C与C′在直线l上， 所以BC＝B′C，BC′＝B′C′. 在△AB′C′中，AB′＜AC′＋B′C′， 所以AC＋B′C＜AC′＋B′C′， 所以AC＋BC＜AC′＋C′B. 【例1】在图中直线l上找到一点M，使它到A，B两点的距离和最小． 分析：先确定其中一个点关于直线l的对称点，然后连接对称点和另一个点，与直线l的交点M即为所求的点． 解：如图所示：(1)作点B关于直线l的对称点B′； (2)连接AB′交直线l于点M. (3)则点M即为所求的点．
点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题. 2.运用轴对称解决距离最短问题 运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长，是解决距离之和最小问题的基本思路，不论题目如何变化，运用时要抓住直线同旁有两点，这两点到直线上某点的距离和最小这个核心，所有作法都相同． 警误区利用轴对称解决最值问题应注意题目要求根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法．解决这类最值问题时，要认真审题，不要只注意图形而忽略题意要求，审题不清导致答非所问． 3．利用平移确定最短路径选址 选址问题的关键是把各条线段转化到一条线段上．如果两点在一条直线的同侧时，过两点的直线与原直线的交点处构成线段的差最大，如果两点在一条直线的异侧时，过两点的直线与原直线的交点处构成的线段的和最小，都可以用三角形三边关系来推理说明，通常根据最大值或最小值的情况取其中一个点的对称点来解决．解决连接河两岸的两个点的最短路径问题时，可以通过平移河岸
最短路径问题专项练习 共13页，全面复习与联系最短路径问题 一、具体内容包括： 蚂蚁沿正方体、长方体、圆柱、圆锥外侧面吃食问题； 线段（之和）最短问题； 二、原理： 两点之间，线段最短；垂线段最短。（构建“对称模型”实现转化） 1．最短路径问题 (1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求． 如图所示，点A ，B 分别是直线l 异侧的两个点，在l 上找一个点C ，使CA ＋CB 最短，这时点C 是直线l 与AB 的交点． (2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于 这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求． 如图所示，点A ，B 分别是直线l 同侧的两个点，在l 上找一个点C ，使CA ＋CB 最短，这时先作点B 关于直线l 的对称点B ′，则点C 是直线l 与AB ′的交点． 为了证明点C 的位置即为所求，我们不妨在直线上另外任取一点C ′，连接AC ′，BC ′， B ′ C ′，证明AC ＋CB ＜AC ′＋C ′B .如下： 证明：由作图可知，点B 和B ′关于直线l 对称， 所以直线l 是线段BB ′的垂直平分线． 因为点C 与C ′在直线l 上， 所以BC ＝B ′C ，BC ′＝B ′C ′. 在△AB ′C ′中，AB ′＜AC ′＋B ′C ′， 所以AC ＋B ′C ＜AC ′＋B ′C ′， 所以AC ＋BC ＜AC ′＋C ′B . 【例1】 在图中直线l 上找到一点M ，使它到A ，B 两点的距离和最小． 分析：先确定其中一个点关于直线l 的对称点，然后连接对称点和另一个点，与直线l 的交点M 即为所求的点． 解：如图所示：(1)作点B 关于直线l 的对称点B ′； (2)连接AB ′交直线l 于点M . (3)则点M 即为所求的点． 点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题.
造桥选址问题的拓展 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT
造桥选址问题的拓展 利用平移变换进行造桥选址，是平移变换的一个重要应用。下面就课本中一道习题，加以拓展探究，我们可发现其一般规律。 一、原题再现 如图1，A和B两地在一条河的两岸，现要在河上造一座桥MN。桥造在何处才能使从A到B的路径AMNB最短（假定河的两岸是平行的直线，桥要与河垂直）。（人教课标七年级下册2007年第二版37页第7题） 分析：由于河岸宽度是固定的，造的桥要与河垂直，因此路径AMNB中的MN 的长度是固定的。 我们可以将点A沿与河垂直的方向平移MN的距离到A 1 ，那么为了使AMNB 最短，只需A 1B最短。根据两点之间距离最短，连接A 1 B，交河岸于点N，在此 处造桥MN，所得路径AMNB就是最短路径。如图2。? 证明：如图3，如果在不同于MN的位置造桥M 1N 1 。由于M 1 N 1 =MN=AA 1 ；又根 据“两点之间，线段最短”。可知，AN 1+N 1 B＞A 1 N+NB。? 所以，路径AMNB要短于AM 1N 1 B。?
二、拓展应用? 拓展1：如图4，如果A、B两地之间有两条平行的河，我们要建的桥都是与河岸垂直的。我们如何找到这个最短的距离呢 方法1：仿照上例，可以将点A沿与河垂直的方向平移两个河宽分别到到 A 1、A 2 ，路径中两座桥的长度是固定的。为了使路径最短，只要A 2 B最短。连接 A 2B，交河流2河岸于N，在此处造桥MN；连接A 1 M，交河流1河岸于P，在此处 造桥PQ。所得路径AQPMNB最短。 方法2：此题还可以用以下方法来确定建桥位置。? 如图6，将点A沿与第一条河流垂直的方向平移一个河宽到A 1 ，将B沿与第 二条河垂直的方向平移一个河宽到B 1 ，连接A1B1与两条河分别相交于N、P，在N、P两处，分别建桥MN、PQ，所得路径AQPMNB最短。? 拓展2：如图7，如果A、B之间有三条平行的河流呢
姓名：学号：专业：
图论的实际应用——蔬菜批发市场选址问题 摘要：在现实生活和生产实践中，有许多管理、组织与计划中的优化问题，都可借助图论知识得以解决，而最短路问题是利用图论解决的一个典型的实际问题。图论中最典型的两种求最短路径的算法分别为Dijkstra算法和Floyd算法，其中Floyd算法广泛应用于求任意两点间的最短路径。本文介绍了利于Floyd算法来解决城市蔬菜批发市场选址的问题。 关键词：最短路；Floyd算法；选址问题 0．引言 对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题[5]。在路径的优选计算问题中，最常见的是最短路径问题，最短路径可能是给定两点间的最短路径，也可能是任意各点间的最短路径。而在顶点的优选计算问题中，最为常见的是选址问题，所谓选址问题就是在某一地理区域构成的网络中选择一个顶点，建立服务设施，为该网络中的各个点提供服务，使得服务效率最高[3]。 选址问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。也可以是生产服务设施，如仓库，转运站等等。可以认为，选址问题，就是把服务设施与服务对象，反映与统一的网络中，便于对问题进行研究[4]。尽管对选址的目标、要求有不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到，这是一个最基本的要求。1．最短路径问题 最短路径问题是图论研究的一个经典算法问题，其目的是求出给定两点之间的长最短的路径，这里所说的长具有广泛意义，即可指普通意义的距离，也可是时间或费用等[2]。因此，最短路径问题通常可以归纳为三类：(1)距离意义上的最短路径，即求两点间距离最短的路径；(2)经济意义上的最短路径，即为两点间的费用最少的路径；(3)时间意义上的最短路径，即选择两点间最节省时间的
中考压轴题突破：几何最值问题大全（将军饮马、造桥 选址、胡不归、阿波罗尼斯圆等） 一、基本图形 所有问题的老祖宗只有两个：①［定点到定点］:两点之间，线段最短；②［定 点到定线］:点线之间，垂线段最短。 由此派生：③［定点到定点］:三角形两边之和大于第三边；④［定线到定线］: 平行线之间，垂线段最短；⑤［定点到定圆］:点圆之间，点心线截距最短 （长）；⑥［定线到定圆］:线圆之间，心垂线截距最短；⑦［定圆到定圆］: 圆圆之间，连心线截距最短（长）。 余不赘述，下面仅举一例证明：［定点到定圆］:点圆之间，点心线截距最 短（长）。 已知。O半径为r，AO=d P是。O上一点，求AP的最大值和最小值。 证明：由“两点之间，线段最短”得AP≤AO+PO AO≤ AP+PO得d-r ≤AP ≤d+r，AP最小时点P在B处，最大时点P在C处。即过圆心和定点的直线截得的线段AB AC分别最小、最大值。（可用“三角形两边之和大于第三边”，其实质也是由“两点之间，
线段最短”推得）。 上面几种是解决相关问题的基本图形，所有的几何最值问题都是转化成上述基本图形解决的。 二、考试中出现的问题都是在基本图形的基础上进行变式，如圆与线这些图形不是直接给出，而是以符合一定条件的动点的形式确定的；再如过定点的直线与动点所在路径不相交而需要进行变换的。类型分三种情况：（1） 直接包含基本图形；（2）动点路径待确定；（3）动线（定点）位置需变换。 （一）直接包含基本图形 例1.在。O中，圆的半径为6,∠ B=30°, AC是。O的切线，贝U CD的最小值是。 简析：由∠ B=30°知弧AD一定，所以D是定点，C是直线AC上的动点，即为求定点D到定线AC的最短路径，求得当CDLAC时最短为3。 （二）动点路径待确定 例2.,如图，在△ ABC中，∠ ACB=90，AB=5, BC=3, P是AB边上的动点（不与点B重合），将△ BCP沿CP所在的直线翻折，得到△ B' CP,连接B' A,则B' A长度的最小值是_________________________ 简析：A是定点，B'是动点，但题中未明确告知B'点的运动路径，所以需 先确定B'点运动路径是什么图形，一般有直线与圆两类。此题中B'的路径是以C为圆心，BC为半径的圆弧，从而转化为定点到定圆的最短路径为 AC-B'C=1。