Preview

Труды Института системного программирования РАН

Расширенный поиск

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

Аннотация

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

Об авторах

В. А. Семенов
ИСП РАН
Россия


О. В. Сидяка
ИСП РАН
Россия


Список литературы

1. Dechter R. Constraint processing. Morgan Kaufmann, San Francisco, 2003.

2. E. Tsang. Foundations of constraint satisfaction. Academic Press Limited, London & San-Diego, 1993.

3. K. Bharat. Supporting the Construction of Distributed, Interoperative, User Interface Applications. Ph.D. Dissertation, Georgia Institute of Technology, 1996.

4. R.D. Hill. The Abstraction-Link-View Paradigm: Using Constraints to Connect User Interfaces to Applications. Proceedings of SIGCHI '92. 1992, pp. 335-342.

5. Joao Pascoal Faria, Raul Moreira Vidal. 1999. Data-driven Active Rules for the Maintenance of Derived Data and Integrity Constraints in User Interfaces to Databases

6. C. M. Hoffman, A. Lomonosov. Decomposition plans for geometric constraint systems. // J. Symbolic Computation. Volume 31. 2001. pp. 367-408.

7. W. Bouma, I. Fudos, C. Hoffmann, J. Cai, R. Paige. A Geometric Constraint Solver. 1995.

8. A. Borning, K. Marriott, P. Stuckey, Y. Xiao. Solving Linear Arithmetic Constraints for User Interface Applications: Algorithm Details. Technical Report 97-06-01, Department of Computer Science and Engineering University of Washington, 1997

9. M. Chetty, K.P. Dabke. Symbolic computations: an overview and application to controller design. // Proceedings of IEEE sponsored international conference on Information, Decision and Control, Adelaide, 8th-10th February, 1999, pp.451–456.

10. I. Fudos. Editable Representations For 2D Geometric Design. 1993

11. B. V. Zanden, An incremental algorithm for satisfying hierarchies of multiway dataflow constraints. // ACM Transactions on Programming Languages and Systems. Volume 18, Issue 1. 1996. 30-72.

12. A. Borning, R. Anderson, B. Freeman-Benson. Indigo: A Local Propagation Algorithm for Inequality Constraints. // In Proceedings of the 1996 ACM Symposium on User Interface Software and Technology, 1996, pp. 129-136.

13. M. Sannella. Skyblue: a multi-way local propagation constraint solver for user interface construction. // Proceedings of the 7th annual ACM symposium on User interface software and technology, 1994, pp. 137-146.

14. J. H. Maloney. Using Constraints for User Interface Construction. Doctoral Thesis. University of Washington. 1992

15. D. Frigioni, A. Marchetti-Spaccamela, U. Nanni. Dynamic algorithms for classes of constraint satisfaction problems. Theor. Comput. Sci. 259, 1-2 (May. 2001), 2001. pp. 287-305.


Рецензия

Для цитирования:


Семенов В.А., Сидяка О.В. Теоретические и экспериментальные оценки сложности методов локального распространения в задачах программирования в ограничениях. Труды Института системного программирования РАН. 2010;19.

For citation:


Semenov V.A., Sidyaka O.V. Theoretical and practical complexity estimates for local propagation methods in constraint-based programming applications. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2010;19. (In Russ.)



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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