* Эвристический, переоценка / недооценка? - PullRequest
Новая
       21

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

18 голосов
/ 18 июня 2009

Меня смущают условия переоценки / недооценки. Я прекрасно понимаю, как работает алгоритм *, но я не уверен в том, что эвристика переоценивает или недооценивает.

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

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

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

Ответы [ 4 ]

30 голосов
/ 18 июня 2009

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

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

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

11 голосов
/ 18 июня 2009

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

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

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

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

3 голосов
/ 06 мая 2018

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

@ хаос ответ вводит в заблуждение ИМО (может быть выделен)

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

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

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

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

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

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

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

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

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

Paths

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

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

Zero

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

3. Идеал (зеленый)

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

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

  • Кратчайший путь без препятствий (если вы не двигаетесь по диагонали; другими словами: стоимость «движения по диагонали» оценивается в 2)
  • переоценивает
  • Узлы расширены: 562
  • Длина пути: 92,840
  • https://i.stack.imgur.com/gD9t4.png

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

3 голосов
/ 18 июня 2009

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

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

...