Реферат на тему Методы распространения ограничений

Содержание:

ВВЕДЕНИЕ 3

1 МЕТОДЫ РАСПРОСТРАНЕНИЯ ОГРАНИЧЕНИЙ: ОСНОВНЫЕ КОНЦЕПЦИИ 4

1.1 ОСНОВНЫЕ ПОНЯТИЯ 4

2. МЕТОДЫ РАСПРОСТРАНЕНИЯ ОГРАНИЧЕНИЙ НАД КОНЕЧНЫМИ ОБЛАСТЯМИ 5

2.1 ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ ЗАДАЧИ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ 5

2.2 СВЕДЕНИЕ ЗАДАЧ И СОВМЕСТНОСТЬ 7

2.3 СООТНОШЕНИЯ МЕЖДУ СОВМЕСТНОСТЬЮ И УДОВЛЕТВОРЯЕМОСТЬЮ 10

ЗАКЛЮЧЕНИЕ 12

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 13

Введение:

Распространение ограничений (иногда также называемое удовлетворением ограничениям или программированием в ограничениях) является одной из наиболее интенсивно развивающихся областей искусственного интеллекта, связанной с решением разнообразных задач. Многие проблемы в различных приложениях могут быть сформулированы как задачи удовлетворения ограничений, хотя люди, не являющиеся специалистами в этой области, не всегда могут это увидеть. Представление же проблемы в виде задачи распространения ограничений позволяет применять для ее решения наряду со специальными методами прикладной области достаточно эффективные и универсальные методы решения задач распространения ограничений.

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

В рамках этих исследований получено достаточно много интересных и важных результатов, а также создан ряд прикладных систем, успешно применяемых для решения широкого спектра конкретных задач.

Целью работы является: изучить особенности методов распространения ограничений.

Заключение:

Результатом данной работы является изучение методов распространения ограниче-ний.

Во время выполнения работы были выполнены следующие задачи:

— изучено понятие распространения ограничений.

— изучены методы распространения ограничений.

— проанализирована предметная область.

Программа разработана в соответствии с заданием.

Фрагмент текста работы:

1 Методы распространения ограничений: основные концепции 1.1 Основные понятия

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

В методах распространения ограничений выделяют два класса методов — мето-ды для задач с дискретными переменными, называемые распространением ограничений над дискретными областями [5], и методы для задач с вещественными переменными, называемые распространением ограничений над непрерывными областями [1]. Для каж-дого из этих классов разработан свой набор эффективных алгоритмов и построены соот-ветствующие прикладные системы [2]. В настоящее время методы распространения огра-ничений все чаще объединяются с другими подходами, порождая новые эффективные ал-горитмы. Например, распространение ограничений над конечными областями использу-ется в комбинации с методами исследования операций и линейного программирования, а распространение ограничений над непрерывными областями использует методы интер-вальной математики.

Говоря неформально, задача удовлетворения ограничений — это задача, состо-ящая из конечного числа переменных, каждая из которых связана с некоторой областью ее определения (дискретной или непрерывной), и конечного множества ограничений, ко-торые ограничивают множества значений переменных, принимаемых одновременно. Ре-шение задачи удовлетворения ограничений состоит в присваивании значения каждой пе-ременной так, чтобы одновременно удовлетворялись все ограничения. Целью может яв-ляться как нахождение одного такого набора (любого или с заданным свойством), так и нахождение всех наборов. 2. Методы распространения ограничений над конечными областями 2.1 Формальное определение задачи удовлетворения ограничений Определение 2.1. Областью определения переменной называется множество всех возможных значений, которые могут быть присвоены этой переменной. В дальней-шем мы будем говорить просто «область переменной» и обозначать эту область перемен-ной x через D . x. Если область переменной содержит только числовые значения, то эта переменная называется числовой переменной. В качестве области числовых переменных обычно рассматривается кольцо целых чисел Z, точнее ее конечные подмножества. Если область переменной содержит два значения, то такая переменная называется булевой пе-ременной и ее значениями считают 0 и 1. Если область переменной есть множество пере-числимых значений (например, дни недели, цвета и т.д.), то переменная называется сим-вольной переменной.

Определение 2.2. Меткой называется пара переменная-значение, которая опре-деляет присваивание некоторого значения переменной. Метка, определяющая присваива-ние значения v переменной x, обозначается . Метка осмысленна только в том случае, когда v D∈ x .

Определение 2.3. Составной меткой называется одновременное присваивание значений некоторому множеству переменных. Составная метка, присваивающая значения соответственно переменным , обозначается . Здесь также полагается, что для i=1,…,n. v1 n , , K v x x ) 1 n , , K ( 11 K ,,,, vxvx nn ><>< i ∈ Dv xi
Составная метка рассматривается как множество, поэтому порядок переменных в ней не важен, и она не может содержать двух одинаковых меток.

Определение 2.4. k-составной меткой называется составная метка, присваиваю-щая k значений одновременно k переменным.

Определение 2.5. Пусть m и n — целые числа и m n ≤ . Будем говорить, что m-составная метка M есть проекция n-составной метки N, если все метки из M являются метками в N. Проекция обозначается Pr(N,M). Например, (,) является проекци-ей (,,).

Определение 2.6. Ограничением на некотором множестве переменных S назы-вается набор составных меток для всех переменных множества S. Будем обозначать огра-ничение CS.