Solution Counting for CSP and SAT with Large Tree-Width
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Solution Counting for CSP and SAT with Large Tree-Width
|
|
| Creator |
Favier, A.
de Givry, S. Jégou, P. |
|
| Subject |
Оптимизационные задачи структурного распознавания образов
|
|
| 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). Запропоновано точний алгоритм, складність якого експоненційно залежить від ширини дерева, і наближений алгоритм, експоненційно залежний від розміру максимальної кліки. |
|
| Date |
2015-06-11T20:00:01Z
2015-06-11T20:00:01Z 2011 |
|
| Type |
Article
|
|
| Identifier |
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 http://dspace.nbuv.gov.ua/handle/123456789/82919 519.157 |
|
| Language |
en
|
|
| Relation |
Управляющие системы и машины
|
|
| Publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
|
|