Содержание к диссертации
Введение
Глава 1. Методы и программные средства решения задач удовлетворения ограничений с конечными областями значений переменных (обзор) 14
1.1. Основные понятия и определения ы
1.2. Классификация задач удовлетворения ограничений с конечными областями и алгоритмов их решения 18
1.3. Оценка эффективности алгоритмов 28
1.4. Инструментальные средства автоматизации программирования в булевых ограничениях 29
Глава 2. Алгоритмы решения задачи выполнимости булевых ограничений.. 32
2.1. Базовый алгоритм зз
2.2. Усовершенствованный алгоритм 35
2.3. Гибридный алгоритм 37
2.4. Сравнительный анализ разработанных алгоритмов
Глава 3. Автоматизация построения булевых моделей дискретных задач 43
3.1. Средства спецификации булевых ограничений в международном формате dimacs и его расширениях 43
3.2. Булевы модели некоторых дискретных задач 48
3.3. Технология булева моделирования дискретных задач 59
3.4. Высокоуровневые языковые средства задания булевых ограничений в инструментальном комплексе ребус 65
Глава 4. Интегрированная инструментальная визуальная среда ребус для автоматизации программирования и решения задач в булевых ограничениях 76
4.1. Постановка задачи и основные функциональные требования к инструментальному комплексу ребус 76
4.2. Концептуальная модель, принципы организации и архитектура инструментального комплекса ребус 7s
4.3. Архитектура и функциональные возможности подсистем инструментального комплекса ребус 86
4.4. Визуальный пользовательский интерфейс и основные аспекты программной реализации ик ребус 93
Заключение 100
Сп исок литературы
- Классификация задач удовлетворения ограничений с конечными областями и алгоритмов их решения
- Усовершенствованный алгоритм
- Булевы модели некоторых дискретных задач
- Концептуальная модель, принципы организации и архитектура инструментального комплекса ребус
Введение к работе
Одним из перспективных направлений исследований в современном программировании [1,2] является направление, связанное с программированием в ограничениях (Constraint Programming - СР). Теоретическую основу этого направления составляют методы решения задач удовлетворения ограничений (Constraint Satisfaction Problem — CSP). Задачи удовлетворения ограничений представляются в виде множества переменных и системы ограничений над ними. Решением задачи является такой набор значений этих переменных (из области допустимых значений), который удовлетворяет всем заданным ограничениям. Многие задачи науки и техники формулируются или могут быть сформулированы как задачи удовлетворения ограничений.
К важному классу ограничений относятся булевы ограничения, представляемые в виде систем булевых уравнений, и связанные с этим классом задача выполнимости булевых ограничений (Boolean Constraint Satisfaction Problem - BCSP) и задача программирования в булевых ограничениях (Constraint Boolean Programming - СВР).
В [3,4] отмечается, что булевы уравнения естественным образом возникают при исследованиях, имеющих дело с отображениями, области определения и значений которых лежат в пространствах векторов с двоичными компонентами В" (52={0,1}). Таковы, например, уравнения
алгебры логики; соотношения, описывающие бинарные отношения со свойствами типа транзитивности, связности, асимметрии и т.д.; булевы неравенства; задачи, описывающие нахождение оптимальных переключательных схем; задачи проверки специальных свойств булевых функций, таких как линейность, монотонность, самодвойственность, существенная зависимость булевой функции от переменной и т.д.
Задача булевой выполнимости является фундаментальной проблемой в математической логике и теории вычислений. Следует отметить, что многие практические задачи могут быть сформулированы как задачи булевой выполнимости (или решение системы булевых уравнений). К ним относятся [5] задачи криптографии, логического программирования, доказательства теорем, дедуктивного и абдуктивного вывода, нейросетевых вычислений, машинного зрения, планирования действий роботов, планирования вычислений в системах синтеза программ, оптимального проектирования, разработки систем баз знаний, компьютерной графики, моделирования цепей, разработки СБИС, создания новых компьютерных архитектур и сетей вычислительных машин, коммуникации, безопасности, составления расписаний, интеллектного управления, различные задачи на графах, шахматной доске и многие другие.
Формально задача решения булевых уравнений формулируется следующим образом [3]: пусть X-(xlt...,xn) - упорядоченное множество
булевых переменных (х^В2 для всех і' = 1,л; В2 ={0,1}). Задано т булевых соотношений (система уравнений) вида
/(^,...,^) = 0, (1)
где /;(1 = 1,т) - произвольные булевы функции своих аргументов. Требуется найти одно, несколько или все решения системы (1) или установить ее несовместность.
Следует заметить, что первая NP-полная задача - задача "выполнимости КНФ" (задача булевой выполнимости или SAT задача) есть, по существу, задача распознавания совместности систем уравнений [6]
*?v-v
где переменная
х, при <У, = 0,
,p = l,k(i)
Двойственная к (2) система уравнений вида (1) записывается следующим образом:
л:/, л...л^(/) =0 (: = 1,...,^). (3)
Известно, что любая система вида (I) может быть представлена одним
эквивалентным уравнением /{хХУ..,,хп) = МУХ*, >—>xi ) = ^. Поэтому далее
будем рассматривать в основном одно стандартное уравнение
/(*„...,*„) = 0. (4)
Известные подходы к решению булевых уравнений. Можно выделить три основных подхода к решению систем булевых уравнений - это аналитический, дискретный и непрерывный.
Истоки аналитического метода можно найти еще у самого Дж. Буля (см., например [7]), который получил решение уравнения с одним неизвестным. Дальнейшее развитие аналитического метода связано с именами его ближайших последователей, таких как У. Джевонс, Э. Шредер и в особенности казанский математик П.С. Порецкий [7]. Уточнение метода Буля-Порецкого выполнено Н.П. Брусенцовым [8]. Систематическое изложение проблемы аналитического решения булевых уравнений к концу 70-х годов представлено в объемной монографии [9]. Акерс [10] использовал в 1959 г. для решения уравнений булевы производные и сформировал основы для развития булевого дифференциального исчисления. В [4] подход Акерса нашел свое дальнейшее развитие. Условия существования решения и вид решений для некоторых специальных важных классов систем булевых уравнений можно найти в работах Чистова В.П. [11] и Пандефа Е. [12]. Из работ последних лет следует выделить исследования B.C. Левченкова [3], в которых получен общий вид решения булева уравнения со многими неизвестными, даны условия единственности решения, а также рассмотрены вопросы решения неявных булевых уравнений. Обсуждение проблемы аналитического решения задачи "выполнимости КНФ" с использованием
средств компьютерной алгебры системы MAPLE (специализированный пакет математической логики) представлен на сайте [13].
В дискретных методах задача решения булева уравнения рассматривается как частный случай задачи удовлетворения ограничений, когда домены, на которых определены переменные, являются бинарными. Поисковое пространство В является дискретным, в котором реализуются
разнообразные стратегии перебора. Самый простой способ — это полный перебор. С целью сокращения поискового пространства предложено много улучшенных методов, таких как алгоритмы с хронологическим возвратом, распространением ограничений, интеллектуальным возвратом, метод резолюций, алгоритмы с применением многозначной логики, алгоритм Дэвиса-Патнема, жадный алгоритм и целый ряд других алгоритмов и их комбинаций (см., например, [6,14,15]). Список комбинаторных SAT-решателей можно найти на сайте [16], Все предлагаемые методы ориентированы на представление левой части булево го уравнения (4) в одной из нормальных форм (конъюнктивной, дизъюнктивной или разностной). Разработка методов и алгоритмов решения булевых уравнений (4) с произвольной левой частью считается [5] перспективным направлением исследований в силу того, что такие уравнения часто возникают в практических задачах.
В непрерывных методах задача решения булевых уравнений из дискретного пространства В% погружается в вещественное пространство R";
далее применяются известные численные методы решения непрерывных уравнений, оптимизации или решения задачи Коши для систем обыкновенных дифференциальных уравнений. Переход в непрерывное пространство позволяет получить некоторую глобальную информацию о расположении нулей булевой функции и, тем самым, повысить размерность решаемых задач и сократить время поиска решения для отдельных классов уравнений. Недостатком численных методов является их неполнота: решение может существовать, но алгоритм его не находит.
Пионерским в этом направлении решения булевых уравнений является итеративный метод СЛО.Маслова [17], который сочетает механизм расширения области поиска (с целочисленной до рациональной) с принципом глобальности обработки информации и итеративной схемой уточнения решения. В [18] приведено три варианта семантики итеративного метода С.Ю.Маслова: это имшшкативная семантика, экстремальная семантика и химико-кинетическая семантика. Интересный подход к погружению задачи решения булевых уравнений из В% в R", основанный на
физических аналогиях и дифференциальных моделях, предложен в [19] - это модель химической кинетики, модель «сотворения мира» и модель резонанса. Из зарубежных работ следует выделить исследования Jun Gu [5], который сводит задачу решения булева уравнения в В1 к задаче безусловной глобальной параметрической оптимизации некоторой целевой функции bR" .
Актуальность темы. Существует достаточно большое количество программ решения задач выполнимости. Список зарубежных систем можно найти на сайте [16]. В качестве входного языка этих программ используется фрагмент международного формата DIMACS [20] представления булевых ограничений в виде конъюнктивной нормальной формы пропозициональной логики (системы булевых ограничений вида (2)). Программы, решающие системы булевых ограничений общего вида (1), автору неизвестны. Средства автоматизации построения булевых моделей (в формате DIMACS) по содержательной (ориентированной на конечного пользователя) постановке задачи в этих программах отсутствуют, взаимодействие с программой возможно только в режиме командной строки (визуальный пользовательский интерфейс отсутствует). Из числа отечественных систем следует выделить решатели UNICL [21], UniCalc [2,22] и интегрированный программный вычислительный комплекс SibCalc [22, 23], предназначенные для решения задач, представленных системами алгебраических уравнений, неравенств и логических выражений и реализованные на основе интервальных методов и
методов распространения ограничений. Эти системы имеют кроме
арифметического логический блок для прямого решения булевых уравнений
и визуальный пользовательский интерфейс, но в основном применяются для
решения численных задач удовлетворения ограничений. Таким образом,
актуальной является проблема разработки эффективного, ориентированного
на конечного пользователя инструментария автоматизации
программирования в булевых ограничениях (включая высокоуровневые средства построения булевых моделей для различных классов дискретных задач).
Цель работы. Основная цель диссертации состоит в исследовании
существующих на данный момент достижений в области решения систем
булевых ограничений; разработка специализированных алгоритмов и
программ для решения булевых уравнений; создании принципиально новой
интегрированной инструментальной среды, объединяющей решатели
комбинаторных задач большой размерности в единую систему,
позволяющую автоматизировать процесс построения булевой модели
решаемой дискретной задачи, выбирать из базы знаний (исходя из свойств
полученной модели и накопленной статистики решения задач) подходящий
алгоритм решения, проводить вычислительный эксперимент, сохранять
результаты расчетов в пользовательской базе данных, осуществлять
тестирование алгоритмов с использованием эталонных тестовых задач и
тестов из библиотеки SATLIB [24], включать в базу знаний
инструментальной среды новые модели и алгоритмы.
Методы исследования. При решении поставленных задач использовались методы системного и прикладного программирования, характерные для разработки инструментальных программных комплексов; методы объектно-ориентированного проектирования и разработки баз знаний и данных; комбинаторные методы дискретной математики и искусственного интеллекта.
Научная новизна. Разработаны и реализованы новые алгоритмы решения булевых уравнений, показавшие на некоторых тестовых задачах сравнительно высокую эффективность. Эти алгоритмы ориентированы как на произвольное представление левой части уравнения, так и на традиционное представление в дизъюнктивной или конъюнктивной нормальной форме (формат DIMACS).
С использованием технологии баз знаний разработана архитектура, языковые средства, алгоритмическое, информационное и программное обеспечение инструментального комплекса (ИК) РЕБУС, обеспечивающего автоматизацию всех этапов программирования в булевых ограничениях. С помощью базовой технологии моделирования ИК РЕБУС получены булевы модели для решения ряда классических дискретных задач (задача об п-ферзях, раскраска графа, покрытие конечного множества системой его подмножеств, ход шахматного коня, задача о голубях и клетках), а так же булевы модели для решения двух практических задач (равномерная загрузка локомотивного депо железной дороги, оперативный план отправления локомотивных бригад).
Практическая значимость. Применение разработанных в диссертации методов и инструментальных средств автоматизации программирования в булевых ограничениях позволяет сократить трудозатраты на разработку, отладку и исследование булевых моделей, повышает качество и сокращает сроки выполнения необходимых многовариантных расчетов. Решатели ИК РЕБУС зарегистрированы в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ) и используются для проведения экспериментальных расчетов по плановым темам НИР в ИДСТУ СО РАН. Применение ИК РЕБУС в учебных целях в качестве программного инструмента решения задач дискретной математики позволяет обучить студентов основным навыкам булева моделирования, наглядно ознакомить их с существующими комбинаторными методами решения классических задач искусственного интеллекта.
Реализация, Исследование, разработка и применение рассматриваемых в диссертации программных средств выполнялись в рамках плановых тем ИДСТУ СО РАН "Методы автоматизации исследования и разработки интеллектных систем" (№ гос. per. 01.99.00 07820, 1999-2001 гг.), "Методы и инструментальные средства организации распределенных вычислений в сети Интернет" (№ гос. per. 01.20.01 11785, 2002-2003 гг.), "Интегрированные информационно-вычислительные и коммуникационные ресурсы: интеллектные методы организации, автоматизации разработки и применения" (2004-2006 гг.), в рамках комплексного интеграционного проекта СО РАН "Методы, технологии и инструментальные средства создания вычислительной инфраструктуры в Internet" (2003-2005 гг.), в рамках проектов РФФИ №98-01-00160 "Численное решение больших разреженных систем булевых уравнений", №01-07-90220 "Разработка инструментальной среды для создания и поддержки функционирования распределенных пакетов знаний в сети Интернет" и №04-07-90358 "Разработка и реализация распределенной вычислительной системы решения булевых уравнений большой размерности", в процессе реализации программы президиума РАН №21 "Разработка фундаментальных основ создания научной распределенной информационно-вычислительной среды на основе технологий GRID" (проект №6 "Планирование и оптимизация схем решения задач в распределенной мультиагентной вычислительной среде ").
Результаты исследований используются в Иркутском государственном университете путей сообщения при проведении практических занятий по дисциплине «Теория дискретных устройств автоматики и телемеханики», а так же в Информационно-вычислительном центре Восточно-Сибирской железной дороги филиала ОАО РЖД для разработки системы поддержки принятия решений при решении задач составления плана ремонта электропоездов и оперативного плана отправления локомотивных бригад в условиях отсутствия жесткого расписания движения грузовых поездов.
Апробация. Основные результаты работы докладывались на
следующих конференциях: I Международной научно-практической
конференции "Интеллектуальные электромеханические устройства, системы
и комплексы" (Новочеркасск, 2000), II Международной научно-практической
конференции "Развивающиеся интеллектуальные системы
автоматизированного проектирования и управления" (Новочеркасск, 2002), V Международной научно-практической конференции "Моделирование. Теория, методы и средства" (Новочеркасск, 2005), на XII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2001), на конференциях "Ляпуновские чтения & Презентация информационных технологий" (Иркутск, 2001, 2002, 2003) , на VII международной конференции "Проблемы управления и моделирования в сложных системах "(Самара, 2005).
Структура работы и публикации. Личный вклад автора. Диссертация состоит из введения, четырех глав, заключения, приложений и списка литературы.
В первой главе определяются основные понятия и терминология,
принятая при изложении материала, приводится обзор основных результатов
по исследованию комбинаторных методов для решения задач
удовлетворения ограничений, рассматриваются существующие
инструментальные средства программирования в булевых ограничениях. Во второй главе предлагаются новые алгоритмы решения задач BCSP, составляющие вычислительное ядро инструментального комплекса РЕБУС. Третья глава содержит описание средств спецификации булевых ограничений в международном формате DIMACS, автоматизированной технологии булева моделирования, лежащей в основе инструментального комплекса РЕБУС и декларативного языка содержательных формулировок ЯСФОР для записи системы булевых ограничений, а также булевы модели ряда дискретных задач, полученные в результате применения этой технологии. В четвертой главе предложены концептуальная модель,
принципы организации, архитектура и программная реализация интегрированной инструментальной визуальной среды ИК РЕБУС, предназначенной для автоматизации программирования в булевых ограничениях.
Приложения содержат дополнительные материалы, включающие информацию о соответствии различных форматов представления системы ограничений, структуре базы знаний ИК РЕБУС, результатах вычислительных экспериментов, о практическом примере построения булевой модели для задачи составления оперативного плана формирования локомотивных бригад.
Содержание диссертации отражено в 14 публикациях в виде статей в сборниках [25], материалов международных [26-30] и российских [31-35] конференций. На программные разработки по теме диссертации получены свидетельства об их официальной регистрации в РОСПАТЕНТ [36-38].
В перечисленных публикациях все результаты, связанные с разработкой архитектуры, языковых средств, алгоритмов и программной реализации ИК РЕБУС, а также проведением вычислительного эксперимента на ЭВМ, получены автором лично. Результаты по булевым моделям и методам решения булевых уравнений получены совместно с научным руководителем Опариным Г.А. и являются неделимыми. Из совместных работ с Феоктистовым А.Г. и Новопашиным А.П. в диссертацию включены только те результаты, которые принадлежат лично автору.
Классификация задач удовлетворения ограничений с конечными областями и алгоритмов их решения
Задачи удовлетворения ограничений используют два типа объектов — переменные с областями значений и ограничения.
Принадлежность алгоритмов, разработанных для решения CSP, к тому или иному классу определяется типами областей значений и ограничений.
В [1] Т.М.Яхно приводит следующую классификацию областей значений переменных и ограничений: Области: конечные /бесконечные; дискретные /интервальные; скалярные /векторные; символьные/числовые; неструктурированные/структурированные. Ограничения: бинарные/ -арные; симметричные / асимметричные; позитивные / негативные; безусловные / условные; неупорядоченные / упорядоченные; статические / динамические; базисные / мета; декларативные / процедурные.
В этой классификации выделены признаки, во многом определяющие оригинальность и эффективность используемых алгоритмов. В многообразии методов получения решения для CSP можно выделить три основных класса: полный поиск в пространстве решений, распространение ограничений и локальный поиск. Алгоритмы полного поиска исследуют пространство частичных решений в глубину и на каждом шаге расширяют частичное решение, присваивая значение еще одной переменной. Эти алгоритмы рассматривают переменные в определенном порядке. Переменным систематически присваиваются значения из доменов, пока не будет найдено решение либо пока не встретится тупик. Худшее время выполнения алгоритмов перебора с возвратами экспоненциально. Причины неэффективности этих алгоритмов рассматривались в работах [1,45,46].
Улучшение эффективности перебора с возвратами требует сокращения размера пространства поиска. Это сокращение может быть достигнуто с помощью двух типов процедур: алгоритмы препроцессорной (предваряющей алгоритм поиска) обработки (статические алгоритмы) и динамические алгоритмы, которые используются во время поиска.
Распространение ограничений. К первому типу относятся алгоритмы распространения ограничений. Распространение ограничений имеет многолетнюю традицию в исследованиях CSP. Это понятие впервые ввел Е. Freuder в работе [42]. Этой же теме посвящены работы [45-54]. Подробный обзор этих работ выполнен российскими и зарубежными исследователями в [1,21,40]. Объем распространения ограничений характеризуется уровнем согласованности CSP, поэтому эти алгоритмы также называются алгоритмами достижения локальной согласованности (совместности).
Алгоритмы распространения ограничений преобразуют исходную CNB эквивалентную, с более явно выраженной структурой, путем вывода новых ограничений и добавления их к сети. По существу, эти алгоритмы осуществляют согласованность небольшой подсети по отношению к входящим в нее ограничениям. Один из основных алгоритмов, называемый согласованностью по дугам — arc consistency, или 2-согласованность, гарантирует, что любое не нарушающее ограничений значение из домена одной переменной имеет аналогичное парное значение в домене любой другой переменной. Согласованность по путям, или 3-согласованность, гарантирует, что любое согласованное решение в подсетях из двух переменных расширяется до третьей переменной, и, в общем, алгоритмы i-согласованности гарантируют, что любая локальная согласованность означенных /-1 переменных может быть расширена до любой і-той переменной. В работе Dechter [55] отмечается, что сложность алгоритмов достижения локальной совместности в наихудшем случае является полиномиальной для размерности задачи, и они часто очень эффективны при обнаружении локальной несогласованности. Так, алгоритм согласованности по узлам (node-consistency - NC), который исключает избыточные значения проверкой доменов одного за другим, имеет сложность 0(dn), где d является максимальной размерностью домена, алгоритм согласованности по дугам (arc-consistency (АС)) имеет квадратичную сложность от размерности задачи [40]. Однако, как подчеркивает Т. Яхно в [1], алгоритм построения сетей, совместных по путям длины п, где п - число всех переменных, потеряет эффективность и будет эквивалентен полному перебору. В связи с этим алгоритмы совместности по путям обычно рассматривают пути длины 2.
В работах [41,57] введено понятие направленной /- согласованности и (d-i- согласованность) и предложены алгоритмы достижения направленной согласованности. Эти алгоритмы направленной согласованности по дугам (DAC), направленной согласованности по путям (DPC) и адаптивной согласованности (ADAPT).
Усовершенствованный алгоритм
Первый (базовый) алгоритм является усовершенствованным алгоритмом Куайна [103] и основан на возможности вычисления булевой функции f(xlt...,x„) при неполностью заданных значениях переменных хх,...,хп. Эта возможность вытекает из следующего свойства операции конъюнкции (дизъюнкции): если в логическом произведении (сумме) один из множителей (слагаемых) равен 0 (1), то и логическое произведение (сумма) принимает значение, равное 0 (1). Пусть функция /( ,,...» „) вычислима при заданных значениях первых аргументов xl=xf,...)xk=x% и незаданных значениях аргументов xk+li... x„ и пусть f(x ,..txl xt+l,...,xri) = f х =В2 для і = \,k,f єВ2. Тогда /(х?,...,Хь,хк+1 ...,х,,) = /0 для любых допустимых значений аргументов л ,..., ,,. Таким образом необходимость перебора по аргументам хк+1,...,хп отпадает, причем, если /=0, то оказывается вычисленным целое множество 2" к решений уравнения (2).
Для численного вычисления значения булевой функции общего вида с неопределенными аргументами используется трехзначная логика Клини Къ [104], в которой переменные и функции определены на множестве В3 ={0,1/2,1}, а операции дизъюнкции, конъюнкции и отрицания соответственно имеют вид: хvу = тах(х,у), хлу = min(x,y), х = 1 -х. Остальные операции логики 1 (импликации, эквивалентности и др.) считаются определенными в логике К3 через операции конъюнкции, дизъюнкции и отрицания согласно соотношениям логики 1 . Предполагается, что значение 1/2 из В3 кодирует ситуацию неопределенности значения переменной или функции в логике L2, а значения 0 и 1 в В3 эквивалентны по смыслу значениям 0 и 1 вВ2. В базовом алгоритме А0 вычисления всех решений уравнения (4), в основе которого лежит описанный выше метод, поиск организуется с начальной точких? =1/2, / = 1,и; элементы множества Въ расположены в порядке 1/2,1,0. Поиск ведется на множествеH(B zH с53"), содержащем 2"+l -1 элементов, каждый из которых удовлетворяет условию: существует такое значение к (1 к п), что xi е {0,1} для i k и JC (= I/2 для і к. Определенный алгоритмом А$ порядок элементов в Н обеспечивает особую простоту управления переходами на множестве Н от одной точки к другой в зависимости от значения функции f{xx,...,х„) в логикеК3.
После останова алгоритма Д, значение переменной к равно числу решений уравнения f(xl9...,x„). Если необходимо найти одно решение, алгоритм Ац следует остановить при к = 1. Параметр t определяет точку возврата при удачном (/ = 0) или неудачном {f = 1) исходе исследования текущей точки ъВ". Параметр увеличивается на 1, если значение функции в Lj не определено (/=1/2вК3). Параметром s определяется количество вычислений булевой функции /( ,,..., „) (подстановок наборов из В" в уравнение (2)) в процессе работы алгоритма Д,.
Базовый алгоритм А0 for /:=1 to п д =1/2; t:=l; k:=0; s:=0; while(f 0) do for і :=/ to n begin B: ifx=0 then begin t:=i-l; xt:=l/2; break; end ifx,=l then begin x,:=0; go to F; end if дг,-=1/2 then JC,:=1 ; F: = 1,... ): 5:= 5+1; ify=0 then begin k:=k+l; print(&, x); go to B; end ify=2 then go to В; end end if =0 then print (система несовместна); exit; Программная реализация алгоритма А$ приведена в [36], описание алгоритма в [105]. 2.2. Усовершенствованный алгоритм. Усовершенствование базового алгоритма состоит в замене трехзначной логики К2 на 2«+ 1-значную логику L2n+i, в которой переменные и функции определены на множестве 2П+1 {-п, п + \,„,,-1,0,1,— п-1,п}, а операции отрицания, конъюнкции и дизъюнкции имеют вид: х = х, х v у = т\п(х,у) при (х 0) & (у 0) и х v у = тах(х у) в противном случае; х л у = так(х,у) при (х 0) & (у 0) и хлу = т т(х,у) в противном случае. Нулевое значение в 2п+, кодирует ситуацию неопределенности значения переменной или функции в двузначной логике! , множества Ай = {-я,-п + 1,...,-1} и Д =(1,2,..,, и} эквивалентны по смыслу значениям 0 и 1 BLJ .
Введенные в 2 , логические операции замечательны тем, что при определенной тактике означивания переменных модуль значения функции / на наборе х в , равен индексу переменной, значение которой существенным образом определяет значение функции f на этом наборе и в этом смысле представляет ограничение. Расстановка ограничений, вызванных присваиванием ненулевого значения переменнойxk, выполняется в этом случае не сразу для всех переменных xk+l,...,xni а постепенно, и определяется алгоритмом присваивания ненулевых значений переменным булевой функции.
Булевы модели некоторых дискретных задач
Расширение DIMACS формата в ИК РЕБУС. В ИК РЕБУС введено расширение формата DIMACS для представления булевой функции в виде дизъюнктивной нормальной формы: DNF формат. Этот формат имеет синтаксис, полностью совпадающий с форматом CNF, за исключением того, что записи, описывающие дизъюнкты, заменяются на записи, описывающие конъюнкты. В записи размерности задачи после символа р следует значение dnf.
Выходной файл. Этот файл содержит одну или несколько записей, в зависимости от типа алгоритма и решаемой задачи:
Комментарий. Определяется аналогично записи комментария для входного файла.
Записи решения. В начале записи стоит буква s , отделяющаяся пробелом. Поле TYPE определяет тип решения, содержащегося в файле: max для задачи MAX-SAT, cnf для решения задачи выполнимости. Поле SOLUTION содержит целое число, соответствующее значению решения: максимальное число дизъюнктов, Г (если формула выполнима), 0 (если формула невыполнима), -Г (если решение не достигнуто). Поле VARIABLES и поле CLASES содержат те же значения, что и во входном файле в записи размерности модели.
Запись времени. Эта запись не обязательна, но рекомендуется. Она может быть использована для статистической обработки результатов решения. Эта запись может находиться в любом месте выходного файла и имеет следующий формат:
Первые четыре поля имеют тот же смысл, что и для перечисленных выше типов записей. Поле CPUSECS содержит вещественное число — время CPU в секундах, затраченное в процессе решения. Поле MEASURE 1 обязательно (можно указать 0 в случае отсутствия) и принимает значение наиболее существенного критерия оценки выполнения задачи (критерий определяется решателем), такого, например, как число узлов дерева поиска.
Последующие необязательные поля содержат дополнительные оценки выполнения (наличие этих значений и интерпретация зависят от выполняемого приложения). Запись значения переменной. Формат: v V Поле V представляет собой целое число, обозначающее номер переменной. Число положительное, если переменная имеет истинное значение и отрицательное, если значение является ложным. Запись выполнимости дизъюнкта. Формат: s С
Эта запись (только для задачи максимальной выполнимости) обозначает, выполним ли дизъюнкт с номером С. Если 00, то выполним. Если С 0, то невыполним.
В начале этого раздела рассматривается ряд классических задач поиска в области искусственного интеллекта, имеющих много практических приложений. Для одних задач в литературе приводятся соответствующие булевы модели, возможно, несколько отличающиеся от приведенных ниже, для других модель разработана впервые. Далее в разделе приводятся булевы модели для решения двух производственных задач: о равномерной загрузке локомотивного депо при составлении графика ремонта электропоездов, о составлении оперативного плана отправления локомотивных бригад.
Представим множество неизвестных булевых переменных в виде матрицы X = ^хи II размерности пхп.
Будем считать, что хи=\> если на соответствующей клетке шахматной доски установлен ферзь и хи = 0 в противном случае. Постановку задачи об n-ферзях в булевых ограничениях можно записать следующим образом: в каждой строке матрицы X может находиться один и только один элемент, значение которого равно единице. Это ограничение выражается уравнением и-1 п = 0: U UU ^A**vrK в каждом столбце матрицы X может находиться один и только один элемент, значение которого равно единице. Это ограничение выражается уравнением л п-І=І 0; в каждой диагонали шахматной доски (матрицы X) может находиться не более одного элемента, значение которого равно единице.
Концептуальная модель, принципы организации и архитектура инструментального комплекса ребус
С точки зрения программной реализации в ИС РЕБУС можно выделить следующие компоненты: интерфейс пользователя и функциональное наполнение (программы-решатели). Интерфейс пользователя реализован на языке MS Visual Basic [124,125] - быстром и простом средстве для создания эффективных визуальных Windows-приложений, ориентированных на данные.
Язык MS Visual Basic обеспечивает также следующие основные возможности, требуемые для реализации архитектурных особенностей ИК РЕБУС: создание быстрых приложений на уровне препроцессорного кода при использовании общей с MS Visual C++ технологии компиляции. Приложения могут быть оптимизированы по скорости или по размеру, а также по многим другим параметрам; создание интерфейсов с локальными базами данных и базами данных типа клиент/сервер в среде Windows; совместное использование визуальных средств Visual Basic по построению интерфейсов и вычислительных возможностей Фортрана и Си; применение технологии ActiveX, использование средств OLE Automation для использования функций, предоставляемых другими приложениями [129].
Главное окно ИК РЕБУС соответствует стандарту, принятому при разработке Windows-приложений и является диалоговым окном, содержащим меню, панель инструментов, строку состояния. Вид главного окна приведен в приложении 4. Все функциональные возможности комплекса становятся доступными посредством команд меню и кнопок панели инструментов. Каждая подсистема ИК РЕБУС имеет свой интерфейс, реализованный в виде набора диалоговых окон, вид которых приведен также в приложении 4.
Для реализации программ функционального наполнения ИК РЕБУС были использованы языки Си, C++ [127,128] и Фортран [116]. Язык Фортран традиционно используется для решения научно-технических и инженерных задач. Digital Visual Fortran, благодаря специальным возможностям, расширяющим стандарт Фортрана, встал в один ряд с такими языками программирования, как C++, Visual Basic и другие. Преимущества Фортрана - численные расчеты. Язык Visual C++ выбран в качестве второго как наиболее универсальный и легко стыкуемый с MS Fortran язык.
ИК РЕБУС использует платформу Win32c, которая поддерживается 32-х разрядными операционными - системами Windows. Первые версии программ-решателей, работающие в автономном режиме, были 16-ти разрядными и работали в MS DOS. Функциональные возможности шестнадцатиразрядных и тридцатидвухразрядных приложений аналогичны. Windows-приложения позволяют решать системы булевых уравнений большей размерности, т. к. существенно улучшают емкостные характеристики DOS-приложений.
Для создания системной базы знаний ИК РЕБУС использована СУБД клиент/сервер Microsoft SQL Server 2000. Этот выбор обоснован следующими соображениями. СУБД клиент/сервер с полным набором возможностей отличает приложения управления базами данных (сервер или серверные приложения) от отдельных приложений (приложений клиента), с помощью которых выбирается или обновляется информация баз данных. СУБД MS SQL Server функционирует, как служба на компьютере сервера. Ее использование обеспечивает выполнение следующих задач: обеспечение безопасности баз данных, предотвращающей несанкционированный доступ к базе данных и ее данным посторонних лиц; обслуживание каталога объектов базы данных, включая информацию о владельце базы данных и таблицах, которые в ней хранятся; ведение протокола всех изменений базы данных, чтобы можно было восстановить базу данных на основе предыдущей резервной копии и данных, записанных в протокол; управление совместным использованием ресурсов обеспечивает нескольким пользователям доступ к данным без конфликтов и существенных задержек при отображении или обновлении данных. Проблемы одновременного доступа решаются с помощью временных блокировок, налагаемых на отдельные записи, страницы таблицы или на всю таблицу; интерпретация запросов, передаваемых в базу данных, и возвращение или обновление записей, которые удовлетворяют критерию, задаваемому с помощью запроса; выполнение хранимых процедур; сохранение целостности ссылок, контроль непротиворечивости и обеспечение соблюдения предписаний целостности доменов. Для предотвращения выполнения запроса, нарушающего правила, используются триггеры.
