* Эвристика, переоценка/недооценка?

Question

Меня смущают термины "завышение / недооценка".Я прекрасно понимаю, как работает алгоритм A *, но я не уверен в эффектах использования эвристики, которые переоценивают или недооценивают.

Является ли переоценкой, когда вы берете квадрат прямой линии обзора с высоты птичьего полета?И почему это сделало бы алгоритм неверным?Для всех узлов используется одна и та же эвристика.

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

Я не могу найти статью, в которой это объяснялось бы красиво и понятно, поэтому я надеюсь, что у кого-нибудь здесь есть хорошее описание.

Answer 1

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

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

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

Answer 2

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

  

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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

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

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

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

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

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

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

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

2.Как летит ворона (желтый)

• Расширенные узлы:658
• Длина пути:89.669
• https://i.stack.imgur.com/75eFV.png

3.Идеальный вариант (зеленый)

• Кратчайший путь без препятствий (если вы будете следовать восьми направлениям)
• Максимально возможная оценка без завышения (отсюда "идеальный")
• Расширенные узлы:854
• Длина пути:89.669
• https://i.stack.imgur.com/VqMtF.png

4.Манхэттен (красный)

• Кратчайший путь без препятствий (если вы не двигаетесь по диагонали;другими словами:стоимость "перемещения по диагонали" оценивается как 2)
• Переоценивает
• Расширенные узлы:562
• Длина пути:92.840
• https://i.stack.imgur.com/gD9t4.png

5.Как ворона пролетает раз десять (голубой)

• Переоценивает
• Расширенные узлы:188
• Длина пути:99.811
• https://i.stack.imgur.com/SZuFH.png