Любой, кто хочет серьезно подойти к изучению искусственного интеллекта, начинает с изучения проблемы удовлетворения ограничений. В этой статье я познакомлю вас с CSP: я объясню, что это такое, чем они могут быть полезны для вас и как их решить, на практическом примере, взятом непосредственно из нации кенгуру 🦘.
В настоящее время CSP используются во многих областях, таких как биология (секвенирование ДНК), базы данных ограничений, диагностика, распознавание естественного языка и т. Д.
Что такое проблема удовлетворения ограничений?
Проблемы удовлетворения ограничений (CSP) представляют собой класс проблем, в которых существуют некоторые ограничения между объектами внутри этой проблемы.
Формально CSP состоит из трех компонентов:
1. Набор переменных (V = {V1… Vn})
2. Область для каждой переменной (D = {D1… Dn })
3. Набор ограничений (C)
Решения
Как и у любой проблемы, у CSP есть решения; но нам нужно определить «понятие решения». Итак, начнем с состояний:
Состояние в CSP - это присвоение значений некоторым или всем переменным; мы определяем как частичное присвоение в первом случае (где не каждая переменная имеет назначение) и как полное присвоение в другом случае. Мы также определяем согласованное назначение как одно назначение, удовлетворяющее всем ограничениям.
Решение для CSP (или состояния цели) - это полное и последовательное задание.
CSP: пример 🦘
Наконец, мы можем увидеть пример. Это известная «проблема раскраски карты Австралии», которую можно описать следующим образом:
Вы должны раскрасить каждый регион Австралии тремя цветами (красный, сине-зеленый), чтобы ни одна соседняя территория не имела такого же цвета.
Хорошо, на первый взгляд это может быть даже слишком просто, но давайте определимся с CSP:
1. V = {WA, NT, Q, NSW, V, SA, T}
2. D = {green , красный, синий}, в этой задаче все переменные имеют один и тот же домен
3 C = {«соседние области не могут иметь одинаковый цвет»}
График ограничений
Первое, что мы можем сделать, чтобы лучше понять эту проблему, - это определить граф ограничений, который полезен для просмотра отношений между переменными.
Граф ограничений - это неориентированный граф, в который мы помещаем узел для каждой переменной (из исходного CSP) и ребро между двумя узлами, если между переменными, представленными узлами, есть ограничение.
Хорошо, теперь мы можем подумать о поиске решения нашей проблемы.
Алгоритмы генерации и тестирования
Вы когда-нибудь слышали о хакерской атаке с использованием грубой силы? Здесь тот же принцип. Эта стратегия обеспечивает создание полного присвоения каждой переменной, проверки того, является ли это назначение решением, проверки выполнения каждого ограничения. Если да, то эта стратегия нашла решение, если нет, начните заново. Это не лучшая стратегия, потому что там много бесполезной работы. Вместо этого давайте подумаем о более разумном решении.
Возврат
Эта стратегия включает проверку ограничения после каждого присваивания одной переменной, а не после того, как каждая переменная присваивается, как в стратегии Generate-and-Test.
Таким образом, если некоторые ограничения нарушаются, эта стратегия возвращается к предыдущим вариантам (отмена задание) и пробует другое задание.
В австралийской задаче мы могли бы иметь такое поведение:
Стратегия начинается с пустого присваивания, выбирается WA в качестве первого выбора (не важно, с чего начать). WA имеет три возможности (красный, синий или зеленый).
Стратегия выбирает одно присвоение и выполняет проверку ограничений. Если есть нарушение ограничения, он отменяет (или откатывает) назначение и пытается с другим назначением. Довольно просто!
О CSP можно сказать гораздо больше. Если вам понравилась эта статья и вы заинтересованы в других статьях этого жанра, я прошу вас нажать кнопку хлопать, чтобы сообщить мне об этом.
И если вы лайк, можешь оставить свой отзыв о Telegram!
