Вы переоцениваете, когда оценка эвристики выше фактической конечной стоимости пути. Вы недооцениваете, когда оно ниже (вам не нужно недооценивать, нужно просто не переоценивать; правильные оценки — это нормально). Если все реберные затраты вашего графа равны 1, то приведенные вами примеры будут давать завышенные и заниженные оценки, хотя расстояние в простых координатах также прекрасно работает в декартовом пространстве.

Переоценка точно не делает алгоритм «неправильным»; это означает, что у вас больше нет допустимой эвристики, которая является условием для гарантированного оптимального поведения A*. С недопустимой эвристикой алгоритм может выполнить массу лишней работы, исследуя пути, которые он должен игнорировать, и, возможно, находя неоптимальные пути из-за их изучения. Произойдет ли это на самом деле, зависит от вашего проблемного пространства. Это происходит из-за того, что стоимость пути «не совпадает» с оценочной стоимостью, что, по сути, дает алгоритму неверные представления о том, какие пути лучше других.

Я не уверен, найдете ли вы его, но вы можете посмотреть статью A* в Википедии. . Я упоминаю (и ссылаюсь) в основном потому, что это почти невозможно найти в Google.

Из статьи A* в Википедии соответствующая часть описания алгоритма:

Алгоритм продолжается до тех пор, пока целевой узел не будет иметь меньшее значение f, чем любой узел в очереди (или пока очередь не станет пустой).

Ключевая идея состоит в том, что при недооценке А* прекратит исследовать потенциальный путь к цели только тогда, когда узнает, что общая стоимость пути превысит стоимость известного пути к цели. Поскольку оценка стоимости пути всегда меньше или равна реальной стоимости пути, A* может отбросить путь, как только предполагаемая стоимость превысит общую стоимость известного пути.

При переоценке A* не знает, когда можно прекратить изучение потенциального пути, поскольку могут быть пути с более низкими фактическими затратами, но более высокими оценочными затратами, чем наилучший известный в настоящее время путь к цели.

Интуитивный ответ

Чтобы A* работал правильно (всегда находя «лучшее» решение, а не просто любое), ваша функция оценки должна быть оптимистичной.

Оптимизм здесь означает, что ваши ожидания всегда лучше реальности.

Оптимист попробует многое, что в конце концов может разочаровать, но он найдет все хорошие возможности.

Пессимист ожидает плохих результатов и поэтому не будет пробовать многое. Из-за этого они могут упустить некоторые золотые возможности.

Таким образом, для A* быть оптимистом означает всегда недооценивать затраты (т. е. «вероятно, это не так далеко»). Когда вы делаете это, как только вы нашли путь, вы все еще можете быть взволнованы несколькими неизведанными вариантами, что может быть даже лучше. Это означает, что вы не остановитесь на первом решении и по-прежнему будете пробовать другие. Большинство, вероятно, разочарует (не станет лучше), но это гарантирует, что вы всегда найдете лучшее решение. Конечно, опробование большего количества вариантов требует больше работы (времени).

Пессимист A* всегда будет завышать стоимость (например, "этот вариант, вероятно, довольно плохой"). Как только он найдет решение и узнает истинную цену пути, любой другой путь будет казаться хуже (потому что оценки всегда хуже реальности), и он никогда не будет пробовать какую-либо альтернативу, как только цель будет найдена.

Самая эффективная А* — это та, которая никогда не занижает оценку, а оценивает либо идеально, либо слегка переоптимистично. Тогда вы не будете наивны и перепробуете слишком много плохих вариантов.

Хороший урок для всех. Всегда будь немного оптимистом!

Краткий ответ

Ответ @chaos немного вводит в заблуждение (можно выделить)

Переоценка точно не делает алгоритм неверным; это означает, что у вас больше нет допустимой эвристики, которая является условием для того, чтобы A* гарантировало оптимальное поведение. С недопустимой эвристикой алгоритм может выполнить массу лишней работы.

как намекает @AlbertoPL

Вы можете найти ответ быстрее, переоценивая, но вы можете не найти кратчайшего пути.

В конце концов (помимо математического оптимума) оптимальное решение сильно зависит от того, учитываете ли вы вычислительные ресурсы, время выполнения, специальные типы карт/пространств состояний и т. д.

Длинный ответ

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

Чтобы дать вам лучшее впечатление, я делюсь некоторыми примерными результатами, которые я быстро создал с помощью Python. Результаты основаны на одном и том же алгоритме A*, отличается только эвристика. Каждый узел (ячейка сетки) имеет ребра со всеми восемью соседями, кроме стен. Стоимость диагональных ребер sqrt(2)=1,41

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

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

<сильный>1. Ноль (синий)

• Соответствует алгоритму Дейкстры
• Расширено узлов: 2685
• Длина пути: 89,669

<сильный>2. По прямой линии (желтый)

• Расширено узлов: 658
• Длина пути: 89,669

<сильный>3. Идеально (зеленый)

• Кратчайший путь без препятствий (если следовать восьми направлениям)
• Максимально возможная оценка без завышения (следовательно, идеальная)
• Расширено узлов: 854
• Длина пути: 89,669

<сильный>4. Манхэттен (красный)

• Кратчайший путь без препятствий (если вы не двигаетесь по диагонали; другими словами: стоимость движения по диагонали оценивается как 2)
• Завышает
• Расширено узлов: 562
• Длина пути: 92.840

<сильный>5. Как ворона умножает на десять (голубой)

• Завышает
• Расширено узлов: 188
• Длина пути: 99,811

Насколько я знаю, вы обычно хотите недооценивать, чтобы вы все равно могли найти кратчайший путь. Вы можете найти ответ быстрее, переоценивая, но вы можете не найти кратчайшего пути. Следовательно, почему переоценка «неверна», тогда как недооценка все же может обеспечить наилучшее решение.

Мне жаль, что я не могу дать никакого представления о линиях обзора с высоты птичьего полета...

Рассмотрим эвристику как f(x)=g(x)+h(x), где g(x) — это реальная стоимость от start-node до current-node, а h(x) прогнозируемая стоимость от current-node до goal. Предположим, что оптимальная стоимость равна R, тогда:

1. h(x) имеет значение на ранней стадии поиска. Даны три узла A,B,C

   (*)                               => current pos: A
    A -------> B - 。。。 -> C
    |_______________________|        => the prediction range of h(x)
   

   Как только вы наступаете на точку B, стоимость пути от A до B становится правдой, прогноз h(x) больше ее не включает:

              (*)                    => current pos: B
    A -------> B - 。。。 -> C
               |____________|        => the prediction range of h(x)
   

2. Когда мы говорим недооценка, это означает, что ваш h(x) вызовет f(x) < R для всех x на пути к goal.

3. Переоценка действительно делает алгоритм неправильным:

   Предположим, что R равно 19. И учитывая, что две стоимости 20, 21 являются стоимостью путей, которые уже достигают цели:

   Front                  Rear
    -------------------------        => This is a priority queue PQ.
   | 20 | 20 | 30 | ... | 99 |
     ^--------                       => This is the "fake" optimal.
   

   Но скажем, f(y)=g(y)+h(y), а y действительно находится на правильном пути для достижения оптимальной стоимости R, но поскольку h(y) завышена, поэтому f(y) в настоящее время 30 находится в PQ, поэтому, прежде чем мы сможем обновить 30 до 19, алгоритм уже вытолкнет 20 из PQ и ошибочно предположит, что это оптимальное решение.