A * гарантирует поиск пути с наименьшей стоимостью в графе с неотрицательными затратами на ребро при условии, что вы используете соответствующую эвристику.Что делает эвристическую функцию подходящей?
Во-первых, она должна быть допустимой , т. Е. Для любого узла она должна давать либо заниженную, либо правильную оценку стоимости самого дешевого пути изэтот узел к любому из целевых узлов.Это означает, что эвристика никогда не должна переоценивать стоимость, чтобы добраться от узла до цели.
Обратите внимание, что если ваша эвристика вычисляет оценочную стоимость 0 для каждого узла, то A * просто поворачиваетсяв исчерпывающий поиск в ширину.Таким образом, h (n) = 0 - все еще допустимая эвристика, только худшая возможная.Таким образом, из всей допустимой эвристики, чем точнее оценивается стоимость цели, тем она лучше.
Во-вторых, вычисление должно быть дешевым.Это должно быть, конечно, O (1), и предпочтительно смотреть только на текущий узел.Рекурсивная оценка стоимости, которую вы предлагаете, сделает ваш поиск значительно медленнее, а не быстрее!
Таким образом, вопрос о применимости A * заключается в том, можете ли вы придумать достаточно хорошую эвристику.Из описания вашей проблемы не ясно, можете ли вы легко ее решить.
В зависимости от проблемной области, A * может быть очень полезным, если требования смягчены.Если эвристика становится недопустимой, вы теряете гарантию нахождения лучшего пути.В зависимости от степени переоценки расстояния, однако, решение все же может быть достаточно хорошим (для конкретного определения «достаточно хороший»).Преимущество в том, что иногда вы можете вычислить этот «достаточно хороший» путь гораздо быстрее.В некоторых случаях вероятностная оценка эвристики работает хорошо (у нее могут быть дополнительные ограничения, чтобы она оставалась в допустимом диапазоне).
Таким образом, в общем, вы в первую очередь выполняете поиск возможных проблем, а затем быстрееиметь A * для трактуемых задач с допустимой эвристикой.Если ваша проблема неразрешима для исчерпывающего поиска в ширину и не допускает эвристического подхода, тогда вы можете выбрать «достаточно хорошее» неоптимальное решение.Опять же, A * может все еще работать с недопустимой эвристикой здесь, или вы должны взглянуть на варианты поиска луча.Разница заключается в том, что при поиске луча существует ограничение на число способов исследования графа в настоящее время, в то время как A * ограничивает их косвенно, выбирая некоторое подмножество менее дорогих.Существуют практические случаи, не решаемые с помощью A * даже при неприемлемой допустимости, когда разница в стоимости между различными путями поиска незначительна.Поиск луча с жестким ограничением числа путей работает более эффективно в таких задачах.