Сборники трудов ИСП РАН


Теоретические и экспериментальные оценки сложности методов локального распространения в задачах программирования в ограничениях.

В.А. Семенов, О.В. Сидяка.

Аннотация

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

Ключевые слова

CLP-программирование, локальное распространение, теория вычислительной сложности.

Издание

Труды Института системного программирования РАН, том 19, 2010, стр. 117-138.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Полный текст статьи в формате pdf Вернуться к содержанию тома