没有驾驶员的自动驾驶汽车可以送披萨。 没有司机的出租车载人。 没有驾驶员的卡车会承载多吨的货物。 如果我们分析所有这些引人入胜的项目，我们将完成不同的典型任务，其中最重要的是路线的搜索和优化。 使用
图论解决了这些问题。 这个主题并不简单，主要在大学或至少在高级专业班学习。 但是在这篇文章中，我将展示如何使用LEGO EV3在高中时就已经学习了图论。 并没有塞满，但应用水平令人着迷。
丹尼的LAB EV3汽车输送机 真正收集乐高汽车。 但这与他无关。为了使无人运输到达需要的地方，它必须能够在给定的点之间建立一条路线。 最短且符合交通规则是可取的。 为了模拟和解决此问题，我们需要LEGO EV3移动平台，以及实际上该平台将在其上移动的地图。
乐高EV3移动平台
我们的移动平台必须配备传感器和伺服器。 您需要的一切都可以在LEGO Mindstorms EV3 45544的基础教育集中找到。这是该平台的外观：
该组装不需要电子学知识，并且花费不超过半小时。 该平台提供了解决问题时提高到更高抽象水平所需的一切。
路线图
让我们以网格形式绘制路线图。 线是道路，交叉点是道路的交叉点：
交叉路口之间的所有路段长度相同，路口上的交通为双向。 一些道路被封锁-它们被标记为“砖”。 此外，地图上的所有转弯都是90度的倍数。 道路网的复杂性不会影响解决问题的原理，为清楚起见，我们将采用一个相当简单的选择。 我们的任务是沿着最短的路径从A点驶向B点。
数
每个交叉点都有自己的坐标-水平和垂直线号。 在图论中，此类交点称为
顶点 。 十字路口之间的道路由箭头指示。 在图论中，这些是
边 。 所有道路都是双向的（双向箭头）意味着该图
是非定向的 。 道路的所有路段的成本（行驶时间）都相同，这意味着该图
未加权 。
邻接矩阵
图片所代表的图形清楚地显示了地图及其内部的连接。 但是，在包括EV3在内的计算机上，处理图形信息非常麻烦。 最好使用矩阵（邻接矩阵）对图进行编码。
如果交叉点之间没有直接连接，则将0放置。如果存在-1.如果存在-1.我们同意相邻的交叉点之间的所有距离都等于1。重量”的情节。 如果考虑到运动方向，则上面的矩阵将是不对称的-在一个方向上它可能是1，在另一个方向上它是0。
有了邻接矩阵，我们的机器人已经可以解决寻找从A到B的最短路径的问题。但是我们有一个二维矩阵，在EV3中只能存储一维数组。 我们可以很容易地通过移位n * Y + X转到一维数组，其中n是矩阵的大小。
Dijkstra的算法
Dijkstra算法（一种用于查找图形的一个顶点与所有其他顶点之间的最短路径的算法）将用于求解。 该算法由荷兰科学家Edsger Dijkstroy于1956年发明。 如果解释尽可能简单，则该算法基于到图的相邻顶点的顺序进度，并不断评估行进的距离。 该算法的一个很好的说明性示例和基本流程图可以在Wikipedia文章中找到。
在我们的例子中，Dijkstra算法流程图（我们的“ Dijkstra”）将如下所示：
根据算法，更好地根据其数学模型，我们已经可以为机器人创建程序。 输入将是邻接矩阵，起点和终点。 完成上述所有操作后，可以快速找到同一地图上任意点之间的最短路径。
当然，除了Dijkstra算法外，我们基于LEGO EV3的机器人还需要一些更简单的程序模块（子程序）：沿着直线移动到相交处，计数相交处，沿两个方向旋转，确定相对于绝对坐标系X，Y，Θ的位置，其中X，Y-网格上的坐标，Θ-机器人的当前方向（通过代码表示，例如1-向上，2-右侧，3-向下，4-左侧）。
这是该问题解决方案的现场演示。 输入数据略有不同，但这不会改变本质。奖励主题：里程表
里程表测量功能可以集成到在地面上移动的任务中，例如，以便迷宫中的机器人可以知道它在哪里以及在哪里移动。 使用测距法，可根据驱动器运动（电机旋转）的数据估算机器人的运动。 知道了轮子的直径，我们就可以计算出机器人在一定时间内的行驶距离。 知道了车轮的角速度，我们可以确定机器人相对于原始物体旋转的角度。 通过设置不同的角速度，我们可以调整机器人沿弧线的移动，并同时确定移动机器人时的“环”，如以下视频所示：
在学校中，三角学得到了很大的关注，但是它的实际应用并未以任何方式涵盖。 用LEGO EV3解决的里程表问题说明了为什么根本需要三角函数的原因。 在实践中，里程表不仅用于运输，还用于例如跟踪CNC机床中的刀具位置（数字控制）。
我在哪里可以学到这一切？
我允许自己做些广告。 上述任务以及更复杂的任务可以由在机器人俱乐部受过训练的7-9年级的孩子解决。 我在叶卡捷琳堡经营一个这样的俱乐部Robit-这是我们的
培训计划 。 我们在其中一个课程中针对上述任务从演示中拍摄了视频。 然后，我们俱乐部的一名八年级生在6个小时内研究了图论的基础知识并解决了类似的问题。
如何选择乐高EV3编程环境
如果没有为LEGO EV3选择正确的编程环境，就不可能解决问题。 有关此领域的最新信息，请
单独阅读 。 我试图教孩子选择一种编程语言来完成任务，而不是选择一种编程语言来学习他们的语法。 但是，低年级的学生很难立即使用基于文本的编程语言工作，因此我们开始研究入门阈值较低的图形语言算法。 从10岁开始，学生将学习EV3 Mindstorms的图形环境。 一些机器人技术竞赛仅将工具包限制在此环境中。
从12岁开始，这些家伙就开始掌握EV3 Basic环境。 该环境相对容易学习，并且Basic为LEGO EV3平台提供了强大的功能。 此外，我们在EV3Dev环境中编程，您可以在其中安装许多不同的语言-Python，Java和C。使用EV3Dev，他们可以在流行的流行语言中获得第一手经验。 与其他环境相比，EV3Dev的唯一缺点是传感器轮询速率相对较低。 通过正确的方法，LEGO EV3成为了解编程的绝佳工具。 当学生看到他们的代码将生命注入构造函数中时，这就是一个极好的动力。
接下来是什么？
在高中时期就已经研究过这种算法，孩子们将能够进一步巩固他们的知识，例如参加真正给予奖金的设计和主题奥林匹克竞赛-例如，大学入学考试中自动获得100分。