Эвристический поиск

Материал из MachineLearning.

Версия от 09:29, 16 июля 2026; Arsenii Kolesnikov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM GPT-5.5 и проверена участником Arsenii Kolesnikov 11:53, 16 июля 2026 (MSD)

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

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

Задача поиска на графе

Пусть задан ориентированный граф состояний $G=(V,E)$ , начальная вершина $s$ , множество целевых вершин $T$ и стоимость ребра $c(u,v)>0$ . Требуется найти путь из $s$ в одну из вершин $T$ , часто минимальной стоимости.

Стоимость уже пройденного пути до вершины $n$ обозначается $g(n)$ . Эвристическая функция $h(n)$ оценивает оставшуюся стоимость от $n$ до цели. Общая оценка в A* задаётся формулой:

$f(n)=g(n)+h(n).$

Эвристическая функция

Эвристика — правило, использующее структуру задачи для ускорения поиска. Эвристика не обязана быть точной. Хорошая эвристика дешёвая в вычислении и достаточно информативная: она различает перспективные и бесперспективные направления.

Примеры:

манхэттенское расстояние в задачах на решётке;
число неверно расположенных плиток в пятнашках;
нижняя оценка длины маршрута в задаче коммивояжёра;
расстояние до цели в релаксированной задаче планирования.

Допустимость и монотонность

Эвристика называется допустимой, если она никогда не завышает истинную минимальную стоимость до цели:

$0\le h(n)\le h^*(n),$

где $h^*(n)$ — истинная оптимальная стоимость от $n$ до цели.

Эвристика называется монотонной, или согласованной, если для каждого ребра $(n,m)$ выполняется

$h(n)\le c(n,m)+h(m).$

Монотонность является аналогом неравенства треугольника и гарантирует, что значения $f(n)$ вдоль пути не убывают.

Алгоритм A*

A* хранит множество открытых вершин и на каждом шаге раскрывает вершину с минимальным значением $f(n)$ . При допустимой эвристике A* находит оптимальный путь, если все стоимости рёбер положительны и пространство поиска конечно или удовлетворяет стандартным условиям полноты^[1].

Схема алгоритма:

поместить начальную вершину в открытое множество;
выбрать вершину с минимальным $f(n)$ ;
если вершина целевая, вернуть путь;
иначе раскрыть её наследников;
обновить оценки $g$ , $h$ и родителей вершин;
повторять до нахождения цели или исчерпания поиска.

Главный недостаток A* — потребление памяти: алгоритм хранит большое число открытых и закрытых вершин.

Варианты

Жадный поиск по первому наилучшему

Жадный поиск выбирает вершину с минимальным $h(n)$ , игнорируя уже накопленную стоимость. Он может быть быстрым, но не гарантирует оптимальность и может уходить в тупики.

IDA*

IDA* сочетает идею A* с итеративным углублением по порогу $f$ . Он требует меньше памяти, но может повторно проходить одни и те же участки пространства состояний.

Beam search

Beam search хранит только ограниченное число лучших кандидатов на каждом уровне. Это делает метод полезным в задачах с огромным пространством вариантов, например в декодировании последовательностей, но лишает гарантий полноты и оптимальности.

Weighted A*

Взвешенный A* использует оценку

$f_w(n)=g(n)+w h(n),\quad w>1.$

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

Применение

Эвристический поиск применяется там, где полный перебор невозможен:

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

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

Ограничения

Качество метода зависит от эвристики.
Информативная эвристика может быть слишком дорогой.
В больших пространствах даже A* может исчерпать память.
Приближённые варианты часто теряют гарантии оптимальности.

См. также

Эвристика

Литература

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%AD%D0%B2%D1%80%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA»

Категория: Энциклопедия анализа данных