Treats_Photo_Anne-Karakash_via-Pixabay

中国邮递员和糖果

分享:

Malgosia Ip、数学与统计数据编辑器

在短短4周,你的邻居可能会被僵尸占领。不,这不是世界末日。万圣节:今年有一天当你的孩子漫步街头,寻找高糖。

但是你不是随便一个家长,你有重要的事情要做和Netflix显示观看。你要确保你所有的街道社区在最短的时间内。

那么我们如何找出最优路线?我们问一个中国邮递员。

中国邮递员问题

中国的邮递员是一个领域的数学问题吗图论旨在找到最短的路线沿着街道。很容易看到相似之处这个问题和我们的万圣节的场景。我们都想找到最短的路线以及所有的街道附近,而是传递邮件,我们收集糖果。

首先,我们需要看看我们的社区地图作为一个图,这是一组顶点(在我们的例子中,十字路口)连接边缘(街道)。我们想要找到最短的路线,沿着每条边至少一次。

Figure1_Malgosia-Ip

看我们的邻居图或网络。

我们可以潜水在尝试画一个路线,但确保我们得到最短的一个,我们必须找到所有可能的路线和比较。这就是所谓的蛮力方法,它不仅是乏味,但它需要更长的时间和更长的时间来找到解决方案更多的街道我们添加。

我们需要的是一个算法:一组指令或方程我们可以使用,可以解决这个问题的速度比蛮力的方法。

在我们继续下去之前,我要介绍一些数学术语。我们需要确定是否我们的图是欧拉。如果可以沿着整个图使用每条边只有一次,那么它就是欧拉。早在1700年代,欧拉证明了这是可能的,如果且仅当,图的所有顶点甚至——也就是说,他们有偶数个边缘连接。

Figure2_Malgosia-Ip

欧拉的定义与复杂性无关。左边的图是欧拉(每个顶点甚至)和右边的不是。去检查!

如果我们的图是欧拉,那么我们的工作就完成了。穿过每条边的路径只有一次是根据定义的最短路径,我们可以使用一个算法如Hierholzer方法找到它。我不会进入Hierholzer方法的细节,但是这个网站有一个很好的一步一步解释。

如果我们的图不是欧拉,那么我们需要使其欧拉。数学家喜欢做这种事情,不是找到一个全新的解决方案,这是对你的问题看起来已经有了解决方案。

做出任何欧拉图,我们需要双一些边缘,这样所有的顶点变得更加。但还有一个问题:因为我们试图找到最短的路线,我们需要确保边缘的长度我们添加的是最小化。在下面这个简单的例子中,我们将添加一个边缘从A到B再次甚至让所有顶点。

Figure3_Malgosia-Ip

通过添加一个A和B两个奇怪的顶点之间的边,我们可以把左边的图(非欧拉)到右边的图(欧拉)。数据显示有多少边缘连接到每个节点。

添加边在更复杂的例子,但是,提出了一种全新的和不同的问题。它被称为一个匹配的问题,因为你想匹配使他们变得更加奇怪的顶点在一起。

进入加拿大的数学家杰克埃特蒙德在早期的年代,谁是在相对较新的滑铁卢大学工作吗组合和优化。埃特蒙德设计了一个算法来解决匹配问题在多项式时间”——这是数学语言来说相对迅速,像所有算法的圣杯。他叫他的解决方案开花的算法因为它看起来在闭合回路图,它可以像花朵。爱德蒙的算法也适用于任何类型的图,像不像其他算法匈牙利法

Figure4_Malgosia-Ip

爱德蒙的匹配算法称为开花算法因为它将关闭循环图,它可以像花朵。

当然,如果你想找到你的最佳万圣节路线使用这些方法,你仍然需要使用合适的算法或创建一个程序找到一些现成的代码——因为没有数学技巧,允许您手动解决问题或在你的脑海中。但由于埃德蒙兹的“不给糖就捣蛋”算法,最优路线可以有效地找到,不需要超级计算机。

现在要是有一个算法来处理高的孩子。

30一个€€””

分享: