БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
В самых ранних работах, относящихся к проблематике удовлетворения ограничений, главным образом рассматривались числовые ограничения. Выраженные в виде уравнений ограничения с целочисленными областями определения были исследованы индийским математиком Брахмагуптой в VII веке; их часто называют диофантовыми уравнениями в честь греческого математика Диофанта (около 200— 284 гг.), который в своих исследованиях фактически рассматривал область определения положительных рациональных чисел. Систематические методы решения линейных уравнений путем удаления переменных исследовались Гауссом [527]; истоки подходов к решению ограничений с линейными неравенствами можно найти в работах Фурье [487].
Задачи удовлетворения ограничений с конечными областями определения также имеют долгую историю. Например, одной из старых задач в математике является раскрашивание графа (раскрашивание карты — частный случай данной задачи). Согласно данным, приведенным в [125], гипотезу о четырех цветах (в соответствии с которой любой плоский граф можно раскрасить с помощью четырех или меньшего количества цветов) впервые выдвинул Френсис Гутри, студент де Моргана, в 1852 году. Эта задача не поддавалась решению (несмотря на то, что в некоторых публикациях утверждалось обратное) до тех пор, пока доказательство не было получено с помощью компьютера Аппелем и Хакеном [35].
Специальные классы задач удовлетворения ограничений рассматривались на протяжении всей истории развития компьютерных наук. Одним из самых первых примеров решения таких задач, оказавшим наибольшее влияние, была система Sketchpad [1476], которая решала геометрические ограничения на чертежах и была предшественником современных программ рисования и инструментальных средств САПР. Выявлению того, что задачи CSP представляют собой общий класс задач, мы обязаны Уго Монтанари [1073]. Первые попытки приведения задач CSP высокого порядка к чисто бинарным задачам CSP с помощью вспомогательных переменных (см. упр. 5.11) были впервые предприняты в XIX веке логиком Чарльзом Сандерсом Пирсом. Соответствующие методы были введены в тематику CSP Дектером [367] и доработаны Бакусом и ван Биком [55]. Задачи CSP с предпочтениями между решениями широко рассматривались в исследованиях по оптимизации; обобщение инфраструктуры CSP, позволяющее использовать предпочтения, приведено в [134]. Для решения задач оптимизации может также применяться алгоритм устранения интервалов [369].
Использование поиска с возвратами для удовлетворения ограничений было предложено Битнером и Рейнгольдом [135], но эти ученые проследили истоки идей своего основного алгоритма до работ XIX века. Кроме того, Битнер и Рейнгольд впервые предложили использовать эвристику MRV, названную ими эвристикой с наиболее ограниченной переменной. Брелаз [181] использовал степенную эвристику для устранения неопределенности, возникающей после применения эвристики MRV. Полученный в итоге алгоритм, несмотря на его простоту, все еще остается наилучшим методом раскрашивания произвольных графов в к цветов. Харалик и Эллиот [618] предложили эвристику с наименее ограничительным значением.
Расширению популярности методов распространения ограничений способствовало успешное решение Вальцем [1552] задач полиэдральной линейной разметки для систем компьютерного зрения. Вальц показал, что применение методов распространения ограничений при решении многих задач позволяет полностью исключить необходимость в использовании возвратов. Монтанари [1073] ввел понятие сетей ограничений и предложил метод распространения ограничений на основе понятия совместимости пути. Ален Макворт [967] предложил алгоритм АС-3 для обеспечения совместимости дуг, а также выдвинул общую идею о том, что поиск с возвратами необходимо сочетать с обеспечением совместимости некоторой степени. Более эффективный алгоритм обеспечения совместимости дуг, АС-4, был разработан Мором и Хендерсоном [1068]. Вскоре после появления статьи Макворта исследователи приступили к экспериментам в области поиска компромисса между затратами на обеспечение совместимости и достигаемыми за счет этого преимуществами с точки зрения сокращения объема поиска. Харалик и Эллиот [618] предпочли минимальный алгоритм предварительной проверки, описанный Макгрегором [1028], а Гашниг [522] предложил применять полную проверку совместимости дуг после присваивания значения каждой переменной; в дальнейшем соответствующему алгоритму в работе Сабина и Фрейдера [1335] было присвоено название MAC. В последней статье представлены некоторые убедительные свидетельства того, что при решении более трудных задач CSP полная проверка совместимости дуг вполне окупается. Фрейдер [497], [498] исследовал понятие k-совместимости и ее связь со сложностью решения задач CSP. Апт [36] описал универсальную алгоритмическую инфраструктуру, в рамках которой могут быть проанализированы алгоритмы распространения совместимости.
Специальные методы обработки ограничений высокого порядка были созданы в основном в контексте логического программирования в ограничениях. Превосходный обзор исследований в этой области приведен в [987]. Ограничение Alldiff исследовалось в [1272]. Ограничения с пределами были включены в тематику логического программирования в ограничениях ван Хентенриком и др. [1533].
Основной метод обратного перехода был разработан Джоном Гашнигом [521], [522]. Кондрак и ван Бик [831] показали, что этот алгоритм по сути перекрывается алгоритмом предварительной проверки. Обратный переход, управляемый конфликтами, был предложен Проссером [1240]. Наиболее общая и мощная форма интеллектуального поиска с возвратами фактически разработана еще довольно давно Стал-маном и Зюссманом [1456]. Предложенный ими метод поиска с возвратами, управляемого зависимостями, привел к разработке систем обеспечения истинности [409], которые будут рассматриваться в разделе 10.8. Связь между этими двумя научными областями проанализирована в [348].
В указанной работе Сталмана и Зюссмана была также предложена идея регистрации ограничения, в соответствии с которой частичные результаты, полученные в ходе поиска, можно сохранять и повторно использовать на последующих этапах этого поиска. Данная идея была введена формально в поиск с возвратами Дектером [366]. Особенно простым методом является проставление обратных отметок [522], в котором для предотвращения повторной проверки ограничений сохраняются и используются совместимые и несовместимые попарные присваивания. Проставление обратных отметок можно комбинировать с обратным переходом, управляемым конфликтами; в [831] представлен гибридный алгоритм, который превосходит любой из этих методов, отдельно взятых (и это подтверждается формальным доказательством). В методе динамического поиска с возвратами [558] сохраняются успешные частичные присваивания из полученных позднее подмножеств переменных при поиске с возвратами по предыдущему варианту, который не влияет на дальнейший успех.
Применение локального поиска при решении задач удовлетворения ограничений стало популярным после публикации [799] с описанием метода эмуляции отжига (см. главу 4), который широко используется для решения задач планирования. Эвристика с минимальными конфликтами была впервые предложена в [601] и независимо разработана в [1058]. В [1447] показано, как эта эвристика может использоваться для решения задачи с 3 000 000 ферзей меньше чем за минуту. Этот поразительный успех локального поиска на основе эвристики с минимальными конфликтами при решении задачи с п ферзями привел к переоценке характера и распространения "легких" и "трудных" задач. В [244] исследовалась сложность задач CSP, сформированных случайным образом, и было обнаружено, что почти все такие задачи являются либо тривиально легкими, либо не имеют решений. "Трудные" экземпляры задач встречаются, только если параметры генератора задач устанавливаются в некотором узком диапазоне, в пределах которого лишь примерно половина задач является разрешимой. Этот феномен рассматривается дополнительно в главе 7.
Исследования, касающиеся структуры и сложности задач CSP, начались с [499], где было показано, что поиск в деревьях с совместимыми дугами происходит без каких-либо возвратов. Аналогичные результаты применительно к ациклическим гиперграфам были получены в области теории баз данных [92]. Со времени публикации этих статей достигнут значительный прогресс в части получения более общих результатов, касающихся связи между сложностью решения задачи CSP и структурой ее графа ограничений. Понятие ширины дерева было введено специалистами по теории графов Робертсоном и Сеймуром [1295]. Дектер и Перл [372], [373], основываясь на работе Фрейдера, применяли то же понятие (названное ими индуцированной шириной) к задачам удовлетворения ограничений и разработали подход с древовидной декомпозицией, кратко описанный в разделе 5.4. Опираясь на эту работу и на результаты из области теории баз данных, Готлобб и др. [585], [586] разработали понятие ширины гипердерева, которое основано на методе характеризации задачи CSP как гиперграфа. Они не только показали, что любую задачу CSP с шириной гипердерева wможно решить за время 0{nw+1logn), но и обосновали утверждение, что критерий ширины гипердерева превосходит все ранее предложенные критерии "ширины" в том смысле, что в некоторых случаях ширина гипердерева является конечной, тогда как ширина, определяемая другими критериями, — неограниченной.
В литературе можно найти несколько хороших обзоров с описанием методов решения задач CSP, включая [73], [370] и [866], а также энциклопедические сборники статей [368] и [968]. В [1194] приведен обзор разрешимых классов задач CSP и описаны как методы структурной декомпозиции, так и методы, основанные на свойствах областей определения или свойствах самих ограничений. В [831] приведен аналитический обзор алгоритмов поиска с возвратами, а в [56] приведен обзор, характеризующийся большей практической направленностью. В [987] и [1514] эта тематика рассматривается гораздо более глубоко, чем было возможно ее представить в данной главе. Некоторые интересные приложения описаны в сборнике статей [500], который вышел под редакцией Фрейдера и Макворта. Статьи на тему удовлетворения ограничений регулярно публикуются в журнале Artificial Intelligence и в специализированном журнале Constraints. Основным местом встречи специалистов в этой области является конференция International Conference on Principles and Practice of Constraint Programming, часто называемая просто СР.