Является ли манхэттенское расстояние монотонным, когда используется как эвристическая функция?

25

У меня есть квадратная карта. Допускается только горизонтальное и вертикальное движение (без диагоналей). Стоимость движения всегда 1.

Я реализую алгоритм A * на этой карте, используя манхэттенское расстояние в качестве эвристики расстояния. Согласна ли эта эвристика? Можно ли избежать проверки g(node)на узлы, которые находятся в наборе ЗАКРЫТО?

Изменить: под последовательным я имею в виду монотонность.

tiles path-finding geometry Эмилиано
источник
1
Если ваши затраты на движение одинаковы для каждой плитки, вы можете заменить A * Search Point Search
Ник Каплингер
Эй, это мило!
Эмилиано

Ответы:

10

На самом деле ответить на ваш вопрос: Manhatten расстояние соответствует , когда вы вынуждены двигаться по вертикали / horizonally вдоль невзвешенном сетки (это можно легко показать , по определению на википедии) . Так что да, в вашем случае вы можете избежать перепроверки узлов в закрытом наборе.

Однако после того, как вы разрешите перемещение по диагонали или под любым углом, ручное расстояние становится недопустимым, поскольку оно переоценивает диагональные затраты, что обязательно означает, что оно не согласовано.

BlueRaja - Дэнни Пфлугхофт
источник
Да, это именно тот ответ, который я искал. Было бы неплохо узнать, что произойдет, если эвристическая функция будет h(x) = min(manhattan(p1), manhattan(p2))(т.е. либо p1, либо p2 - хорошая конечная точка, и я хочу достичь ближайшей). Это h(x)все еще монотонный?
Эмилиано
1
@happy_emi: Да, если h(x, p1)и h(x, p2)согласованы, то min(h(x,p1), h(x,p2))также будут согласованы. Это легко показать из определения в википедии (нам нужно показать, что min(h(x, p1), h(x, p2)) <= distance(x,y) + min(h(y, p1), h(y, p2))для всех узлов xи yс ребром между ними. Теперь предположим, что h(x, p1)это минимум; можете ли вы показать, что это определенно <=правая сторона, используя тот факт, что обе эвристики согласуются?)
BlueRaja - Дэнни Пфлюгофт
31

Да, манхэттенское расстояние между двумя точками всегда одинаково, как и обычное расстояние между ними. Вы можете думать, что расстояние до Манхэттена является компонентами X и Y линии, проходящей между двумя точками.

Это изображение ( из Википедии ) хорошо иллюстрирует это:

Манхэттенские расстояния

Зеленая линия фактическое расстояние.

В синих , красных и желтых линиях все представляют собой один и то же Manhattan расстояние (12 единиц). Независимо от того, какую комбинацию движений вверх и вправо вы рисуете из нижней левой точки в нижнюю правую, вы получите одинаковое общее расстояние Манхэттена.

MichaelHouse
источник
2
Отличный ответ: коротко, мило, по существу и с красивой картинкой.
Том Блю Пиддок
1
Этот ответ близок, но неверен. Это изображение не показывает, что манхэттенское расстояние является согласованным (на самом деле, если вы считаете, что зеленая линия является расстоянием, оно не согласовано!) , А также причина того, что ему не нужно перепроверять узлы, потому что «манхэттенское расстояние между две точки всегда одинаковы " не имеет места (утверждение также верно h(x) = 1000, что, очевидно, не соответствует) . Он может избежать перепроверки узлов, но только потому, что расстояние Манхэттена является постоянным, что этот ответ не показывает.
BlueRaja - Дэнни Пфлюгофт
2
Я полагаю, что согласно определению, которое вы связали, манхэттенское расстояние соответствует. Расстояние зеленой линии будет использовать другую эвристику. Красные, синие и желтые линии показывают, что расстояние между двумя узлами остается одинаковым (при использовании одной эвристики). При приближении уменьшается эвристика, а при удалении увеличивается эвристика. Это соответствует монотонному требованию ОП. Поскольку граф построен, с узлом на каждом «пересечении», манхэттенское расстояние является постоянным. Если бы это был другой сценарий (например, разрешить перемещение по диагонали), эвристика была бы плохой.
MichaelHouse
2
Я уже говорил, что Манхэттенское расстояние является последовательным, но не по тем причинам, которые вы упомянули. Ваш ответ не показывает последовательность, равно как и ваш аргумент в комментариях. «Согласованная / монотонная эвристика» имеет точное определение (приведенное в моей ссылке выше) , которое не совпадает с монотонной функцией, для которой вы, кажется, путаете ее. Утверждение «приближение уменьшает эвристику, а перемещение дальше увеличивает эвристику» недостаточно, чтобы показать, что она последовательна, например. 2*manhattenудовлетворяет это, но не соответствует.
BlueRaja - Дэнни Пфлугхофт
3
Я не знаю, почему вы говорите, что это неправильно , вы, кажется, настаиваете, что этот ответ неполон . Доказательство в вашем ответе выглядит столь же слабым: «расстояние между людьми не меняется ...», затем вы повторяете первоначальные спецификации вопроса, следуя тому, как это было бы неприемлемо, если бы сценарий был другим , Я не чувствовал, что ответ требует полного математического доказательства. Если вы считаете, что этот вопрос требует этого, пожалуйста, включите его в свой ответ, и я проголосую за него. Спасибо за конструктивную критику.
MichaelHouse
6

В продолжение ответа Byte56 я хотел бы указать, что в вашем конкретном наборе данных использование Манхэттенского расстояния в качестве эвристической функции фактически всегда будет идеальной эвристикой в том смысле, что она всегда будет возвращать фактическую стоимость пути (при условии, что есть ничто не "блокирует" пути).

Следует также отметить, что все узлы в правильном направлении (по горизонтали или по вертикали) будут давать одинаковое ожидаемое расстояние (поскольку существует множество одинаково коротких путей к цели). Вы должны знать, что ваша очередь приоритетов (открытый набор) должна, в случае связанных приоритетов, сначала удалить из очереди последний добавленный узел (LIFO - Last In First Out). При этом вы будете проверять только те узлы, которые окажутся на оптимальном пути . Если вы исследуете одинаково подходящие узлы в порядке FIFO («первым пришел - первым обслужен»), вы будете эффективно проверять все узлы, являющиеся частью лучшего пути. Эта проблема возникает из-за того, что есть несколько одинаково хороших путей к целевому узлу.

Торкил Холм-Якобсен
источник
«(при условии, что ничто не блокирует путь)» - это довольно большое предположение. Если ничто не блокирует путь, нет нужды начинать поиск алгоритма!
BlueRaja - Дэнни Пфлугхофт
@ BlueRaja-DannyPflughoeft: Это правда, это была просто мысль, возникающая при взгляде на изображение Byte56. Все остальное правда, тем не менее.
Торкил Холм-Якобсен
4

Я не уверен, что вы подразумеваете под "всегда" последовательным. Является ли расстояние Манхэттена на фиксированной сетке независимым от пройденного пути? Да, как сказал ответ Byte56.

Однако, например, манхэттенское расстояние не является инвариантным относительно поворотов. Например, манхэттенское расстояние ( L1-норма ) между началом координат и точкой (10,10)есть |10-0| + |10-0| = 20. Однако, если вы повернете свои координаты на 45 градусов (то есть теперь ваша фиксированная точка лежит вдоль одного из направлений сетки), вы обнаружите, что та же самая точка находится сейчас (10sqrt(2),0), как и расстояние от Манхэттена до начала координат 10sqrt(2)~14.14.

доктор джимбоб
источник
+1 за указание на это; Ото, Манхэттен расстояние является инвариантным относительно 90-градусных поворотов, которые на самом деле только те , которые могут быть сделаны «последовательно» на дискретной сетке.
Стивен Стадницки,
1
Хороший улов, хотя он упомянул, что разрешено только горизонтальное и вертикальное движение.
Торкил Холм-Якобсен
1
Оригинальный вопрос был о последовательном, как в монотонном.
Эмилиано