0

我有以下等式：

y(t) = x(t) and not x(t-1)
x, y are boolean variables
t is discrete time

这是一个边缘检测器。我进一步知道

y(0) = 0
y(1) = 0
y(2) = 1
y(3) = 0
y(4) = 0

和初始条件

x(0) = 1
x(4) = 0

我想解方程，以便找到令人满意的值x(1), x(2), x(3)。对于这个例子，我希望解决方案之一是：

x(1) = 0
x(2) = 1
x(3) = 1

我是 Prolog 初学者，但我认为 Prolog 正是可用于解决此类任务的东西。我会将预期的输出和初始条件写成事实：

y(0,0).
y(1,0).
y(2,1).
y(3,0).
y(4,0).
x(0,1).
x(4,0).

和等式 self 作为谓词。如何将方程重写为 Prolog 谓词以及如何查询x？是否有可能获得所有灵魂解决方案？非常感谢每一个想法！最好的祝愿。

阅读第一个答案后

约束中有一个错误（如果我很好地使用了这个术语）。由 激发的方程（系统）x(t)将给出特定的y(t)

x(t):  1 0 1 0 0
y(t):  X 0 1 0 0
  t :  0 1 2 3 4

whereX表示“我们不知道”，因为x(-1)需要知道y(0)计算。

任务是计算x(t)何时t in 1..4已知y(t)。 x(0)并且x(4)可以被要求具有或不具有特定值。这只会影响解决方案的数量，但我认为这对任务的本质并不重要。

对于给定的

y(t):  X 0 1 0 0
  t :  0 1 2 3 4

恕我直言，有两种解决方案：

S1:
x(t):  1 0 1 0 0
y(t):  X 0 1 0 0
  t :  0 1 2 3 4

S2:
x(t):  1 0 1 1 0
y(t):  X 0 1 0 0
  t :  0 1 2 3 4

如果没有初始/最终约束x(t)，至少还有这些解决方案：

S3:
x(t):  1 0 1 1 1
y(t):  X 0 1 0 0
  t :  0 1 2 3 4

S4:
x(t):  0 0 1 0 0
y(t):  X 0 1 0 0
  t :  0 1 2 3 4

S5:
x(t):  0 0 1 1 0
y(t):  X 0 1 0 0
  t :  0 1 2 3 4

S6:
x(t):  0 0 1 1 1
y(t):  X 0 1 0 0
  t :  0 1 2 3 4

即使对于更长的系列和更复杂的方程，我也想解决这个问题，这个例子非常简化。

4

1 回答 1

1

考虑在布尔变量或有限域上使用约束求解器。例如，使用 SWI-Prolog：

:- use_module(library(clpfd)).

edge(Xs, Ys) :-
        Xs = [X0,X1,X2,X3,X4],
        Ys = [_Y0,Y1,Y2,Y3,Y4],
        Xs ins 0..1,
        Ys ins 0..1,
        X0 = 1,
        X4 = 0,
        Ys = [0,0,1,0,0],
        Y1 #= X1 #/\ Y1 #\= X0,
        Y2 #= X2 #/\ Y2 #\= X1,
        Y3 #= X3 #/\ Y3 #\= X2,
        Y4 #= X4 #/\ Y4 #\= X3.

我得到：

?- edge(Xs, Ys).
false.

因此，假设我正确理解并建模了这一点，您的约束不承认解决方案。当我注释掉最后一个约束时，我得到了一个独特的解决方案：

?- edge(Xs, Ys).
Xs = [1, 0, 1, 0, 0],
Ys = [0, 0, 1, 0, 0].

从中可以清楚地看出， noY4​​可以满足这些给定的最终约束Xs，因为它必须既0与0（中的最后两个元素Xs）又不同。label/1当您的答案中仍然存在变量时（上述情况并非如此），您可以使用它来枚举所有具体解决方案。

于 2013-07-24T11:37:37.767 回答