Расстояние городских кварталов
Расстояние городских кварталов — метрика, введённая Германом Минковским. Согласно этой метрике, расстояние между двумя точками равно сумме модулей разностей их координат.
У этой метрики много имён. Расстояние городских кварталов также известно как манхэттенское расстояние, метрика прямоугольного города, метрика L1 или норма <math>\ell_1</math> (см. пространство Lp), метрика городского квартала, метрика такси, метрика Манхэттена, прямоугольная метрика, метрика прямого угла; на <math>\mathbb{Z}^2</math> её называют метрикой гриды и 4-метрикой[1][2][3].
Название «манхэттенское расстояние» связано с уличной планировкой Манхэттена[4].
Содержание
Формальное определение
Расстояние городских кварталов <math>d_1</math> между двумя векторами <math>\mathbf{p}, \mathbf{q}</math> в n-мерном вещественном векторном пространстве с заданной системой координат — сумма длин проекций отрезка между точками на оси координат. Более формально,
- <math>d_1(\mathbf{p}, \mathbf{q}) = \|\mathbf{p} - \mathbf{q}\|_1 = \sum_{i=1}^n |p_i-q_i|,</math>
где
- <math>\mathbf{p}=(p_1,p_2,\dots,p_n)</math> и <math>\mathbf{q}=(q_1,q_2,\dots,q_n)</math>
— векторы.
Например, на плоскости расстояние городских кварталов между <math>(p_1,p_2)</math> и <math>(q_1,q_2)</math> равно <math>| p_1 - q_1 | + | p_2 - q_2 |.</math>
Свойства
Манхэттенское расстояние зависит от вращения системы координат, но не зависит от отражения относительно оси координат или переноса. В геометрии, основанной на манхэттенском расстоянии, выполняются все аксиомы Гильберта, кроме аксиомы о конгруэнтных треугольниках.
Шар в этой метрике имеет форму октаэдра, вершины которого лежат на осях координат.
Примеры
| a | b | c | d | e | f | g | h | ||
| 8 |            | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
Расстояния в шахматах
Расстояние между полями шахматной доски для визиря (или ладьи, если расстояние считать в клетках) равно манхэттенскому расстоянию; король и ферзь пользуются расстоянием Чебышёва, а слон — манхэттенским расстоянием на доске, повёрнутой на 45°.
Пятнашки
Сумма манхэттенских расстояний между костяшками и позициями, в которых они находятся в решённой головоломке «Пятнашки», используется в качестве эвристической функции для поиска оптимального решения[5].
Клеточные автоматы
Множество клеток на двумерном квадратном паркете, манхэттенское расстояние до которых от данной клетки не превышает r, назвается окрестностью фон Неймана диапазона (радиуса) r[6].
См. также
- Нормированное векторное пространство
- Метрика
- Расстояние Хэмминга
- Расстояние Чебышёва
- Французская железнодорожная метрика
- Игра в 15
- Случайное блуждание
- Матрица расстояний
Напишите отзыв о статье "Расстояние городских кварталов"
Примечания
- ↑ Елена Деза, Мишель Мари Деза. Глава 19. Расстояния на действительной и цифровой плоскостях. 19.1. Метрики на действительной плоскости // Энциклопедический словарь расстояний = Dictionary of Distances. — М: Наука, 2008. — С. 276. — ISBN 978-5-02-036043-3.
- ↑ [www.statsoft.ru/home/textbook/modules/stcluan.html#d Кластерный анализ: Меры расстояния]
- ↑ [www.nist.gov/dads/HTML/manhattanDistance.html Manhattan distance]
- ↑ [stn.spotfire.com/spotfire_client_help/hc/hc_city_block_distance.htm City Block Distance.] Spotfire Technology Network.
- ↑ [chernykh.net/content/view/294/494/ История компьютера: Эвристические функции]
- ↑ Weisstein, Eric W. [mathworld.wolfram.com/vonNeumannNeighborhood.html von Neumann Neighborhood] (англ.) на сайте Wolfram MathWorld.
Литература
- Eugene F. Krause. Taxicab Geometry. — Dover, 1987. — ISBN 0-486-25202-7.
Ссылки
- [planetmath.org/encyclopedia/CityBlockMetric.html city-block metric] on PlanetMath
- Weisstein, Eric W. [mathworld.wolfram.com/TaxicabMetric.html Taxicab Metric] (англ.) на сайте Wolfram MathWorld.
- [www.nist.gov/dads/HTML/manhattanDistance.html Manhattan distance]. Paul E. Black, [www.nist.gov/dads/ Dictionary of Algorithms and Data Structures], NIST
- [www.ams.org/featurecolumn/archive/taxi.html Taxi!] - AMS column about Taxicab geometry
- [www.taxicabgeometry.net TaxicabGeometry.net] - a website dedicated to taxicab geometry research and information
Отрывок, характеризующий Расстояние городских кварталов
– Уволь ты меня, матушка, ради бога, вели от меня ключи принять, – сказал он. – Служил двадцать три года, худого не делал; уволь, ради бога.Княжна Марья не понимала, чего он хотел от нее и от чего он просил уволить себя. Она отвечала ему, что она никогда не сомневалась в его преданности и что она все готова сделать для него и для мужиков.
Через час после этого Дуняша пришла к княжне с известием, что пришел Дрон и все мужики, по приказанию княжны, собрались у амбара, желая переговорить с госпожою.
– Да я никогда не звала их, – сказала княжна Марья, – я только сказала Дронушке, чтобы раздать им хлеба.
– Только ради бога, княжна матушка, прикажите их прогнать и не ходите к ним. Все обман один, – говорила Дуняша, – а Яков Алпатыч приедут, и поедем… и вы не извольте…
– Какой же обман? – удивленно спросила княжна
– Да уж я знаю, только послушайте меня, ради бога. Вот и няню хоть спросите. Говорят, не согласны уезжать по вашему приказанию.
– Ты что нибудь не то говоришь. Да я никогда не приказывала уезжать… – сказала княжна Марья. – Позови Дронушку.
Пришедший Дрон подтвердил слова Дуняши: мужики пришли по приказанию княжны.
– Да я никогда не звала их, – сказала княжна. – Ты, верно, не так передал им. Я только сказала, чтобы ты им отдал хлеб.
Дрон, не отвечая, вздохнул.
– Если прикажете, они уйдут, – сказал он.
– Нет, нет, я пойду к ним, – сказала княжна Марья
Несмотря на отговариванье Дуняши и няни, княжна Марья вышла на крыльцо. Дрон, Дуняша, няня и Михаил Иваныч шли за нею. «Они, вероятно, думают, что я предлагаю им хлеб с тем, чтобы они остались на своих местах, и сама уеду, бросив их на произвол французов, – думала княжна Марья. – Я им буду обещать месячину в подмосковной, квартиры; я уверена, что Andre еще больше бы сделав на моем месте», – думала она, подходя в сумерках к толпе, стоявшей на выгоне у амбара.
Толпа, скучиваясь, зашевелилась, и быстро снялись шляпы. Княжна Марья, опустив глаза и путаясь ногами в платье, близко подошла к ним. Столько разнообразных старых и молодых глаз было устремлено на нее и столько было разных лиц, что княжна Марья не видала ни одного лица и, чувствуя необходимость говорить вдруг со всеми, не знала, как быть. Но опять сознание того, что она – представительница отца и брата, придало ей силы, и она смело начала свою речь.
– Я очень рада, что вы пришли, – начала княжна Марья, не поднимая глаз и чувствуя, как быстро и сильно билось ее сердце. – Мне Дронушка сказал, что вас разорила война. Это наше общее горе, и я ничего не пожалею, чтобы помочь вам. Я сама еду, потому что уже опасно здесь и неприятель близко… потому что… Я вам отдаю все, мои друзья, и прошу вас взять все, весь хлеб наш, чтобы у вас не было нужды. А ежели вам сказали, что я отдаю вам хлеб с тем, чтобы вы остались здесь, то это неправда. Я, напротив, прошу вас уезжать со всем вашим имуществом в нашу подмосковную, и там я беру на себя и обещаю вам, что вы не будете нуждаться. Вам дадут и домы и хлеба. – Княжна остановилась. В толпе только слышались вздохи.
– Я не от себя делаю это, – продолжала княжна, – я это делаю именем покойного отца, который был вам хорошим барином, и за брата, и его сына.
Она опять остановилась. Никто не прерывал ее молчания.
– Горе наше общее, и будем делить всё пополам. Все, что мое, то ваше, – сказала она, оглядывая лица, стоявшие перед нею.
Все глаза смотрели на нее с одинаковым выражением, значения которого она не могла понять. Было ли это любопытство, преданность, благодарность, или испуг и недоверие, но выражение на всех лицах было одинаковое.
– Много довольны вашей милостью, только нам брать господский хлеб не приходится, – сказал голос сзади.
– Да отчего же? – сказала княжна.
Никто не ответил, и княжна Марья, оглядываясь по толпе, замечала, что теперь все глаза, с которыми она встречалась, тотчас же опускались.
– Отчего же вы не хотите? – спросила она опять.
Никто не отвечал.
Княжне Марье становилось тяжело от этого молчанья; она старалась уловить чей нибудь взгляд.
– Отчего вы не говорите? – обратилась княжна к старому старику, который, облокотившись на палку, стоял перед ней. – Скажи, ежели ты думаешь, что еще что нибудь нужно. Я все сделаю, – сказала она, уловив его взгляд. Но он, как бы рассердившись за это, опустил совсем голову и проговорил:
– Чего соглашаться то, не нужно нам хлеба.
– Что ж, нам все бросить то? Не согласны. Не согласны… Нет нашего согласия. Мы тебя жалеем, а нашего согласия нет. Поезжай сама, одна… – раздалось в толпе с разных сторон. И опять на всех лицах этой толпы показалось одно и то же выражение, и теперь это было уже наверное не выражение любопытства и благодарности, а выражение озлобленной решительности.
