雷竞技rebat前沿的年轻人

雷竞技rebat前沿的年轻人
菜单
核心概念 数学 发表:2021年12月10日

在网络上找到你的方法:最短路径

文摘

旅行到不同的目的地是我们生活的重要组成部分。我们参观各种各样的地点在我们的日常生活和当我们度假。我们如何找到最好的方式从一个地方到另一个导航吗?也许我们可以测试所有不同的两个地方之间的旅行方式,但另一种方法是使用数学和计算它们之间寻找最短路径。在本文中,我们讨论如何构造并介绍迪杰斯特拉最短路径算法来最小化总成本的路径,成本可能是旅行的距离,出行时间,或其他一些数量。我们还将讨论如何使用最短路径在现实世界中旅行节省时间和提高效率。

一条路径是什么?

每一天,我们决定哪些航线之间使用旅行不同的地方。在你的家里,你可能从你的卧室到厨房。你家外面,你可能从你的家到学校旅行。假设我们有一个网络的地方彼此连接的街道和人行道。每一个位置被称为节点,街道和人行道边缘。的“邻居”节点的节点连接的优势。一个路径是一个序列的边缘一个源节点和目的节点之间(1,2]。

最短路径

在数学中,人们研究路径构造短路径的长度。通常很有用找到最短路径。两个节点间的最短路径是一个路径,最少的边缘,如果成本旅行的每条边都是一样的(例如,如果每条边的街道长度相同)。更普遍的是,给定一个源节点和目的节点,最短路径从源节点到目标节点的路径,最低的总成本在所有路径从原点到目的地(1]。计算成本的一个路径,总结它的所有的个人成本边缘。成本可以测量距离、时间或别的东西。例如,在小城市地图图1最短路径,从家到学校可能要花最少的时间之一的可能路径。可以有一个以上的网络中两个节点之间的最短路径,因为多个路径可以有相同的最低成本。这就是为什么我们称“a”两个节点之间的最短路径(尽管这听起来很奇怪),而不是“”他们之间的最短路径。

图1 -在这个小城市地图,它是一个网络的例子,位置(即。1比4节点),发生在街道之间的十字路口(即。,边缘)。
  • 图1 -在这个小城市地图,它是一个网络的例子,位置(即。1比4节点),发生在街道之间的十字路口(即。,边缘)。
  • 每一个位置(蓝色和红色房子,池塘,学校,和杂货店)也是一个节点。活动1:跟踪路径从蓝色的房子到学校在地图上。这街道(即。,边缘) do you take in the picture? Which streets do you take when you travel from your home to school in real life? (This figure is inspired by the figure athttp://clipart-library.com/clipart/449476.htm。我们的图也使用公共剪贴画。)

你可能已经考虑最短路径在日常生活中当你要去不同的地方。在bedroom-to-kitchen的案例中,它将没有多大意义从卧室走,然后到洗衣房,然后到外面你的后院,最后你的厨房,如果你只是想旅游从卧室到厨房。是更快的直接从卧室走到你的厨房没有停止在洗衣房和后院。在一次相互接近的位置,只有几街十字路口(即。节点),你可以尝试大多数不同的路径来找到最短路径。但如果位置更远的拆解为例,你的家,你的学校,和一个玩具商店在不同的城市找到一个最短路径是更加困难的。如谷歌地图导航工具如何确定最好的方式到达目的地?一种方法是解决最短路径问题,这是两个节点之间找到一个路径的数学问题,最小化成本之和的边缘路径1。

在数学中,我们经常使用数字标签节点(参见的十字路口图1(参见)或字母图2)。也为简单起见,我们假设一切都是二维的(例如在画在一张纸上),所以我们将测量距离的方式,我们将测量两个点之间在家里的地板上。我们不会担心高度或地球的曲率。在网络图2,如果我们想要找到一个从节点到节点的最短路径,我们应该选择成本最低的边缘。例如,而不是选择优势与成本4从节点到节点B,我们选择成本的边缘2 c从节点到节点选择成本最低的边缘找到最短路径的一个关键的想法迪杰斯特拉算法2,3。

下面图2 -在这个网络,高亮显示的蓝色箭头显示了我们从节点到节点的最短路径。
  • 下面图2 -在这个网络,高亮显示的蓝色箭头显示了我们从节点到节点的最短路径。
  • 数字显示边缘的成本(不按比例画)。蓝色箭头显示最短路径生成树有一个源节点。观察到从节点到节点的最短路径是最短路径生成树的一部分。“距离”这个标签显示的总距离“起源”特定节点,节点和标签“最后”表示最后一个节点,通过达成特定的目标节点的“起源”a章节“迪杰斯特拉算法”,我们给出一个详细的解释的步骤来确定最短路径。(这个数字是灵感来自网上的数据1,3。]
图3 -活动2:现在轮到你了!使用迪杰斯特拉算法找到最短路径生成树从原点到network5每个其他节点。
  • 图3 -活动2:现在轮到你了!使用迪杰斯特拉算法找到最短路径生成树从原点到每个其他节点在这个网络5。
  • 我们已经完成第一步的迪杰斯特拉算法。(这个数字是灵感来自网上的一个活动1。]

迪杰斯特拉算法

一组“算法”是一个精确的步骤来解决一个问题,如最短路径问题1]。迪杰斯特拉算法是一个著名的最短路径算法;这是其发明者的名字命名的Edsger Dijkstra,荷兰是一个著名的计算机科学家4。可以使用迪杰斯特拉算法来创建一个最短路径生成树(参见图2)找到最短路径从一个源节点到每个网络中其他节点分别到原点的距离计算每一个其他节点。在这个讨论中,我们使用的是距离我们的成本,但可以使用迪杰斯特拉算法的任何类型的成本。

在图2,我们将展示如何使用迪杰斯特拉算法构造一个连接网络的最短路径生成树。请按照图2当你阅读我们的解释,手表视频1这个例子的一个动画。

  • 视频1 -图2介绍:跟随这个视频的解释的一个例子使用迪杰斯特拉算法来找到一个网络的最短路径生成树图2。

这是我们采取的步骤:

1。我们阴影的“起源”节点。(参见节点图2)。为每个源节点的邻居,我们设置的初始值“经销”到原点的距离节点邻居和初始值的“最后”原点节点。在这个例子图2,到这一步,我们填写的值“距离”和“最后”节点B和c的“距离”和“最后”项节点D, E, F仍然空白。

2。我们确认没有阴影的“距离”价值最低的节点(不含空格)和标签这个作为我们的“当前”节点。例如,如果我们开始节点为原点,那么当前节点节点C,因为“经销”从A到C小于“经销”从A到b。如果有领带,我们选择任何节点的最小的“距离”价值。

3所示。我们做以下步骤为每个无遮蔽的邻居“当前”:

。我们添加的“距离”“当前”的成本优势从“当前”到你的邻居。

从步骤3 b。如果“经销”比邻居的小“经销”(或者邻居的“距离”仍然是空白的),我们更新了邻居的“距离”的“距离”,我们计算步骤3 a和设置当前节点邻居的“最后一次”。

4所示。我们完成第3步后所有无遮蔽的邻居的”,“我们在“当前”阴影,划掉的标签“当前”。

5。如果所有节点都是阴影,我们去第六步。否则,我们回到第2步。

6。我们强调每个节点之间的边和它的“最后”节点,以揭示的最短路径生成树的起源。

应用程序

使用迪杰斯特拉算法,我们可以找到一个最短路径从一个源节点到其他节点在网络中。如果你觉得你的家庭起源节点和目的地其他节点在网络中,你可以确定一个好的路线从你的家到你想去的任何地方。假设您想要参观几个地方才回家。你如何找到最佳的方式来访问所有这些目的地同时最小化费用,如气体、酒店、和时间?更抽象,我们怎样才能找到一条最短路径,穿过所有网络中节点,并返回到起始节点?这个问题,这是一个扩展的最短路径问题,被称为“旅行推销员问题”6。

寻找最短路径对解决问题很重要在许多不同类型的网络。例如,最短路径可以提高城市规划的效率。土木工程师可以代表一个城市作为一个网络和确定最佳位置修建公路,以减少交通拥堵和最好的位置放置灌溉管道输送水人口(2]。找到最短路径还允许数据从一台计算机转移到另一个在高速度,允许大量的旅游信息在几秒钟内(1,2]。

也有许多短路径沟通和社交网络的例子。例如,假设每一个人在一个社交网络是一个节点,每条边代表了友谊。你可以找出如何连接到你的友谊团体以外的人通过你的朋友的联系。最短路径的连接(如友谊)两个随机的美国人比一个短。平均而言,一个起源的人之间有少于六个步骤和一个目的地的人在这样一个路径(3]!人们之间的最短路径的典型脆性说明了“小世界现象,”这些短路径长度也激发了术语“六度分离”1]。第二个例子与时事。COVID-19大流行期间,发现短路径已被用于限制导致COVID-19暴露于病毒。例如,当移动在一个超市在过去的一年半,这是有利于找到短路径去接杂货(同时避免接触别人通过物理距离)(4,5]。

结论

最短路径从一个地方到另一个旅行时是很重要的。他们有大量的应用程序在许多类型的网络,可以帮助解决各种现实问题。从家庭度假计划探索我们的世界是如何连接的,网络的最短路径的研究是非常重要的,形成了更为复杂的基础调查。

术语表

网络:↑一个对象集合(称为“节点”)和它们之间的连接(称为“边缘”)。

节点:↑的对象在一个网络连接到其他对象。例如,在图1,每个位置和每个街十字路口是一个节点。

边缘:↑连接两个节点的对象。例如,旅行时从你的家到学校,每个街道都是优势。

路径:↑一系列的边缘从源节点到目标节点。

成本:↑衡量多少努力才能沿着一个网络的边缘。在现实生活中,成本可以测量距离,时间,或者别的东西。

最短路径:↑路径从源节点到目的节点的最低总成本在所有路径从起源到目的地。

最短路径生成树:↑连接网络的一部分,从一个给定的源节点,它指定了一个最短路径节点网络。例如,如果一个网络6节点,有5个这样的最短路径最短路径生成树。生成树的网络包括网络的所有节点。此外,由于网络生成树是一种称为“树”,任何一对节点之间有一个路径。

的利益冲突

作者声明,这项研究是在没有进行任何商业或财务关系可能被视为一个潜在的利益冲突。

确认

我们感谢年轻readers-Nia邱Taryn邱佐伊邱,第谷埃林,和鼠尾草Hansen-for许多有用的评论。我们也感谢家人members-Lyndie邱,克里斯蒂娜Chow,蒂姆•埃林和英镑Hansen-for把我们与他们联系,征求他们的反馈。我们也感谢Lyndie邱,米歇尔·李,托马斯•Rexin和Akrati Saxena有用的评论。我们也感谢我们的年轻的评论家和他们的导师的许多优秀的建议。地图承认国家科学基金会的支持(批准号1922952)通过威胁检测(ATD)计划的算法。

引用

[1]↑纽曼,m . e . j . 2018。网络,第二版。英国牛津:牛津大学出版社。

[2]↑克莱默,C。,Porter, M. A., Sayama, H., Sheetz, L., and Uzzo, S. (eds). 2015.网络文化:基本概念和核心思想。网上:http://tinyurl.com/networkliteracy

[3]↑米尔格拉姆,s . 1967。小世界的问题。Psychol今天1:61-7。doi: 10.1037 / e400002009 - 005

[4]↑布鲁克斯,h . Z。,Kanjanasaratool, U., Kureh, Y. H., and Porter, M. A. 2021. Disease detectives: Using mathematics to forecast the spread of infectious diseases.前面。年轻人9:577741。doi: 10.3389 / frym.2020.577741

[5]↑应,F。,and O’Clery, N. 2021. Modelling COVID-19 transmission in supermarkets using an agent-based model.《公共科学图书馆•综合》16:e0249821。doi: 10.1371 / journal.pone.0249821

附录

答案

活动1:一个可能的路径(主要,榆树,学者)。另一个可能的路径(主要、橡树,棕榈,学者)。第三个可能的路径是(松、枫木,学者)。

活动2:这里的一个例子是一个网络的最短路径生成树完成图3。跟随我们的解释视频2。

脚注

[1]↑维基百科》2020。最短路径问题。网上:https://en.wikipedia.org/wiki/Shortest_path_problem(2020年8月20日通过)。

[2]↑发音名字Dijkstra算法时,“j”是沉默。

[3]↑Code.org。2020年。U2L07活动guide-Dijkstra的最短路径算法。网上:https://docs.google.com/document/d/15N7aHAoWG1_9VIcDHNZRygzFK0hle-EHlmHu0PZI8D4/view(2020年8月20日通过)。

[4]↑维基百科》2020。Edsger Dijkstra算法(george w . bush)。网上:https://en.wikipedia.org/wiki/Edsger_W._Dijkstra(2020年8月20日通过)。

[5]↑你可以下载一个可打印版的图3从https://drive.google.com/file/d/1rNONK-cmy4gq_aCJRnAYpe9Y2HSeq2A1/view。

[6]↑看到https://www.youtube.com/watch?v=q8nQTNvCrjE&t=35s。