简单的数学运算如何改变算法

小灰灰 2024-02-22 09:04 10阅读 0赞

![5c057f32c9d4085e81dc40323a2db0e5.jpeg][]

**简单的数学运算如何影响事物**

当你坐在无人驾驶汽车上行驶时，突然发现前面有一个问题。一个亚马逊快递司机将他们的货车开到了一辆双停的UPS卡车旁边，然后才意识到无法通过。现在他们卡住了，你也卡住了。

![44e2d02a805601f0a81b3c715e62e57a.png][]

街道太窄，无法实现U型转弯，所以你的AI增强汽车开始进行一个三点转弯。首先，汽车沿着一侧的曲线路径前进。

一旦到达那里，它会向另一侧转向，然后向相对侧的人行道后退。然后它再次将方向盘转向第一侧的曲线路径，向前驶离障碍物。

![f7deb6a4447d59a2a51d1d213544a4d9.png][]

这种通过中间转向的简单几何算法可以帮助你在狭窄的情况下绕过障碍物。 如果你曾经并排停车，你就知道这种前后摆动可以帮助你。

这里有一个关于车辆绕过的空间有多大的有趣数学问题，数学家们已经研究了一个理想化的版本超过100年。

这始于1917年，当时日本数学家柿谷宗一提出了一个听起来有点像我们的交通堵塞的问题。假设你有一根长度为1的无限细的针。

你可以将针旋转180度并将其返回到原始位置的最小区域是多大？这就是柿谷的针问题，数学家们仍然在研究它的各种变体。

让我们看看使柿谷的针问题如此有趣和令人惊讶的简单几何学。

像许多数学问题一样，这个问题涉及到一些简化的假设，使问题不那么现实，但更容易管理。

例如，车辆的长度和宽度在驾驶时很重要，但我们将假定我们的针的长度为1，宽度为零。

这意味着针本身的面积为零，这在解决问题中扮演了重要角色。此外，我们将假设针可以围绕其前端、后端或中间的任何一点旋转，不像车辆一样。

目标是找到允许针旋转180度的最小区域。找到满足一定条件的最小的东西可能会有一定的挑战，但开始的好方法是寻找任何满足这些条件的东西，看看你可以在途中学到什么。

例如，一个简单的答案是只需将针围绕其端点旋转180度，然后将其向上滑动。这将针恢复到其原始位置，但现在它指向相反的方向，正如柿谷的针问题要求的那样。

![b1a26e654f51ab932135419da4a867e3.png][]

所需转弯的区域是半圆，半径为1，其面积是

![22974fc79ec2ed08d4fcd4c54c97ee66.png][]

因此，我们找到了一个可行的区域。

通过充分利用我们神奇的数学针绕其任何点旋转的能力，我们可以做得更好。与其围绕其端点旋转，不如围绕其中点旋转。

![34d16ddeabbea7a9e0d6456db288dea5.png][]

我们可以从我们的无人驾驶汽车困境中获得灵感，考虑使用类似于针的三点转弯。这实际上非常有效。

使用这种技术扫掠的针产生的区域称为三叶线，它也满足柿谷的要求。

计算它的面积需要更多比我们在这里讨论的基础几何学了解参数曲线的知识有所帮助)，但事实证明，这个特定的三叶线的面积——由长度为1的线段扫出的三叶线——恰好是π的1/8。

![f3bb672ff354ee9ebf22b4dd656a9ef4.png][]

现在我们找到了一个更小的区域，可以让柿谷的针绕过，你可能会原谅我认为这就是我们所能做到的最好的。

但是当俄罗斯数学家阿布拉姆·贝西科维奇发现你可以无限制地做得更好时，这个针问题发生了巨大的变化。他提出了一种方法，可以消除区域的不必要部分，直到它足够小。

这个过程是复杂的，但基于贝西科维奇的想法的一个策略依赖于两个简单的思想。首先，考虑下面的直角三角形，高度为1，底边为2。

![193067a7a6016708ca4b5db446bc1e33.png][]

现在，我们暂时忘记完全将针旋转一周，只关注一个简单的事实：如果我们将长度为1的针放在顶点上，这个三角形足够大，可以让针从一侧旋转90度到另一侧。

![03ad926b23a6c74cd56fe2d0536f450b.png][]

现在，这里是第一个重要的思想：

我们可以减小区域的面积，同时保持90度的旋转。策略很简单：我们将三角形切成两半，然后将两半推在一起。

![96642680d1bcadac937e95bc7dfba0d7.png][]

这个新图形的面积必须小于原来的，因为三角形的一部分现在重叠在一起。事实上，计算这个图形的面积很容易：它只是边长为1的正方形的四分之三，所以面积是 A = 3/4，这小于我们开始的三角形的面积。

而且，我们仍然可以将针指向以前的所有方向。只有一个问题：原始角度被分成了两部分，所以这些方向现在分成了两个独立的区域。

![b309e9db8055fe0c1a4f0101fcdd307d.png][]

如果针在新区域的左侧，我们可以将其旋转45度，位于南和东南之间，如果在右侧，我们可以将其旋转45度，位于南和西南之间，但由于两个部分被分开，似乎无法像以前那样旋转90度。

这就是第二个重要的想法。有一种狡猾的方法可以让针从一侧移动到另一侧，而不需要太多的区域。在国际象棋中，你可能知道骑士以L形移动。好吧，我们的针将以N形移动。

![5620dac64257f8c45eeda0e5847a2bb2.png][]

这是它的操作方式。首先，针沿着N的一侧滑动。然后，它旋转以指向对角线，然后滑下。然后它再次旋转，完成其行程，滑到N的另一侧。

![44b073f7b8134625003cde0bbede2917.png][]

乍一看，这种N形状的移动可能看起来不起眼，但它确实有很有用的功能。它允许针“跳跃”从一条平行线到另一条线，这将有助于我们将针从一个区域移到另一个区域。

更重要的是，它在不需要太多区域的情况下完成。事实上，你可以根据需要将其要求的面积减小到很小。原因如下。

请记住，我们的针宽度为零。因此，针向前或向后移动的任何线都将具有零面积。这意味着将针沿着N形状向上、向下或沿对角线移动所需的区域将由零面积的部分组成。

这只留下了N形状的拐角处的旋转。

![c8f68224eecd978919f90494948231cc.png][]

这些移动确实需要区域。你可以看到每个角落有一个小扇形。但这里的狡猾之处在于：你可以通过拉长N来缩小这些区域。

![b17735b428a89c82330af67218a19e82.png][]

扇形区域的面积公式是 A = θ/360 πr2，其中 θ 是扇形角的度数。

无论N有多高，扇形的半径始终为1：这是针的长度。但随着N的增高，角度会缩小，从而减小扇形区域的面积。

因此，你可以通过拉伸N来使附加的区域面积尽可能小。

请记住，我们能够通过将三角形分成两部分并使它们重叠来减小三角形区域的面积。问题在于，这将90度角分成了两个独立的部分，阻止我们将针旋转90度。

现在，我们可以通过附加适当的N形状来解决这个问题，以确保针可以从一侧到另一侧。

在这个更新后的区域中，针仍然可以像以前一样旋转90度，只是现在分两个阶段进行。首先，针旋转45度并与左侧的垂直边对齐。

接下来，它沿着N的形状移动，以到达另一侧。一旦到达那里，它就可以自由地旋转另外的45度。

![8e46eeb780a515b7a7d1526bd4ff8253.png][]

这使得针可以旋转90度，并为保持旋转，只需添加区域的旋转副本。

![6b2dc3306f89d4079af8312291ab76ab.png][]

通过添加适当的N形状，针可以从一个三角半岛跳到下一个，一点一点地旋转，就像汽车执行三点转弯一样。

这些细节中还有更多的数学问题，但这两个想法——我们可以不断减小原始区域的面积，通过切割和移动确保我们可以使用任意小的N形状从一个部分到另一个部分

——帮助我们将针在一个不断缩小的区域中移动，最终可以变得很小。

![2508860c2ab19466ee5e95d4c5123932.png][]

建立这种区域的更标准的方法是从等边三角形开始，使用“Needle树”，这是一种巧妙的方法，可以切割三角形并将碎片拉长和滑动在一起。

结果非常令人惊叹。

最近，数学家在这个古老问题的新变种中取得了进展，这些问题设置在更高维度，并采用不同的大小概念。

我们可能永远不会看到一辆AI驱动的汽车在执行柿谷针对点转弯，但我们仍然可以欣赏它几乎不存在的美和简单。

练习1. 作为柿谷针对点集的最小等边三角形的面积是多少？

查看答案1：

高度为1的等边三角形有足够的空间，可以让位于一个顶点的针从一侧摆动到另一侧。一旦在一侧，它可以滑到另一个顶点，旋转，然后继续旅程，直到回到起始位置，指向相反的方向。

![25adecf92ae563d73c5a786ab429c51b.png][]

边长为s的等边三角形的面积是。您可以使用三角法或毕达哥拉斯定理来确定高度为1的等边三角形的边长。因此，面积为

![7feeb9765f780cc9daf40a92ab3e1b79.png][]

练习2. 您可以通过使用“Reuleaux三角形”来比练习1的等边三角形好一点，它是由三个重叠的圆形扇区组成的区域。

最小Reuleaux三角形的面积是多少？

查看答案2：取三个半径为1，角度为60度的圆形扇区，并排列它们，以便它们都与边长为1的等边三角形重叠。

这个区域允许长度为1的针完全旋转。

![d84b36410421ac9a08df14be113f9c7a.png][]

三个圆形扇区的面积之和计算了三角形重叠的面积三次，因此总面积是三个圆形扇区的面积之和减去两次三角形重叠：

![0cb919f2ebf4e75079529e29ef627fef.png][]

[5c057f32c9d4085e81dc40323a2db0e5.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/2171b6cbbfea4f8a896d770c3e812761.png
[44e2d02a805601f0a81b3c715e62e57a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/202e1c983de94f08859b806966f3053d.png
[f7deb6a4447d59a2a51d1d213544a4d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/e796fdc713f047478bd1a482c618ff46.png
[b1a26e654f51ab932135419da4a867e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/47923c0498da4e6f8fac496c8deb9864.png
[22974fc79ec2ed08d4fcd4c54c97ee66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/d2d95bbf83574d7f84847c071dee7e41.png
[34d16ddeabbea7a9e0d6456db288dea5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/92df18ef60b6411ea6741aafc648b21c.png
[f3bb672ff354ee9ebf22b4dd656a9ef4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/0f11bba3f184452db724c7f974b5486d.png
[193067a7a6016708ca4b5db446bc1e33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/4371c44f153c41119f3fc2f7b632fd47.png
[03ad926b23a6c74cd56fe2d0536f450b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/549f53bc087f4f2da3967ed829ffc3d0.png
[96642680d1bcadac937e95bc7dfba0d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/7c10282fc37842afae4b8854eba18c48.png
[b309e9db8055fe0c1a4f0101fcdd307d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/ce5205e572284dfeb83c1f04a608c582.png
[5620dac64257f8c45eeda0e5847a2bb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f6facb3689214c0ba38ed1d78458dc62.png
[44b073f7b8134625003cde0bbede2917.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/9da3da203f294de7bbe0f051d3f1ec26.png
[c8f68224eecd978919f90494948231cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/66740a468d2e4ea88a339f5d6eaecf27.png
[b17735b428a89c82330af67218a19e82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/47cca5af762545519e2cd8ca0f35cdd9.png
[8e46eeb780a515b7a7d1526bd4ff8253.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/9e73f4e55e364197b9cd7862d668608f.png
[6b2dc3306f89d4079af8312291ab76ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/7d646ffde2264ec094549c887e9c2c1a.png
[2508860c2ab19466ee5e95d4c5123932.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f837a74d77dc41d6bb2a072dbb6dc33f.png
[25adecf92ae563d73c5a786ab429c51b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/fbfb312b10754a18bbd45c3d23898ea2.png
[7feeb9765f780cc9daf40a92ab3e1b79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/2cf43f7316e741d1b295edf2f65cd574.png
[d84b36410421ac9a08df14be113f9c7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f8daa215fdd943859f5987b1b4264df1.png
[0cb919f2ebf4e75079529e29ef627fef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/1ea7aa114f0545bcb5d282c5c840a42c.png