Эвристика — метод решения задач¶
Эвристика — это метод (правило, стратегия, приём), используемый для решения задач, когда полный перебор вариантов невозможен или экономически нецелесообразен. В отличие от алгоритма, гарантирующего нахождение решения за конечное число шагов, эвристика даёт приближённый результат и не всегда приводит к оптимальному ответу. Термин происходит от греческого heuriskein — «находить, отыскивать».
¶История
Понятие эвристики в математике связывают с работами немецкого математика Георга Поли, автора книги «Как решать задачи» (1945), где систематизированы приёмы математического исследования. В 1960-е годы изучение эвристических методов развивалось в рамках искусственного интеллекта: Герберт Саймон, Аллен Ньюэлл и Клиффорд Шоу создали программы, решающие задачи методом эвристического поиска. В СССР вклад в теорию эвристики внесли А. Н. Колмогоров, В. А. Успенский и А. Л. Берлинер, а также школа В. М. Глушкова в области кибернетики.
¶Классификация
Эвристические методы можно разделить на несколько групп:
- Эвристики общего назначения — применимы к широкому классу задач: «разделяй и властвуй», «решай противоположную задачу», «рассматривай частные случаи», «используй аналогию».
- Эвристики предметной области — учитывают специфику конкретной задачи (например, в шахматах — «контролируй центр», «развивай фигуры»).
- Эвристики оценки — функции, приближённо оценивающие «стоимость» или «перспективность» состояния в процессе поиска.
¶Основные эвристические приёмы
¶Методы суждения
- Эвристика близости — предположение, что более вероятны события, близкие по времени, месту или свойствам к уже известным.
- Эвристика доступности — оценка вероятности события по лёгкости, с которой примеры приходят на ум.
- Эвристика закрепления (якорения) — оценка величины, исходя из начального ориентира, даже если он произволен.
- Эвристика репрезентативности — суждение о вероятности по сходству с типичным образцом.
Эти приёмы описаны в работах Даниэля Канемана и Амоса Тверски (1970-е годы) и используются в психологии суждений.
¶Методы поиска
В теории искусственного интеллекта различают алгоритмы, основанные на эвристической оценке:
- Жадный алгоритм — на каждом шаге выбирается вариант с наилучшей эвристической оценкой.
- Поиск с возвратом на шаг назад — при тупике происходит возврат к предыдущему узлу.
- Алгоритм A\* — комбинирует стоимость пути от старта и эвристическую оценку до цели; при адекватной оценке гарантирует оптимальность.
- Метод имитации отжига — имитирует процесс сплавления металлов, допуская «ухудшения» с вероятностью, убывающей по мере «остывания».
¶Применение
Эвристические методы применяются там, где задача сложна для полного решения:
- Искусственный интеллект — планирование, распознавание образов, принятие решений.
- Компьютерные игры — шахматные и игровые движки используют эвристические функции оценки позиции.
- Оптимизация — эвристические алгоритмы (генетические алгоритмы, муравьиный алгоритм) решают задачи комбинаторной оптимизации, например, задачу коммивояжёра.
- Психология и экономика — модели ограниченной рациональности Герберта Саймона описывают человека как субъекта, принимающего решения эвристически, а не вычисляющего оптимум.
- Программирование — эвристики используются в компиляторах, базах данных, системах поиска.
¶Ограничения
Эвристики не гарантируют оптимальности и могут приводить к систематическим ошибкам — когнитивным искажениям, описанным Канеманом и Тверски. Применение эвристики оправдано, когда стоимость полного решения задачи превышает ценность точного результата.
¶Источники
- Поли Г. «Как решать задачи». — М.: Наука, 1976.
- Ньюэлл А., Саймон Г. «Человек как система обработки информации».
- Канеман Д., Тверски А. «О суждениях в условиях неопределённости».
- Берлинер Г. «Искусство и методы эвристического программирования».
