美文网首页数学教育
将军饮马——求最短路径

将军饮马——求最短路径

作者: 翔哥_6492 | 来源:发表于2020-09-23 20:49 被阅读0次

       两点之间,线段最短,再简单不过了?只不过隐藏在一些图里就不一定了,不过,在进入正题前我先澄清一下,将军饮马的原型,不是喂马,而是将军如厕!呵呵,我想有许多人都想把这匹马宰了,只不过这匹马只是为了是名字好听而加上去的!闲话说到此,我们言归正传。

目录:

一、两定一动

二、一定两动

三、两定两动

四、定长动线段

一、两定一动

模型1.下图,是一切将军饮马的基础——两点之间,线段最短。如下图,在直线l上找一点P,使PA+PB最小。

在直线l上找一点P,使PA+PB最小

很简单,连接AB,交l于点P,这就出来了。但是变形后就不同了。

模型2原题

模型2.如图,在直线l上找一点P,使PA+PB最小。这道题和两点之间线段最短唯一不同的就是A、B在了同一边,那我们就把A或B点挪到对面不就行了?我们只需让B以直线l为轴做一个轴对称就好了。轴对称出的点B‘只需与A相连即可(别忘了哪一段要用虚线!)我们从图中不难可以证出两个三角形的全等,所以BP等于BP’,所以P点即为所求。

如图,在直线l上找一点P,使PA+PB最小

二、一定两动

模型3、4原题

模型3.如图,点P在锐角∠AOB内部,在OB边上求作一点N,在OA边上求作一点M,使△PMN的周长最短。这道题的周长最短就是PM+PN+MN的距离最短,我们可以把它看成两个模型1,一个得出PM,一个得出PN,连接MN即可。

如图,点P在锐角∠AOB内部,在OB边上求作一点N,在OA边上求作一点M,使△PMN的周长最短

模型4.如图,点P在锐角∠AOB的内部,在OB上求作一点N,OA上求作一点M,使PM+PN最小。和模型3相比,他只是少了PN一段,OA上一点到OB的距离要想变小,肯定是往OB上做垂了,所以只要对称得出点P的位置做垂就行了。

如图,点P在锐角∠AOB的内部,在OB上求作一点N,OA上求作一点M,使PM+PN最小

三、两定两动

模型5原题

模型5.如图,点P、Q在锐角∠AOB的内部,在OB边求作点N,OA边求作点M,使PM+MN+NQ最小。这里和模型3唯一的区别就是多出一个点Q,我们把这两个点想做一个点,分别向两边做对称,得到P'和Q',连接之后(两点之间线段最短)与OA、OB的交点便是M、N了。

如图,点P、Q在锐角∠AOB的内部,在OB边求作点N,OA边求作点M,使PM+MN+NQ最小

四、定长动线段

模型6原题

模型6:如图,线段MN在直线l上且长为10米,求AM+MN+BN的最小值。这道题只需要将A向右平移10米后到A',连接A'B得到点N,再将点N向左平移10米得到点M,连接AM、BN即可。

如图,线段MN在直线l上且长为10米,求AM+MN+BN的最小值

模型7:

模型7原题  

A,B与直线l的位置如图所示,在直线l上找到M、N两点,且MN=10米,M在N左面,使四边形ABMN的周长最短。此题的基础是模型2,先将A对称下来,在像模型6一样平移再连线即可。

A,B与直线l的位置如图所示,在直线l上找到M、N两点,且MN=10米,M在N左面,使四边形ABMN的周长最短。

模型8:

模型8原题

在直线l1和直线l2上分别找M、N点,且MN⊥l2,使AM+MN+NB的取值最小。此题和模型7其实是一样的,首先,MN是定值,不用考虑,所以只需寻找AM+NB。先将A向下平移MN的距离,得到A',再连接A'B,交l2于点N,进而可得点M,连接AM、MN、NB即可

在直线l1和直线l2上分别找M、N点,且MN⊥l2,使AM+MN+NB的取值最小。

致此,常用的将军饮马模型基础,便没了。

谢谢!

相关文章

  • 将军饮马——求最短路径

    两点之间,线段最短,再简单不过了?只不过隐藏在一些图里就不一定了,不过,在进入正题前我先澄清一下,将军饮马的...

  • Yen的K条最短路径算法(KSP)

    一、问题介绍 1.求K条最短路径的必要性 最短路径问题分为: 单源最短路径 所有顶点对间的最短路径 共同的缺陷:这...

  • 最短路径算法

    最短路径算法可以分为两类:单源最短路径问题:从某固定源点出发,求其到所有其他顶点的最短路径。多源最短路径问题:求任...

  • 图-最短路径-弗洛伊德算法

    多源点最短路径-弗洛伊德算法(Floyd) 求所有顶点到所有顶点的最短路径,而迪杰斯特拉是求单源点到所有顶点的最短...

  • FLoyd算法

    适用:求给定顶点间的最短路径。

  • 最短路径

    无权图的最短路径用BFS来求 O(|V|+|E|) 有向带权图两点之间的最短路径也包含了路径上其他顶点间的最短路径...

  • PROB: comehome & fracdec

    comehome:赤裸裸的最短路径 出口都给了,求每个点的最短路径,之中再选最短的即可。 数据量很小,只有 52 ...

  • 在CPLEX中求解最短路径问题

    最短路径问题顾名思义,即求问题的最短路。如有以下问题,图中有1-5五个结点,求node1到node4的最短路径。答...

  • 弗洛伊德算法求图的最短路径 JavaScript实现

    弗洛伊德算法求图的最短路径 JavaScript实现 核心思想我们假设Dis(i,j)为节点u到节点v的最短路径的...

  • 2021-06-04 从例题看Dijkstra算法

    /背景/在图论的学习中,非常有实用性的一个课题:最短路径。这里讨论一下Dijkstra算法求最短路径。**用于图中...

网友评论

    本文标题:将军饮马——求最短路径

    本文链接:https://www.haomeiwen.com/subject/jdifektx.html