Эвристические алгоритмы

Эвристический алгоритм – это алгоритм, целенаправленно использующий приближённые правила выбора действий для сокращения пространства поиска и времени вычислений. Он не гарантирует оптимума во всех случаях, но стремится быстро находить «достаточно хорошие» решения для сложных задач (часто NP-трудных). Для подготовки к ЕГЭ по информатике владение эвристиками полезно по трём причинам:

1. формализует мышление о поиске и оптимизации (графы состояний, функции стоимости, оценка сложности);
2. тренирует аккуратную работу с критериями и ограничениями (инварианты, допустимость решения);
3. развивает навык конструирования и проверки алгоритмов (корректность, оценка качества, граничные случаи).

Формальная модель задачи поиска/оптимизации

Пусть задана задача минимизации

Найти x* ∈ S: f(x*) = min{ f(x) : x ∈ S и G(x) = True }

где S – пространство решений, G(x) – предикат допустимости, f(x) – целевая функция (стоимость).

Представление через граф поиска.
Состояние: вершина v ∈ V, переход: ребро (v,u) со стоимостью c(v,u) ≥ 0. Пути соответствуют частичным решениям, целевые вершины удовлетворяют Goal(v) = True. Стоимость пути g(v) – сумма рёбер на пути из старта s к v.

Эвристическая оценка.
Функция h(v) ≥ 0 аппроксимирует «оставшуюся» стоимость до цели. Полезные свойства:

• Допустимость (admissibility): 0 ≤ h(v) ≤ h*(v), где h*(v) – истинная минимальная оставшаяся стоимость.
• Согласованность (монотонность): h(v) ≤ c(v,u) + h(u) для любого ребра (v,u).

В задачах без явного графа часто задают окрестность N(x) и переходы «локальных» улучшений (локальный поиск).

Критерии качества и корректности эвристик

1. Точностные критерии
   

   • Относительный разрыв (optimality gap) при минимизации:

   gap(x) = (f(x) - LB) / max(1, |LB|)

   где LB – нижняя оценка (например, из релаксации).

   • Аппроксимационное отношение (approximation ratio):

   ρ(x) = f(x) / f(x*)   (для min-задач, ρ ≥ 1)

   Чем ближе ρ к 1, тем лучше решение.

2. Вычислительные критерии
   

   • Асимптотика по числу состояний/элементов: O(T(n)).

   • Память: объём фронта поиска/популяции/таблиц.

   • Стабильность: дисперсия качества при разных случайных посевах.

   • Детерминизм/повторяемость: фиксируйте генератор случайных чисел.

3. Правила корректности (инварианты)
   

   • I1 (допустимость): каждый выдаваемый ответ удовлетворяет ограничениям G(x)=True.

   • I2 (монотонность улучшений): операция «улучшить» не ухудшает метрику: f(next(x)) ≤ f(x) (или допускает случайные подъёмы по строго описанным правилам, см. имитацию отжига).

   • I3 (терминация): достигается либо критерий останова, либо зацикливание предотвращено (табулирование, счетчик итераций, отсутствие улучшений).

Базовые классы эвристик (формально и практично)

1. Жадные алгоритмы (Greedy)
   

   На шаге выбирается локально лучший кандидат по жадной функции φ(state, option).
   Пример жадного для рюкзака (вещественный вес/ценность): сортировка по убыванию value/weight, взятие до заполнения.
   Плюсы: скорость O(n log n) (через сортировку). Минусы: возможен большой разрыв от оптимума в целочисленных вариантах.

2. Поиск с эвристикой: A*
   

   Функция приоритета: F(v) = g(v) + h(v).
   Свойства:

   • При допустимой h A* находит оптимальный путь.

   • При согласованной h достаточно не уменьшать F при релаксациях, что упрощает корректность.
     Правило A*: выбирайте h максимально информативной, но сохраняющей h(v) ≤ h*(v).

3. Локальный поиск и подъём на холм (Hill Climbing)
   

   Итерация: x := argmin{ f(y) : y ∈ N(x) } до неподвижной точки.
   Риски: застревание в локальном минимуме.
   Противоядия: случайные перезапуски, большие шаги (2-opt, k-opt), табу-память.

4. Имитация отжига (Simulated Annealing)
   

   Вероятностное принятие ухудшений:

   Δ = f(y) - f(x)

   вероятность принятия: p = exp( -Δ / T )

   где T > 0 – температура, по расписанию уменьшается, например

   T_k = T0 * α^k, 0 < α < 1

   Суть: позволяет выходить из локальных минимумов; при убывании T стремится к «жадности».

5. Табу-поиск (Tabu Search)
   

   Ведётся память запрещённых ходов/состояний Tabu с горизонтом L.
   Правило Tabu: не посещать запрет в течение L шагов, кроме критерия устремления (aspiration), если новое качество лучше лучшего найденного.

6. Эволюционные/генетические алгоритмы (GA)
   

   Популяция P решений, оператор отбора, кроссовера, мутации.

   • Вероятность отбора по приспособленности (для максимизации):

   P(i) = fitness(i) / Σ_j fitness(j)

   • Критично: кодирование решения, баланс мутаций/скрещиваний, давление отбора.

7. Муравьиные алгоритмы (ACO)
   

   Вероятность выбора ребра (i,j):

   P(i→j) = [τ_ij]^α * [η_ij]^β / Σ_k [τ_ik]^α * [η_ik]^β

   где τ_ij – феромон, η_ij – видимость (обычно 1/длина), α,β – веса. Обновление:

   τ_ij := (1 - ρ) * τ_ij + Δτ_ij,   0 < ρ ≤ 1

   Смысл: баланс между опытом (феромон) и жадностью (видимость).

Конструирование эвристик: строгие правила

R1. Сохраняйте допустимость. Любое частичное решение должно оставаться потенциально продолжимым до корректного полного.
R2. Вычислительная экономия. Выбирайте h дёшево считаемой; лучше «чуть слабее, но в 10 раз быстрее».
R3. Декомпозиция. Разбивайте задачу на независимые компоненты; h = h1 + h2, если компоненты не пересекаются по ресурсам.
R4. Нормирование. Приводите разные факторы к сопоставимым шкалам (z-нормировка, деление на максимум).
R5. Рестарты и диверсификация. При локальных застреваниях используйте многократные пуски с разными посевами.
R6. Контроль остановки.
Критерии: лимит времени/итераций, стагнация (no_improve ≥ K), достижение «достаточно хорошего» f(x) ≤ τ.

Эвристики для типовых задач (ориентиры для ЕГЭ)

1. На графах
   

   • Кратчайший путь: A* с h(v) – эвклидово/манхэттенское расстояние (для сеток) с допустимостью h ≤ h*.

   • Обходы/покрытия: жадные по ближайшей вершине/ребру; локальные улучшения 2-opt, 3-opt.

2. Рюкзак (0–1)
   

   • Жадная инициализация: отсортировать по value/weight, набрать до переполнения, затем локально заменить пары на один более «удобный» предмет.

   • Верхняя граница (для gap): непрерывная релаксация (дозаполнить рюкзак дробной частью).

3. Расписание
   

   • Правило СЖР (Shortest Job Rule): сначала короткие работы → уменьшает среднее время ожидания.

   • С приоритетами: весовая жадность по w_i / t_i.

Оценка и верификация (минимум практики)

• Бенчмарки: набор задач разной сложности и структуры.
• Повторяемость: фиксируйте seed.
• Сравнение: с базовой жадной и с «разумной» верхней/нижней оценкой.
• Отчётность: храните лучшую стоимость, время, число итераций, долю улучшений.

Мини-шпаргалка

A*: приоритет F(v) = g(v) + h(v),  h допустима: 0 ≤ h(v) ≤ h*(v)

Имитация отжига:

Δ = f(y) - f(x),  T_k = T0 * α^k,  p = exp( -Δ / T_k )

Табу:

Tabu-список длины L, запрет последних L ходов, критерий устремления – разрешить, если f(x_new) < f(best)

Генетика:

P(отбора i) = fitness(i) / Σ fitness, кроссовер + мутация, элитизм сохраняет best

Муравьи:

P(i→j) = [τ_ij]^α [η_ij]^β / Σ_k [τ_ik]^α [η_ik]^β

τ_ij := (1 - ρ) τ_ij + Δτ_ij

Аппрокс. отношение (min-задача):

ρ(x) = f(x) / f(x*)  (ρ ≥ 1),  gap = (f(x) - LB) / max(1, |LB|)

Связь с ЕГЭ по информатике

• Задания на графы и строки выигрывают от умения строить оценки и локальные улучшения.
• Требуется строгое понимание корректности (допустимость, инварианты), умение анализировать сложность и границы.
• Эвристическое мышление помогает быстро находить путь к решению при ограниченном времени.

Пять упражнений (академический формат)

Упражнение 1. Конструирование допустимой эвристики для A*

Дан прямоугольный лабиринт на сетке с разрешёнными шагами вверх/вниз/влево/вправо. Стоимость шага – 1.
a) Докажите, что h(v) = манхэттенское_расстояние(v, goal) допустима и согласована.
b) Предложите более сильную h', если разрешены диагонали со стоимостью 1.5 (подсказка: евклидова метрика, затем привести к допустимому виду).
c) Оцените, как изменится число развёрнутых вершин при переходе от h=0 (Дейкстра) к h(v).

Упражнение 2. Рюкзак 0–1: жадная и локальное улучшение

Имеется набор предметов (w_i, v_i) и вместимость W.
a) Постройте жадное решение по убыванию v_i / w_i.
b) Предложите операцию 2-opt: заменить пару выбранных предметов на один невыбранный, если улучшается v и не нарушается ограничение по весу.
c) Оцените верхнюю границу стоимости через непрерывную релаксацию (добавление дробной части) и вычислите gap.

Упражнение 3. Имитация отжига: расписание параметров

Для задачи минимизации функции f(x) с окрестностью N(x) выберите T0, α, число итераций K.
a) Обоснуйте выбор T0 через долю принимаемых ухудшений в начале (например, ~0.8 при типичных Δ).
b) Сравните геометрическое и линейное расписания температуры по времени сходимости и качеству.
c) Предложите критерий остановки по стагнации и объясните, как он влияет на дисперсию результата.

Упражнение 4. Муравьиный алгоритм для TSP (малая размерность)

Для полного графа по городам 1..n с длинами d_ij требуется приблизительный цикл минимальной длины.
a) Запишите формулы выбора следующей вершины и обновления феромона, указав параметры α, β, ρ.
b) Объясните роль η_ij = 1 / d_ij.
c) Предложите локальный улучшатель (2-opt) после построения тура и оцените прирост качества.

Упражнение 5. Табу-поиск и предотвращение зацикливания

В задаче размещения n объектов по m местам разрешены операции обмена местами.
a) Объясните, как длина L табу-списка влияет на диверсификацию и скорость сходимости.
b) Введите критерий устремления: разрешить ход, если f(x_new) < f(best). Покажите, что инвариант допустимости не нарушается.
c) Предложите стратегию динамической настройки L (увеличение при стагнации, уменьшение при частых улучшениях).

Заключение

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