It's OK!
Подход в принципе нормальный, и лично я считаю Пролог хорошим выбором для таких задач.
Однако есть несколько тонкостей, которые необходимо решить.
Во-первых, давайте правильно разработаем синтаксис CLP(R):
vector([X1,X2,X3,X4,X5,X6,X7]) :-
{ X1 > X2 + X3 + X4,
X5 =< sin(X6 + X7) }.
Обратите особое внимание на использование =<
, а также на правильное использование {}/1
для обозначения ограничений CLP(R). Маркер <=
избегается в арифметике Пролога, потому что он выглядит как стрелка, которая обычно обозначает импликацию в доказывающих.
Этого достаточно, чтобы получить первые ответы, даже если они еще не преобразованы в конкретные решения:
?- vector(Ls).
Ls = [_1028, _1034, _1040, _1046, _1052, _1058, _1064],
{_1046=_1028-_1034-_1040-_1088, _1088>0.0},
{_1052-sin(_1058+_1064)=<0.0},
{_1052-sin(_1058+_1064)=<0.0},
{_1052-sin(_1058+_1064)=<0.0}.
Используя random/1
, мы можем присвоить случайные числа с плавающей запятой из (0,1) любой из переменных. Например:
?- vector([A,B,C,D,E,F,G]),
random(A),
random(B).
A = 0.33797712696696053,
B = 0.7039688010209147,
{D= -0.3659916740539542-C-_894, _894>0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0}.
Это решает одну часть задачи. Однако этот метод подводит нас в таких случаях, как:
?- vector([A,B,C,D,E,F,G]),
random(A),
random(B),
random(C),
random(D).
false.
Здесь (детерминированная!) генерация случайных чисел конфликтует с ограничениями. Есть несколько способов обойти это. Прежде чем я покажу их, давайте ограничим переменные нужным интервалом, используя, например, следующее определение:
zero_to_one(X) :- { 0 =< X, X =< 1 }.
Мы можем просто указать это ограничение как одно дополнительное требование:
?- vector([A,B,C,D,E,F,G]),
maplist(zero_to_one, [A,B,C,D,E,F,G]),
random(A),
random(B),
random(C).
Это снова дает false
.
Способ 1: Больше того же
Один из способов решить описанную выше проблему — просто повторять рандомизированное назначение до тех пор, пока не будет найдено решение при возврате:
?- vector([A,B,C,D,E,F,G]),
maplist(zero_to_one, [A,B,C,D,E,F,G]),
random(A),
random(B),
repeat,
random(C).
A = 0.9433451780634803,
B = 0.15859272177823736,
C = 0.706502025956454,
{D>=0.0, _2064=0.07825043032878898-D, D<0.07825043032878898},
{E>=0.0, E=<1.0, F>=0.0, F==0.0, G=<1.0, E-sin(...)=<0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0} .
Таким образом, мы на шаг ближе к конкретному решению, под которым мы подразумеваем полную реализацию вектора. Недостатки довольно очевидны: в крайних случаях мы никогда не найдем правильное присваивание таким образом. Если повезет, может потребоваться много попыток найти конкретное значение даже для одной дополнительной переменной.
Способ 2: максимизировать или минимизировать
Другой способ решить эту проблему — использовать maximize/1
и/или minimize/1
из CLP(R), чтобы использовать сам решатель ограничений для получения конкретных решений. Это работает только для линейных ограничений, и даже не для всех из них. Например, рассмотрим следующие запросы:
?- { X = sin(Y) },
maplist(zero_to_one, [X,Y]),
maximize(X).
false.
И даже:
?- { X < 1 }, maximize(X).
false.
Хотя в отличие:
?- { X =< 1 }, maximize(X).
X = 1.0 .
Теперь давайте воспользуемся следующим трюком, чтобы избавиться от всех нелинейных ограничений: мы просто назначаем случайные числа с плавающей запятой для X6
и X7
, используя, например:
?- vector(Ls),
Ls = [A,B,C,D,E,F,G],
maplist(zero_to_one, Ls),
random(F), random(G).
Опираясь на это, мы можем написать:
?- vector(Ls),
Ls = [A,B,C,D,E,F,G],
maplist(zero_to_one, Ls),
random(F), random(G),
maximize(A), minimize(B+C+D+E).
Ls = [1.0, 0.0, 0.0, 0.0, 0.0, 0.9702069686491169, 0.13220925936558517],
A = 1.0,
B = C, C = D, D = E, E = 0.0,
F = 0.9702069686491169,
G = 0.13220925936558517 .
Таким образом, мы получили конкретное решение, удовлетворяющее всем ограничениям и имеющее некоторые случайные составляющие.
Заключительные замечания
Во-первых, повторюсь, я думаю, что Prolog — хороший выбор для таких задач. Сокращение с помощью решателя ограничений может помочь устранить большие части пространства поиска, а сам решатель ограничений может помочь вам получить конкретные решения путем минимизации и максимизации. Во-вторых, есть еще несколько вопросов, о которых вам нужно помнить:
- Во-первых, решения, сгенерированные таким образом (любым методом), не являются случайными в том смысле, что каждое решение равновероятно. Скорее, могут быть кластеры решений, которые могут появиться с большей вероятностью, чем другие.
- Как показано выше, уравнения могут потребовать некоторых дополнительных рассуждений и экспериментов, как для сведения их к линейным уравнениям, так и для применения подходящего направления оптимизации. Пролог хорошо подходит для таких рассуждений, и вы можете легко использовать его для опробования различных стратегий.
- Возможно, вам придется найти рабочий компромисс между рандомизацией и детерминированной оптимизацией для создания экземпляров оставшихся векторных компонентов. Компромисс может также зависеть от запутанности компонентов вектора.
Наконец, очень важное замечание: неявные случайные состояния идут вразрез со свойствами, которые мы ожидаем от логических отношений, поскольку они могут привести к тому, что ваши предикаты будут вести себя совершенно по-разному при последующих вызовах, превращая отладку и систематическое тестирование в кошмар. Поэтому я настоятельно рекомендую вам предусмотреть случайное начальное число или использовать в коде явное состояние генератора случайных чисел. Это поможет вам лучше понять поведение вашей программы и сделать ее полностью детерминированной. Позже вы можете изменить начальное значение для создания различных наборов решений.
person
mat
schedule
08.05.2017