Форма пошуку Назад
укр рус eng
 Cписок

Фавьер А., де Живри С, Жегу Ф.
Подсчет количества решений залач CSP и SAT на деревьях большой ширины

Вид документа: Стаття періодики
Автор: Фавьер А., де Живри С, Жегу Ф. Вид автора: персона
Мова: Російська Обсяг: С. 4-13, 70
УДК: 519.157

Аннотацiя:Рассмотрена проблема подсчета количества решений залами совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность котрого экспоненниально зависит от ширины дерева, и приближенный алгоритм, экспоненциально зависящий от размера максимальной клики. Ключевые слова: подсчет решений, задача совместимости ограничений, динамическое программирование, приближенный подсчет. хордальный граф, раскраска графа.

Є складовою частиною документа: Управляющие системы и машины

Відомості щодо головного
 Назва головного документа:Управляющие системы и машины
 Дата видання головного документа:2011
 Номер частини головного документа:2

Загальна інформація
 Бібліографія:36 назв.

Теми документа: