Методы внешнего оценивания множества решений задачи удовлетворения ограничений

• Автор: Лоенко, Михаил Юрьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Новосибирск
• Количество страниц: 134 с.

Содержание
Введение

1. Вычисление элементарных функций с гарантированной точностью

1.1. Соглашения

1.2. Оценка синуса на интервале 0, .

1.3. Оценка синуса на интервале О.ос

1.4. Оценка косинуса.

1.5. Оценка тангенса.

1.6. Обратные тригонометрические функции.

1.6.1. Оценка арксинуса.

1.6.2. Оценка арккосинуса.

1.6.3. Оценка арктангенса.
1.7. Оценка экспоненты
1.8. Оценка логарифма
1.9. Результаты
2. Алгоритм коррекции решения
2.1. Базовые определения
2.2. Алгоритм М2В
2.3. Применение алгоритма М2В.
2.4. Алгоритм МЗВ.
2.5. Алгоритм коррекции решения.
2.6. Настроечные параметры алгоритма
2.7. Результаты экспериментов.
2.8. Управление алгоритмами сужения.
3. Ньтоновские корректоры
3.1. Граф задачи
3.2. Функциихарактеристики.
3.3. Граф истории.
3.3.1. Вершины графа истории
3.3.2. Создание заготовки графа истории
3.3.3. Эволюция графа истории.
3.3.4. Свойства графа истории.
3.4. Графиндикатор несовместности
3.4.1. Вершинычисла
3.4.2. Вершиныфункции
3.4.3. Корректность графаиндикатора
3.4.4. Предельное значение графаиндикатора.
3.4.5. Теорема о предельном значении графаиндикатора
3.5. Алгоритм ньютоновской коррекции
3.5.1. Теорема о корректности алгоритма.
36. Сравнение алгоритмов и М2В на примере конкретной задачи
3.6.1. Решение задачи М алгоритмом М2В
з
3.6.2. Решение задачи М алгоритмом
3.7. Результаты экспериментов
Заключение
Литература


Ж|, хп удовлетворяют всем ограничениям над Х, хп, существуют значения а-2 ,ап г переменных X2>-,? Xi+i. Для достижения совместности по путям также создано несколько алгоритмов [], однако все они практически не используются, поскольку уступают в эффективности различным суперпозициям алгоритмов поиска и достижения совместности по дугам. Для непрерывных задач также существуют понятия локальной совместности: совместности по границам (2В-, ЗВ-, . Ьох-совместность и другие [, ]. Методы достижения перечисленных и некоторых других видов совместностей называют также методами распространения ограничений [, , , 4G, ]. Такие методы могут оказаться единственным подходом к решению реальных задач, когда применение классических вычислительных методов или методов компьютерной алгебры затруднено наличием неточных данных или частично определенных параметров. Второй класс методов решения CSP содержит различные методы поиска решения. Большинство существующих методов решения конечных CSP принадлежит этому классу. Основным алгоритмом поиска для конечных CSP является бэктрэкинг (backtracking) [, ], известный также как хронологический бэктрэкинг (chronological backtracking). Этот алгоритм состоит в последовательном фиксировании переменных, т. Изначально все переменные неэафиксированны. На каждом шаге выбирается некоторая незафиксированная переменная, после чего ищется ” совместное” значение из области ее возможных значений, т. Если область значений выбранной переменной не содержит совместных значений, то значение, присвоенное при фиксировании предыдущей переменной, признается несовместным, и происходит возврат на предыдущий шаг. В противном случае найденное совместное значение фиксируется, после чего происходит переход к следующему шагу, на котором выбирается и фиксируется следующая переменная. Если все переменные оказались фиксированными - решение найдено. Если все значения первой выбранной переменной оказались несовместными - задача не имеет решений. Удачно сделанный выбор может уменьшить пространство поиска. Существует большое количество модификаций бэктрэкинга. Рассмотрим некоторые из них. Алгоритм ЬасксЬескш? Если при фиксировании некоторой переменной у, значение Ь оказывается несовместным с некоторым значением а фиксированной переменной х, ЬасксЬескй^ запоминает это и не проверяет больше значение 6, пока значением переменной х остается а. Алгоритм backmarking [] является улучшением алгоритма backchecking- Как и backchecking, он уменьшает количество проверь совместности, запоминая, какие значения несовместны с ранее фиксированными переменными. Болес того, он запоминает, какие значения совместны с ранее фиксированными переменными, и тоже их не проверяет. Предположим что на текущем шаге ищется совместное значение для переменной Xj. Предположим также, что некоторое время назад все возможные значения переменной Xj были проверены и найдены несовместными. Предположим, что с тех пор backmarking произвел откат ДО переменной Xi, где і < j, присвоил ей новое значение, после чего нашел совместные значения для переменных j. Xj backmarking не будет рассматривать те значения, которые ’’конфликтуют” с переменными хь. Хі-і, про них уже известно, что они несовместны. Кроме того, backmarking не будет проверять совместность между . Следующий алгоритм - backjumping [] отличается от бэктрэкинга тем, что при необходимости возврата к предыдущему шагу он проводит анализ и возвращается сразу к той переменной, фиксирование которой привело к отсутствию совместных значений на текущем шаге. Алгоритм forward checking [[ при фиксировании каждой переменной удаляет из областей возможных значений нефиксированных переменных значения, несовместные со значениями уже фиксированных переменных. При этом, если область значений некоторой переменной становится пустой, фиксируемое значение признается несовместным. Существуют также алгоритмы, которые после фиксирования каждой переменной вызывают некоторый алгоритм сужения. Такие алгоритмы наряду с forward checking называются lookahead-алгоритмами []. Другой подкласс алгоритмов поиска - стохастические алгоритмы [, , , , ].