На этом шаге мы рассмотрим, что это за задачи и приведем общие алгоритм их решения.
Многие задачи, для решения которых используются компьютерные вычисления, можно в целом отнести к категории задач с ограничениями (constraint-satisfaction problems, CSP). CSP-задачи состоят из переменных, допустимые значения которых попадают в определенные диапазоны, известные как области определения. Для того чтобы решить задачу с ограничениями, необходимо удовлетворить существующие ограничения для переменных. Три основных понятия - переменные, области определения и ограничения - просты и понятны, а благодаря их универсальности задачи с ограничениями получили широкое применение.
Рассмотрим пример такой задачи. Предположим, что вы пытаетесь назначить на пятницу встречу для Джо, Мэри и Сью. Сью должна встретиться хотя бы с одним человеком. В этой задаче планирования переменными могут быть три человека - Джо, Мэри и Сью. Областью определения для каждой переменной могут быть часы, когда свободен каждый из них. Например, у переменной "Мэри" область определения составляет 2, 3 и 4 часа пополудни. У этой задачи есть также два ограничения. Во-первых, Сью должна присутствовать на встрече. Во-вторых, на встрече должны присутствовать по крайней мере два человека. Решение этой задачи с ограничениями определяется тремя переменными, тремя областями определения и двумя ограничениями, тогда задача будет решена и при этом не придется объяснять пользователю, как именно (рисунок 1).
Рис.1. Задачи планирования - это классическое применение структур для удовлетворения ограничений
В некоторых языках программирования, таких как Prolog и Picat, есть встроенные средства для решения задач с ограничениями. В других языках обычным подходом является создание структуры, которая включает в себя поиск с возвратами и несколько эвристик для повышения производительности поиска. Начиная с этого шага, мы сначала создадим структуру для CSP-задач, которая будет решать их простым рекурсивным поиском с возвратами. Затем воспользуемся этой структурой для решения нескольких примеров таких задач.
На следующем шаге мы рассмотрим построение структуры.
