Составной граф ограничений
Составной граф ограничений представляет собой взвешенный по узлам неориентированный граф, связанный с заданной задачей комбинаторной оптимизации, представленной как задача удовлетворения взвешенных ограничений . Идея составного графа ограничений, разработанная и представленная Сатишом Кумаром Титтамаранахалли (TK Satish Kumar), является большим шагом на пути к объединению различных подходов к использованию «структуры» в задачах удовлетворения взвешенных ограничений. [1] [2]
Задача взвешенного удовлетворения ограничений (WCSP) — это обобщение проблемы удовлетворения ограничений, в которой ограничения больше не являются «жесткими», а расширяются для определения неотрицательных затрат, связанных с кортежами . Цель состоит в том, чтобы найти присвоение значений всем переменным из соответствующих областей так, чтобы общие затраты были минимизированы. Проблемы удовлетворения взвешенных ограничений находят бесчисленное множество применений в искусственном интеллекте и информатике . Их также по-разному называют марковскими случайными полями (в статистике и обработке сигналов ) и минимизации энергии задачами (в физике ).
Хотя проблемы удовлетворения взвешенных ограничений в целом решить NP-трудно , некоторые подклассы можно решить за полиномиальное время , если их взвешенные ограничения демонстрируют определенные виды числовой структуры. Управляемые подклассы также можно определить, анализируя способ наложения ограничений на переменные. В частности, задача удовлетворения взвешенных ограничений может быть решена в экспоненциальной зависимости от времени только в древовидной ширине ее графа взаимодействия переменных (сети ограничений). Однако основным недостатком сети ограничений является то, что она не обеспечивает вычислительную основу для использования числовой структуры взвешенных ограничений.
В отличие от сети ограничений, составной граф ограничений обеспечивает объединяющую структуру для представления как графической структуры взаимодействий переменных, так и числовой структуры взвешенных ограничений. Его можно построить с помощью простой процедуры с полиномиальным временем; и заданная проблема удовлетворения взвешенных ограничений сводится к задаче вычисления минимального взвешенного вершинного покрытия для связанного с ним составного графа ограничений. «Гибридные» вычислительные свойства составного графа ограничений отражены в следующих двух важных результатах:
(Результат 1) Составной граф ограничений данной взвешенной задачи удовлетворения ограничений имеет ту же ширину дерева, что и связанная с ним сеть ограничений.
(Результат 2) Многие подклассы задач удовлетворения взвешенных ограничений, которые разрешимы благодаря числовой структуре их взвешенных ограничений, имеют связанные составные графы ограничений, которые являются двудольными по своей природе.
Результат 1 показывает, что составной граф ограничений можно использовать для захвата графической структуры взаимодействий переменных (поскольку минимальное взвешенное покрытие вершин для любого графа может быть вычислено в экспоненциальном времени только в древовидной ширине этого графа). Результат 2 показывает, что составной граф ограничений также можно использовать для фиксации числовой структуры взвешенных ограничений (поскольку минимальное взвешенное покрытие вершин можно вычислить за полиномиальное время для двудольных графов).
Эмпирически при решении WCSP было показано, что более выгодно применять алгоритмы передачи сообщений и целочисленное линейное программирование к составному графу ограничений WCSP, чем непосредственно к WCSP. [3] [4]
Ссылки
[ редактировать ]- ^ Кумар, ТКС (2008). «Структура гибридной управляемости приводит к проблемам удовлетворения логических взвешенных ограничений» . Материалы четырнадцатой Международной конференции по принципам и практике программирования с ограничениями (CP) . Серия книг «Конспекты лекций по информатике». Том. 5202. стр. 282–297. дои : 10.1007/978-3-540-85958-1_19 . ISBN 978-3-540-85958-1 .
- ^ Кумар, ТКС (2008). «Техники снятия ограничений для задач удовлетворения взвешенных ограничений» (PDF) . Материалы Десятого Международного симпозиума по искусственному интеллекту и математике (ISAIM'2008) .
- ^ Сюй, Хун; Кумар, Т.К. Сатиш; Кениг, Свен (2017). «Сокращение Немхаузера-Троттера и улучшенная передача сообщений для взвешенного CSP». Материалы 14-й Международной конференции по интеграции искусственного интеллекта и методов исследования операций в программировании с ограничениями (CPAIOR) . Серия книг «Конспекты лекций по информатике». Том. 10335. Спрингер. стр. 387–402. дои : 10.1007/978-3-319-59776-8_31 . ISBN 978-3-319-59776-8 .
- ^ Сюй, Хун; Кениг, Свен; Кумар, Т.К. Сатиш (2017). «Комплексное графическое ILP-кодирование логических взвешенных CSP с ограничениями». Материалы 23-й Международной конференции по принципам и практике программирования с ограничениями (CP) . Серия книг «Конспекты лекций по информатике». Том. 10416. Спрингер. стр. 630–8. дои : 10.1007/978-3-319-66158-2_40 . ISBN 978-3-319-66158-2 .