Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{well|Статья написана с использованием LLM '''GPT-5.5''' и проверена участником [[Участник:Arsenii Kolesnikov|Arsenii Kolesnikov]] 11:53, 16 июля 2026 (MSD)}} '''Эвристический поиск''' — класс методов поиска, использующих дополнительную информацию о задаче для выбора наиболее перспективных состояний или вершин. В отличие от слепого поиска, который не различает направления до цели, эвристический поиск применяет функцию оценки, приближённо измеряющую стоимость или расстояние до решения. Эвристический поиск используется в планировании, маршрутизации, решении головоломок, синтезе программ, игровых агентах и комбинаторной оптимизации. Его эффективность зависит не только от алгоритма, но и от качества эвристики. == Задача поиска на графе == Пусть задан ориентированный граф состояний <tex>G=(V,E)</tex>, начальная вершина <tex>s</tex>, множество целевых вершин <tex>T</tex> и стоимость ребра <tex>c(u,v)>0</tex>. Требуется найти путь из <tex>s</tex> в одну из вершин <tex>T</tex>, часто минимальной стоимости. Стоимость уже пройденного пути до вершины <tex>n</tex> обозначается <tex>g(n)</tex>. Эвристическая функция <tex>h(n)</tex> оценивает оставшуюся стоимость от <tex>n</tex> до цели. Общая оценка в A* задаётся формулой: :: <tex>f(n)=g(n)+h(n).</tex> == Эвристическая функция == [[Эвристика]] — правило, использующее структуру задачи для ускорения поиска. Эвристика не обязана быть точной. Хорошая эвристика дешёвая в вычислении и достаточно информативная: она различает перспективные и бесперспективные направления. Примеры: * манхэттенское расстояние в задачах на решётке; * число неверно расположенных плиток в пятнашках; * нижняя оценка длины маршрута в задаче коммивояжёра; * расстояние до цели в релаксированной задаче планирования. == Допустимость и монотонность == Эвристика называется допустимой, если она никогда не завышает истинную минимальную стоимость до цели: :: <tex>0\le h(n)\le h^*(n),</tex> где <tex>h^*(n)</tex> — истинная оптимальная стоимость от <tex>n</tex> до цели. Эвристика называется монотонной, или согласованной, если для каждого ребра <tex>(n,m)</tex> выполняется :: <tex>h(n)\le c(n,m)+h(m).</tex> Монотонность является аналогом неравенства треугольника и гарантирует, что значения <tex>f(n)</tex> вдоль пути не убывают. == Алгоритм A* == A* хранит множество открытых вершин и на каждом шаге раскрывает вершину с минимальным значением <tex>f(n)</tex>. При допустимой эвристике A* находит оптимальный путь, если все стоимости рёбер положительны и пространство поиска конечно или удовлетворяет стандартным условиям полноты<ref>Hart P. E., Nilsson N. J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 1968.</ref>. Схема алгоритма: # поместить начальную вершину в открытое множество; # выбрать вершину с минимальным <tex>f(n)</tex>; # если вершина целевая, вернуть путь; # иначе раскрыть её наследников; # обновить оценки <tex>g</tex>, <tex>h</tex> и родителей вершин; # повторять до нахождения цели или исчерпания поиска. Главный недостаток A* — потребление памяти: алгоритм хранит большое число открытых и закрытых вершин. == Варианты == === Жадный поиск по первому наилучшему === Жадный поиск выбирает вершину с минимальным <tex>h(n)</tex>, игнорируя уже накопленную стоимость. Он может быть быстрым, но не гарантирует оптимальность и может уходить в тупики. === IDA* === IDA* сочетает идею A* с итеративным углублением по порогу <tex>f</tex>. Он требует меньше памяти, но может повторно проходить одни и те же участки пространства состояний. === Beam search === Beam search хранит только ограниченное число лучших кандидатов на каждом уровне. Это делает метод полезным в задачах с огромным пространством вариантов, например в декодировании последовательностей, но лишает гарантий полноты и оптимальности. === Weighted A* === Взвешенный A* использует оценку :: <tex>f_w(n)=g(n)+w h(n),\quad w>1.</tex> Увеличение веса ускоряет поиск за счёт склонности двигаться к цели, но может нарушать оптимальность. == Применение == Эвристический поиск применяется там, где полный перебор невозможен: * построение планов действий; * поиск маршрутов; * доказательство теорем; * оптимизация расписаний; * игровые агенты; * синтез программ и автоматическое исправление ошибок. В машинном обучении эвристический поиск появляется в выборе архитектур, дискретном выводе, декодировании, поиске гиперпараметров и постобработке структурных предсказаний. == Ограничения == * Качество метода зависит от эвристики. * Информативная эвристика может быть слишком дорогой. * В больших пространствах даже A* может исчерпать память. * Приближённые варианты часто теряют гарантии оптимальности. == См. также == * [[Эвристика]] == Литература == <references/> [[Категория:Энциклопедия анализа данных]]

• Шаблон:Mbox
• Шаблон:Well

Возврат к странице Эвристический поиск.