Алгоритм с минимальными конфликтами показал себя чрезвычайно эффективным при решении многих задач CSP, особенно при наличии подходящего начального состояния. Его производительность показана в последнем столбце табл. 5.1. Больше всего достойно удивления то, что при решении задачи с п ферзями время прогона алгоритма с минимальными конфликтами остается почти независимым от размера задачи (если не учитываются затраты времени на первоначальную расстановку ферзей). Данный алгоритм решает в среднем за 50 этапов (после начального присваивания) даже задачу с миллионом ферзей. Это замечательное достижение стало стимулом, побудившим к проведению значительной части исследований по локальному поиску в 1990-х годах, а также позволило уточнить различие между легкими и трудными задачами, которое дополнительно будет рассматриваться в главе 7. Грубо говоря, задача с п ферзями является легкой для локального поиска, поскольку решения плотно распределены по всему пространству состояний. Кроме того, алгоритм с минимальными конфликтами успешно применяется при решении трудных задач. Например, он использовался для планирования наблюдений на космическом телескопе Хаббл, что позволило сократить затраты времени на планирование наблюдений, намеченных для проведения в течение одной недели, с трех недель (!) примерно до 10 минут.

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