Уменьше́ние разли́чий (англ. hill climbing – карабканье на холм, восхождение на холм), эвристическая стратегия, являющаяся эффективной для приближения к оптимальному решению. Используется в исследованиях искусственного интеллекта, в линейном программировании и комбинаторной оптимизации, а также как элемент психологической теории мышления.

Как итеративный метод математической оптимизации относится к семейству локального поиска. «Карабканье на холм» является итеративным (многократно повторяющимся) алгоритмом, который начинается с произвольного решения задачи, а затем пытается найти лучшее решение, внося в него постепенные изменения. Если изменение приводит к лучшему решению, в новое решение вносится ещё одно изменение, и так далее, пока все дальнейшие улучшения не будут найдены. Данный метод выступает эффективным способом приближения к оптимальному решению задачи благодаря своей итеративности (Optimal sizing of generalized memory … 2016). Относительная простота алгоритма уменьшения различий делает его популярным среди оптимизирующих алгоритмов: метод широко используется в искусственном интеллекте.

При простом восхождении на холм выбирается первый более близкий узел, тогда как при восхождении на холм с самым крутым подъёмом сравниваются все последующие узлы и выбирается наиболее близкий к решению. Оба варианта ведут к неудаче, если нет такого более близкого к решению узла. Это может произойти, если в пространстве поиска существуют локальные максимумы, которые не являются решениями. Восхождение на холм с самым крутым подъёмом похоже на поиск наилучшего первого шага, который опробует все возможные расширения текущего пути вместо только одного. Существует несколько видов стратегии «карабканья на холм»: простое, стохастическое и случайное повторное «восхождение на холм».

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

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

Психологические исследования показали, что эвристическая стратегия уменьшения различий является реальным элементом человеческого мышления и выступает важной составной частью процесса решения многих видов задач (Newell. 1972). Согласно теории проблемного пространства (PST), решение проблем определяется как поиск в проблемном пространстве. Проблемное пространство – это пространство логических возможностей, которое определяется начальным состоянием (проблемой), целевым состоянием (решением) и операторами, которые могут быть применены к проблеме. Предполагается, что сложность задачи зависит от размера проблемного пространства – чем больше проблемное пространство, тем сложнее задача. Классической проблемой, которая может описана с помощью теории проблемного пространства, является задача «Ханойская башня», в которой предлагается переместить два диска с колышка A на колышек C, соблюдая следующие правила: а) одновременно может быть перемещён только один диск и б) диск большего размера никогда не может быть помещён на диск меньшего размера (Ollinger. 2009).

При решении задач могут применяться эвристики, ограничивающие количество возможных путей решения в проблемном пространстве, что способствует более эффективному и целенаправленному решению (Lindsay. 1981). В основе эвристики уменьшения различий лежит правило всегда выбирать ход, который преобразует текущее состояние в состояние, максимально похожее на состояние цели, что предполагает некоторую меру расстояния, которая оценивает сходство между текущим состоянием и целевым состоянием. В задаче Ханойской башни сходство может быть определено как количество дисков, которые уже находятся на колышке C: после установки маленького диска на колышек C текущее состояние больше похоже на целевое состояние, чем на начальное состояние (Ollinger. 2009).