伤蓝 发表于 2020-9-18 00:00:23

曼哈顿距离算法是什么？


从美国纽约帝国大厦到纽约联合国总部有多远？那要看情况了。你有翅膀吗？如果没有，你就不得不坐出租车，然后遵循街道的网格模式前进。你将向东走大约8个街区，向北走9个街区，总共17个街区，才能到达目的地。这种只在南北(或垂直)和东西(或水平)方向计算距离的算法，就是由十九世纪赫尔曼·闵可夫斯基所创的计程车几何，也叫曼哈顿距离算法，是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。那么怎么使用曼哈顿距离算法计算距离呢？首先，让我们从我们所知道的开始。我们知道在欧几里德几何中，我们使用的是一个非常熟悉的距离公式来寻找两点之间的距离。这个公式是：https://www.tuiliz.com/data/attachment/album/201906/27/224732gw62ggbm9g6b9wgz.jpg现在，在出租车几何中，我们不能利用这个公式，因为在出租车几何中，你不能穿过街区——你必须计算街区数才能找到距离。看看这个例子…下面是一个城市街道网格图。所有的街道都是平行或垂直的，所有的城市街区都是大小相等的。
https://www.tuiliz.com/data/attachment/album/201906/27/224729pnosh5s5hgzt555n.gif
约翰在A点，鲍勃在b点。距离是通过计算从A点到b点的最小城市街区数来测量的。约翰需要走多少个街区去找鲍勃？这是唯一的路线吗？约翰能走多条路线去找鲍勃？答案是，约翰必须经过6个街区，他可以通过多条线路去找鲍勃，但是不管走哪条路，最快的路都必须经过7个街区。如下图所示：
https://www.tuiliz.com/data/attachment/album/201906/27/224729iq99ptvnkztn5zvn.gif
从上图我们可以看到，约翰有多种路线可以选择，其中最短的距离是经过6个街区，当然如果他喜欢，他可以选择走更长的路，经过7个街区。如果假设，约翰可以穿过街区，我们假设那里有开放的公园，或者他会飞。那么最短距离是多少？用什么公式可以帮助我们计算出这个距离？
https://www.tuiliz.com/data/attachment/album/201906/27/224730vso4ya5odsl5sydd.gifhttps://www.tuiliz.com/data/attachment/album/201906/27/224731a7wn0af0wf0pzfbj.gif
利用毕达哥拉斯定理，计算出最短的距离是五个街区（红线表示）。从上面两个例子我们可以看到，在出租车几何中，除非你能穿越大楼，才能走直线最短距离，否则必须遵循城市街道的网格模式前进。言归正传。如果我们让两点a(x1,y1)与b(x2,y2)成为笛卡平面上的点，我们如何找到曼哈顿距离的公式？你可以试着在笔记本上画一画，最终，你会发现在出租车几何中要计算二维平面两点之间距离的最佳公式是:https://www.tuiliz.com/data/attachment/album/201906/27/224732r7zic6f0lzzfvui7.png要注意的是，曼哈顿距离依赖座标系统的转度，而非系统在座标轴上的平移或映射。那么，欧氏距离和曼哈顿距离是一样的吗？是的，没错，只要当计算的点位于同一条垂直线或水平线上时，我们计算出的距离结果是相同的，不管我们使用什么公式。那么，曼哈顿距离可以用来计算圆形吗？让我们看看。
https://www.tuiliz.com/data/attachment/album/201906/27/224936helrd9z9ylpdydrl.gif
上图是一个半径为2的圆，它固定在该平面上。现在，出租车几何形状是怎么样的？这个圆仍然半径不变，但是它可以呈现出不同的形状。
https://www.tuiliz.com/data/attachment/album/201906/27/224731yeb8x5ptrabplxk5.gif
这个圆，现在看起来像一个正方形！其他形状呢？他们会是什么样子？双曲线怎么样？假设约翰和鲍勃想在周末见面，但是约翰必须比鲍勃少走3个街区(假设他腿受伤了)。那么，他们可能相遇的所有地点在哪里？
https://www.tuiliz.com/data/attachment/album/201906/27/224937gx2xqzxgb2clls2x.gif

上图红线上的所有点（街区）都符合要求，约翰只需要经过2个街区，鲍勃需要经过5个街区，就可以和约翰相遇。

宮野奈奈子 发表于 2020-9-18 18:03:57

蓝大把我之前想码的帖码出来了，还要完整一点……
我可能还是太懒了一点{:4_341:}。。。

QQ可乐 发表于 2020-9-18 22:31:41

没懂

萌新报道 发表于 2020-10-3 11:17:24

好难，看不懂{:4_136:}

Qssssssss 发表于 2020-10-7 14:30:39

懂了懂了

忘川先生 发表于 2021-4-26 18:49:01

今天刚看完唐二

犭 发表于 2021-5-12 23:52:13

看不懂。。。唐探2里有。

完美犯罪 发表于 2021-5-13 08:48:19

这是数学函数中两点中，距离公式。

发表于 2021-5-22 12:30:10

看了这个就看懂了唐2……？

太宰治 发表于 2021-5-22 13:45:05

看了一遍好像懂了，好像……中学生自卑orz我再看一遍呜呜呜
页: [1] 2
查看完整版本: 曼哈顿距离算法是什么？