Ограничение удовлетворенности задачами с решателями В. С. Системный поиск

Question

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

Мы изначально начали использовать алгоритмы Constraint Satisfaction Problem (используя Choco ), чтобы попытаться решить его, но поскольку число правил и переменных будет меньше ожидаемого, мы собираемся составить список всех возможных конфигурации в базе данных и использование нескольких запросов на основе правил для фильтрации этого списка и поиска решений таким образом.

Есть ли ограничения или недостатки систематического поиска по сравнению с использованием алгоритмов решателя CSP для разумного количества правил и переменных? Это сильно повлияет на выступления? Это уменьшит ограничения, которые мы можем реализовать?

В качестве примеров :

Вы должны представить это с гораздо большим числом переменных, гораздо большими областями определения (но всегда дискретными) и большим количеством правил (а некоторые гораздо более сложными), но вместо того, чтобы описывать проблему как:

x in (1,6,9)
y in (2,7)
z in (1,6)
y = x + 1
z = x if x < 5 OR z = y if x > 5

И, отдавая его решателю, мы построим таблицу:

X | Y | Z
1   2   1
6   2   1
9   2   1
1   7   1
6   7   1
9   7   1
1   2   6
6   2   6
9   2   6
1   7   6
6   7   6
9   7   6

И использовать такие запросы, как (это просто пример, чтобы помочь понять, на самом деле мы бы использовали SPARQL для семантической базы данных):

SELECT X, Y, Z WHERE Y = X + 1 
INTERSECT 
SELECT X, Y, Z WHERE (Z = X AND X < 5) OR (Z = Y AND X > 5)

Answer 1

CSP позволяет комбинировать детерминистическую генерацию значений (через правила) с эвристическим поиском. Красота происходит, когда вы настраиваете оба из них для вашей проблемы. Правила - это только одна часть. Не менее важным является выбор алгоритма поиска / генератора. Вы можете выбрать лот пространства поиска.

Хотя я не могу прогнозировать производительность вашего SQL-решения, я должен сказать, что оно кажется мне довольно окольным. Одна конкретная проблема произойдет, если ваши правила изменятся - вы можете обнаружить, что вам придется начинать все заново. Кроме того, СУБД будет полностью генерировать все подзапросы, которые могут взорваться.

Я бы предложил реализовать работающий прототип с CSP и один с SQL для простого подмножества ваших требований. Тогда вы получите хорошее чувство, что работает, а что нет. Обязательно подумайте и о долгосрочном обслуживании.

Полный отказ от ответственности: мой последний контакт с CSP был десятилетием назад в университете как часть моей магистерской программы (я реализовал поисковую систему CSP, не похожую на choco, конечно, немного более элементарную, и немного исследовал эту тему). Но область, безусловно, будет развиваться с тех пор.