Основные понятия.

Эвристика - это функция или критерий, который позволяет оценить «перспективность» текущего частичного решения, не выполняя полный перебор до конца. Например, в контексте поиска пути эвристика - это оценка оставшегося расстояния до цели.

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

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

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

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

Суть эвристического алгоритма А*.