1

优化 Datalog 程序的一个经典技巧是对称破坏。对称性破坏可以将您必须在数据库中计算的事实数量减半，因为您只需要计算edge(0, 1)而不需要同时计算edge(1, 0).

考虑一个 nxm 坐标网格。如果我们想在这个网格上写一个描述无向边的关系，一个打破对称性的简单方法是说边只从较小的坐标到较大的坐标（例如，(2, 3)到(3, 3)，但反之不行）。这是一个简单的 cligo 程序，它以这种方式对 2x2 网格进行建模：

row(0..1).
col(0..1).
node(n(I, J)) :- row(I), col(J).
delta(0,1).
delta(1,0).
edge(e(N1, N2)) :-
    node(N1), node(N2),
    N1 = n(I1, J1),
    N2 = n(I2, J2),
    delta(I2-I1, J2-J1).

#show edge/1.

我们可以看到，如果对称性没有被破坏，这会产生四个关于边缘的事实，而不是八个：

edge(e(n(0,0),n(0,1)))
edge(e(n(1,0),n(1,1)))
edge(e(n(0,0),n(1,0)))
edge(e(n(0,1),n(1,1)))

现在考虑由这个坐标网格引起的折线图。这个折线图也是无向的，我们想以类似的方式打破对称性。什么是打破该图对称性的紧凑方法？

作为参考，这里是折线图上边的简短定义，它不会破坏对称性。

ledge(l(E1, E2)) :-
    edge(E1), edge(E2),
    E1 = e(N1, N2),
    E2 = e(N1, N3; N3, N1; N3, N2; N2, N3),
    N3 != N1, N2 != N1.

#show ledge/1.

我们可以看到它不会破坏对称性，因为它会生成以下两个事实（以及其他事实）：

ledge(l(e(n(0,0),n(1,0)),e(n(1,0),n(1,1))))
ledge(l(e(n(1,0),n(1,1)),e(n(0,0),n(1,0))))
4

1 回答 1

2

要打破对称性，在元素上定义一些总顺序就足够了，所以你可以简单地说 p(A, B) 只有当 A < B 时。Clingo 定义了所有元素的字典顺序，所以解决方案实际上很简单作为：

ledge(l(E1, E2)) :-
    edge(E1), edge(E2),
    E1 < E2,
    E1 = e(N1, N2),
    E2 = e(N1, N3; N3, N1; N3, N2; N2, N3),
    N3 != N1, N2 != N1.

给予

ledge(l(e(n(0,0),n(1,0)),e(n(1,0),n(1,1))))
ledge(l(e(n(0,0),n(0,1)),e(n(0,1),n(1,1))))
ledge(l(e(n(0,1),n(1,1)),e(n(1,0),n(1,1))))
ledge(l(e(n(0,0),n(0,1)),e(n(0,0),n(1,0))))

如预期的。不过，可能还有其他优化的机会！

于 2020-11-26T22:47:06.540 回答