Solution Counting for CSP and SAT with Large Tree-Width
Рассмотрена проблема подсчета количества решений задачи совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2011 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/82919 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Solution Counting for CSP and SAT with Large Tree-Width / A. Favier, S. de Givry, Ph. Jégou // Управляющие системы и машины. — 2011. — № 2. — С. 4-13, 70. — Бібліогр.: 36 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-82919 |
|---|---|
| record_format |
dspace |
| spelling |
Favier, A. de Givry, S. Jégou, P. 2015-06-11T20:00:01Z 2015-06-11T20:00:01Z 2011 Solution Counting for CSP and SAT with Large Tree-Width / A. Favier, S. de Givry, Ph. Jégou // Управляющие системы и машины. — 2011. — № 2. — С. 4-13, 70. — Бібліогр.: 36 назв. — англ. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82919 519.157 Рассмотрена проблема подсчета количества решений задачи совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность которого экспоненциально зависит от ширины дерева, и приближенный алгоритм, экспоненциально зависящий от размера максимальной клики. The problem of counting the number of solutions of a CSP is considered. For solving the problem the Backtracking with a Tree-Decomposition method was adapted. The exact algorithm is suggested which has the worst-time complexity exponential in a tree width, as well as iterative algorithm that has computational complexity exponential in a maximum clique size. Розглянуто проблему підрахунку кількості розв’язків задачі сумісності обмежень (Constraint Satisfaction Problem). Для її розв’язку було адаптовано метод зворотного простеження з ациклічним поданням графа обмежень (Backtracking with Tree-Decomposition). Запропоновано точний алгоритм, складність якого експоненційно залежить від ширини дерева, і наближений алгоритм, експоненційно залежний від розміру максимальної кліки. en Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Оптимизационные задачи структурного распознавания образов Solution Counting for CSP and SAT with Large Tree-Width Подсчет количества решений задач CSP и SAT на деревьях большой ширины Підрахунок кількості розв’язків задач CSP та SAT на деревах великої ширини Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Solution Counting for CSP and SAT with Large Tree-Width |
| spellingShingle |
Solution Counting for CSP and SAT with Large Tree-Width Favier, A. de Givry, S. Jégou, P. Оптимизационные задачи структурного распознавания образов |
| title_short |
Solution Counting for CSP and SAT with Large Tree-Width |
| title_full |
Solution Counting for CSP and SAT with Large Tree-Width |
| title_fullStr |
Solution Counting for CSP and SAT with Large Tree-Width |
| title_full_unstemmed |
Solution Counting for CSP and SAT with Large Tree-Width |
| title_sort |
solution counting for csp and sat with large tree-width |
| author |
Favier, A. de Givry, S. Jégou, P. |
| author_facet |
Favier, A. de Givry, S. Jégou, P. |
| topic |
Оптимизационные задачи структурного распознавания образов |
| topic_facet |
Оптимизационные задачи структурного распознавания образов |
| publishDate |
2011 |
| language |
English |
| container_title |
Управляющие системы и машины |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| format |
Article |
| title_alt |
Подсчет количества решений задач CSP и SAT на деревьях большой ширины Підрахунок кількості розв’язків задач CSP та SAT на деревах великої ширини |
| description |
Рассмотрена проблема подсчета количества решений задачи совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность которого экспоненциально зависит от ширины дерева, и приближенный алгоритм, экспоненциально зависящий от размера максимальной клики.
The problem of counting the number of solutions of a CSP is considered. For solving the problem the Backtracking with a Tree-Decomposition method was adapted. The exact algorithm is suggested which has the worst-time complexity exponential in a tree width, as well as iterative algorithm that has computational complexity exponential in a maximum clique size.
Розглянуто проблему підрахунку кількості розв’язків задачі сумісності обмежень (Constraint Satisfaction Problem). Для її розв’язку було адаптовано метод зворотного простеження з ациклічним поданням графа обмежень (Backtracking with Tree-Decomposition). Запропоновано точний алгоритм, складність якого експоненційно залежить від ширини дерева, і наближений алгоритм, експоненційно залежний від розміру максимальної кліки.
|
| issn |
0130-5395 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/82919 |
| citation_txt |
Solution Counting for CSP and SAT with Large Tree-Width / A. Favier, S. de Givry, Ph. Jégou // Управляющие системы и машины. — 2011. — № 2. — С. 4-13, 70. — Бібліогр.: 36 назв. — англ. |
| work_keys_str_mv |
AT faviera solutioncountingforcspandsatwithlargetreewidth AT degivrys solutioncountingforcspandsatwithlargetreewidth AT jegoup solutioncountingforcspandsatwithlargetreewidth AT faviera podsčetkoličestvarešeniizadačcspisatnaderevʹâhbolʹšoiširiny AT degivrys podsčetkoličestvarešeniizadačcspisatnaderevʹâhbolʹšoiširiny AT jegoup podsčetkoličestvarešeniizadačcspisatnaderevʹâhbolʹšoiširiny AT faviera pídrahunokkílʹkostírozvâzkívzadačcsptasatnaderevahvelikoíširini AT degivrys pídrahunokkílʹkostírozvâzkívzadačcsptasatnaderevahvelikoíširini AT jegoup pídrahunokkílʹkostírozvâzkívzadačcsptasatnaderevahvelikoíširini |
| first_indexed |
2025-12-07T13:13:54Z |
| last_indexed |
2025-12-07T13:13:54Z |
| _version_ |
1850855374893088768 |