Я пытаюсь решить частный случай общей проблемы удовлетворения ограничений в Java.
В основном у меня есть несколько переменных, каждая из которых принимает дискретные значения, и каждая переменная определяется набором всех возможныхзначения, которые он имеет (подумайте об этом, как о перечислении в Java, это помогло бы).
У меня также есть несколько групп условий (представьте себе условие как систему из нескольких уравнений для переменных, и все ониУнарные ограничения: другими словами, форма переменная = возможное значение), цель состоит в том, чтобы найти, есть ли набор значений переменных, который удовлетворяет хотя бы одному условию из каждой группы (он может удовлетворять нескольким из одной и той же группы).Я назову этот конкретный набор решений.То, что я ищу, - это все возможные решения.
Единственная идея, которая у меня есть до сих пор, это в основном грубая сила.
Это конкретный пример, так что все яснее:
s = {a,b,c}, v = {1,2,3}, n = {p,k,m}. - Первая группа условий:
c1 = {s=a and v=2}, c2 = {s=b}. - Вторая группа условий:
c1={n=p and v=2}. - Третья группа условий:
c1={s=a and n=p}, c2 = {s=c}.
В этой ситуации, если мы примем (s=a,v=2,n=p): она удовлетворяет первому условию из всехтри группы, и, следовательно, является решением проблемы.
(s=b,v=2,n=p) однако не является решением, поскольку оно не проверяет ни одно из условий третьей группы.На самом деле количество возможных решений здесь равно 1.
Обратите внимание, что условия внутри группы не обязательно являются взаимоисключающими.
Любое понимание возможного пути повышения эффективности, чем путемгрубая сила, будь то структура данных или алгоритм, была бы великолепна, поскольку мне пришлось бы решать миллионы таких систем с достаточным количеством переменных (тридцать переменных вершин, каждая из которых имеет около 15 значений, и сотни таких условий).
Edit1: ограничения данных Если N - это число переменных, которое будет иметь каждая проблема, тогда N<=30.
Если |V| - максимальное количество элементовпеременная V может иметь, тогда я знаю, что Max(|Vi|)<=15 для каждой переменной Vi в проблеме.
Я также знаю, что если C - это число ограничений на проблему, то C<100.
Наконец, я знаю, что, по статистике, количество решений проблемы будет небольшим, а это означает, что большинство проблем будет иметь одно решение.п, и вероятность наличия более 8 решений составляет менее 99% времени.Ради оптимизации мы можем даже предположить, что меня никогда не интересовала какая-либо проблема, которая когда-либо имела бы более 10 решений.