Открыть сервисСервис

Эвристика — метод решения задач

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

История

Понятие эвристики в математике связывают с работами немецкого математика Георга Поли, автора книги «Как решать задачи» (1945), где систематизированы приёмы математического исследования. В 1960-е годы изучение эвристических методов развивалось в рамках искусственного интеллекта: Герберт Саймон, Аллен Ньюэлл и Клиффорд Шоу создали программы, решающие задачи методом эвристического поиска. В СССР вклад в теорию эвристики внесли А. Н. Колмогоров, В. А. Успенский и А. Л. Берлинер, а также школа В. М. Глушкова в области кибернетики.

Классификация

Эвристические методы можно разделить на несколько групп:

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

Основные эвристические приёмы

Методы суждения

  • Эвристика близости — предположение, что более вероятны события, близкие по времени, месту или свойствам к уже известным.
  • Эвристика доступности — оценка вероятности события по лёгкости, с которой примеры приходят на ум.
  • Эвристика закрепления (якорения) — оценка величины, исходя из начального ориентира, даже если он произволен.
  • Эвристика репрезентативности — суждение о вероятности по сходству с типичным образцом.

Эти приёмы описаны в работах Даниэля Канемана и Амоса Тверски (1970-е годы) и используются в психологии суждений.

Методы поиска

В теории искусственного интеллекта различают алгоритмы, основанные на эвристической оценке:

  • Жадный алгоритм — на каждом шаге выбирается вариант с наилучшей эвристической оценкой.
  • Поиск с возвратом на шаг назад — при тупике происходит возврат к предыдущему узлу.
  • Алгоритм A\* — комбинирует стоимость пути от старта и эвристическую оценку до цели; при адекватной оценке гарантирует оптимальность.
  • Метод имитации отжига — имитирует процесс сплавления металлов, допуская «ухудшения» с вероятностью, убывающей по мере «остывания».

Применение

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

  • Искусственный интеллект — планирование, распознавание образов, принятие решений.
  • Компьютерные игры — шахматные и игровые движки используют эвристические функции оценки позиции.
  • Оптимизация — эвристические алгоритмы (генетические алгоритмы, муравьиный алгоритм) решают задачи комбинаторной оптимизации, например, задачу коммивояжёра.
  • Психология и экономика — модели ограниченной рациональности Герберта Саймона описывают человека как субъекта, принимающего решения эвристически, а не вычисляющего оптимум.
  • Программирование — эвристики используются в компиляторах, базах данных, системах поиска.

Ограничения

Эвристики не гарантируют оптимальности и могут приводить к систематическим ошибкам — когнитивным искажениям, описанным Канеманом и Тверски. Применение эвристики оправдано, когда стоимость полного решения задачи превышает ценность точного результата.

Источники

  • Поли Г. «Как решать задачи». — М.: Наука, 1976.
  • Ньюэлл А., Саймон Г. «Человек как система обработки информации».
  • Канеман Д., Тверски А. «О суждениях в условиях неопределённости».
  • Берлинер Г. «Искусство и методы эвристического программирования».
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru