From 060e1b14244d5c9719ac38dec78a4f8234ed8e43 Mon Sep 17 00:00:00 2001 From: partychicken <44670668+partychicken@users.noreply.github.com> Date: Wed, 20 Mar 2019 08:43:40 +0800 Subject: [PATCH] Update distance.md fix format --- docs/misc/distance.md | 33 ++++++++++++++++++--------------- 1 file changed, 18 insertions(+), 15 deletions(-) diff --git a/docs/misc/distance.md b/docs/misc/distance.md index 5fa2d795..cb26bd3e 100644 --- a/docs/misc/distance.md +++ b/docs/misc/distance.md @@ -244,36 +244,39 @@ $$ $A,B$ 两点的曼哈顿距离为: -$d(A,B)=|x_1 - x_2| + |y_1 - y_2|$ - -$=|x_1 - x_2| + |y_1 - y_2|$ - -$= max\begin{Bmatrix} x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1,x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1\end{Bmatrix}$ - -( 把绝对值拆开,能够得到四个值,这四个值中的最大值是两个非负数之和,即曼哈顿距离 ) +$$ +\begin{align} +d(A,B)&=|x_1 - x_2| + |y_1 - y_2|\\ +&=\max\begin{Bmatrix} x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1,x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1\end{Bmatrix}\\ +&\text{( 把绝对值拆开,能够得到四个值,这四个值中的最大值是两个非负数之和,即曼哈顿距离 )}\\ -$= max(|(x_1 + y_1) - (x_2 + y_2)|, |(x_1 - y_2) - (x_2 - y_2)|)$ +&= \max(|(x_1 + y_1) - (x_2 + y_2)|, |(x_1 - y_2) - (x_2 - y_2)|) +\end{align} +$$ -我们很容易发现,这就是 $(x_1 + y_1,x_1 - y_1), (x_2 + y_2,x_2 - y_2)$ 两点之间的切比雪夫距离。 +我们很容易发现,这就是 $(x_1 + y_1,x_1 - y_1), (x_2 + y_2,x_2 - y_2)​$ 两点之间的切比雪夫距离。 所以将每一个点 $(x,y)$ 转化为 $(x + y, x - y)$ ,新坐标系下的切比雪夫距离即为原坐标系下的曼哈顿距离。 同理, $A,B$ 两点的切比雪夫距离为: -$d(A,B)=max\begin{Bmatrix} |x_1 - x_2|,|y_1 - y_2|\end{Bmatrix}$ - -$=max\begin{Bmatrix} |\frac{x_1 + y_1}{2}-\frac{x_2 + y_2}{2}|+|\frac{x_1 - y_1}{2}-\frac{x_2 - y_2}{2}|\end{Bmatrix}$ +$$ +\begin{align} +d(A,B)&=\max\begin{Bmatrix} |x_1 - x_2|,|y_1 - y_2|\end{Bmatrix}\\ +&=\max\begin{Bmatrix} \left|\dfrac{x_1 + y_1}{2}-\dfrac{x_2 + y_2}{2}\right|+\left|\dfrac{x_1 - y_1}{2}-\dfrac{x_2 - y_2}{2}\right|\end{Bmatrix} +\end{align} +$$ -而这就是 $(\frac{x_1 + y_1}{2},\frac{x_1 - y_1}{2}), (\frac{x_2 + y_2}{2},\frac{x_2 - y_2}{2})$ 两点之间的 曼哈顿距离。 +而这就是 $(\dfrac{x_1 + y_1}{2},\dfrac{x_1 - y_1}{2}), (\dfrac{x_2 + y_2}{2},\dfrac{x_2 - y_2}{2})$ 两点之间的 曼哈顿距离。 -所以将每一个点 $(x,y)$ 转化为 $(\frac{x + y}{2},\frac{x - y}{2})$ ,新坐标系下的 曼哈顿距离 即为原坐标系下的 切比雪夫距离。 +所以将每一个点 $(x,y)$ 转化为 $(\dfrac{x + y}{2},\dfrac{x - y}{2})$ ,新坐标系下的 曼哈顿距离 即为原坐标系下的 切比雪夫距离。 ### 结论 - 曼哈顿坐标系是通过切比雪夫坐标系旋转 $45^\circ$ 后,再缩小到原来的一半得到的。 - 将一个点 $(x,y)$ 的坐标变为 $(x + y, x - y)$ 后, - 原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离 -- 将一个点 $(x,y)$ 的坐标变为 $(\frac{x + y}{2},\frac{x - y}{2})$ 后, +- 将一个点 $(x,y)$ 的坐标变为 $(\dfrac{x + y}{2},\dfrac{x - y}{2})$ 后, 原坐标系中的切比雪夫距离等于新坐标系中的 哈顿距离 -- 2.11.0