Эвристика — методы эвристического поиска и мышления¶

Эвристика (от др.-греч. εὑρίσκω — «нахожу») — метод (правило, стратегия, приём) решения задач, основанный на эмпирических соображениях и не гарантирующий нахождение оптимального решения, но позволяющий получить приемлемый результат за разумное время. Эвристический подход применяется там, где точные (алгоритмические) методы либо отсутствуют, либо требуют неприемлемых вычислительных затрат. Термин «эвристика» используется в математике, искусственном интеллекте, психологии, философии и повседневном мышлении.

¶Эвристическое мышление

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

Психологи Даниэль Канеман и Амос Тверски в 1970-х годах описали ряд эвристик, используемых человеком при принятии решений в условиях неопределённости:

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

Эти эвристики приводят к систематическим когнитивным искажениям, что стало предметом отдельного направления исследований — поведенческой экономики.

¶Эвристики в математике

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

Классический пример — эвристика «решай задачу проще» (принцип Пойа): при трудной задаче сначала решают упрощённый вариант, исследуют граничные случаи, строят аналогии с уже решёнными задачами. Джордж Пойа в книге «Математика и эвристические рассуждения» (1945) систематизировал такие приёмы.

В теории чисел и комбинаторике эвристические аргументы (например, «принцип большого пальца» — pigeonhole principle) часто предшествуют строгим доказательствам.

¶Эвристический поиск в информатике

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

¶A*-алгоритм

Наиболее известный пример — A-алгоритм поиска кратчайшего пути в графе, предложенный Питером Хартом, Нильсом Нилссоном и Бертрамом Рафаэлем в 1968 году. Он использует оценочную функцию f(n) = g(n) + h(n), где g(n) — стоимость пути от старта до узла n, а h(n) — эвристическая оценка расстояния от n до цели. При корректно выбранной h(n) (не переоценивающей расстояние) A находит оптимальный путь.

¶Жадные алгоритмы

Жадный алгоритм на каждом шаге выбирает локально оптимальное действие, не задумываясь о глобальном результате. Примеры — алгоритм Дейкстры (для кратчайшего пути), кодирование Хаффмана, задача о рюкзаке (жадная стратегия по соотношению ценность/вес).

¶Метод ветвей и границ

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

¶Эвристики в искусственном интеллекте

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

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

В теории сложности задача о нахождении эвристик с доказанными гарантиями аппроксимации активно исследуется в рамках аппроксимируемых NP-трудных задач.

¶Эвристика в философии и науке

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

Пример — атомистическая модель Демокрита: гипотеза о неделимых частицах была эвристической, но плодотворной, позволив через века сформулировать современную атомную теорию.

¶Критика эвристического подхода

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

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

¶Применение

Эвристические методы применяются в широком спектре областей:

• Логистика и транспорт — эвристические алгоритмы решения задачи коммивояжёра (имитационный отжиг, муравьиный алгоритм, генетические алгоритмы).
• Промышленное проектирование — эвристики раскроя материалов, планирования производства.
• Медицина — эвристические правила первичной диагностики (красные флаги).
• Образование — обучение эвристическим стратегиям решения задач как способу развития мышления.

Исторически термин «эвристика» в научный оборот ввёл математик Георгий Полонский (Георгий Поло), а широкое распространение получил после работ Джорджа Пойа.

Источники:

• Пойа Дж. «Математика и эвристические рассуждения» (1945)
• Канеман Д., Тверски А. «Judgment under Uncertainty: Heuristics and Biases» (1974)
• Харт П., Нилссон Н., Рафаэл Б. «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» (1968)
• Рассел С., Норвиг П. «Искусственный интеллект: современный подход»
• Новиков Д.А. «Эвристические методы решения задач управления»