reference - Prolog比较变量的方法

Question

我试图在 Prolog 中实现一些图形算法。我想出了一个想法，使用统一从图结构构建树:

图表定义如下:

• Vertex-Variable 对列表，其中 Vertex 是表示顶点的常量，Variable 是相应的变量，即将用作顶点的“引用”。例如:

  [a-A, b-B, c-C, d-D]

• VertexVar-NeighboursList 对列表，其中 VertexVar 和 NeighboursList 中的各个邻居是“引用变量”。例如:

  [A-[B, C, D], B-[A, C], C-[A, B], D-[A]] 意思是 b, c, d 是a 等的邻居

然后在可以使用从原始图构建的某种树的某些图算法(例如搜索组件，或简单的 DFS/BFS 等)之前，可以使用一些谓词，例如 unify_neighbours将 VertexVar-NeighbourList 对统一为 VertexVar = NeighboursList。之后，顶点变量可能被解释为它的邻居列表，其中每个邻居又是其邻居的列表。

所以这会在遍历图形时产生良好的性能，因为不需要为图形中的每个顶点线性搜索某个顶点及其邻居。

但我的问题是:如何比较那些顶点变量？ (检查它们是否相同。)我尝试使用 A == B，但存在一些冲突。对于上面的示例，(使用 unify_neighbours 谓词)Prolog 在内部将图形解释为:

[a-[S_1, S_2, S_3], b-S_1, c-S_2, d-S_3]

哪里:

S_1 = [[S_1, S_2, S_3], S_2]
S_2 = [[S_1, S_2, S_3], S_1]
S_3 = [[S_1, S_2, S_3]]

问题出在 S_1 和 S_2(又名 b 和 c)，因为 X = [something, Y], Y = [something, X], X == Y 为 true。共享相同邻居的顶点也会出现同样的问题。例如U-[A, B] 和 V-[A, B]。

所以我的问题是:有没有其他比较变量的方法可以帮助我解决这个问题？比较“变量本身”而不是内容的东西，比如比较过程编程语言中的地址？或者这会不会过于程序化并破坏 Prolog 的声明性思想？

例子

graph_component(Vertices, Neighbours, C) :-
    % Vertices and Neighbours as explained above.
    % C is some component found in the graph.
    vertices_refs(Vertices, Refs),
    % Refs are only the variables from the pairs.
    unify_neighbours(Neighbours), % As explained above.
    rec_(Vertices, Refs, [], C).

rec_(Vertices, Refs, Found, RFound) :-
    % Vertices as before.
    % Refs is a stack of the vertex variables to search.
    % Found are the vertices found so far.
    % RFound is the resulting component found.
    [Ref|RRest] = Refs,
    vertices_pair(Vertices, Vertex-Ref),
    % Vertex is the corresponding Vertex for the Ref variable
    not(member(Vertex, Found)),
    % Go deep:
    rec_(Vertices, Ref, [Vertex|Found], DFound),
    list_revpush_result([Vertex|Found], DFound, Found1),
    % Go wide:
    rec_(Vertices, RRest, Found1, RFound).

rec_(Vertices, Refs, Found, []) :-
    % End of reccursion.
    [Ref|_] = Refs,
    vertices_pair(Vertices, Vertex-Ref),
    member(Vertex, Found).

这个例子并没有真正起作用，但它是这个想法。 (此外，检查是否找到顶点是线性完成的，因此性能仍然不佳，但这只是为了演示。)现在为变量找到相应顶点的谓词实现为:

vertices_pair([Vertex-Ref|_], Vertex-Ref).
vertices_pair([_-OtherRef|Rest], Vertex-Ref) :-
    Ref \== OtherRef,
    vertices_pair(Rest, Vertex-Ref).

\== 运算符并不是我真正想要的，它会造成这些冲突。

Answer 1

Prolog 的一个内在特征是，一旦将变量绑定(bind)到项，它就与项本身无法区分。换句话说，如果将两个变量绑定(bind)到同一个术语，则您有两个相同的东西，并且无法区分它们。

应用于您的示例:一旦您将每个顶点变量与相应的邻居列表统一起来，所有变量都将消失:您只剩下一个嵌套的(很可能是循环的)数据结构，由一个列表组成列表列表...

但是正如您所建议的，嵌套结构是一个有吸引力的想法，因为它使您可以直接访问相邻节点。尽管 Prolog 系统在支持循环数据结构方面有所不同，但这并不妨碍您利用这个想法。

您的设计的唯一问题是节点完全由(可能是深度嵌套和循环的)数据结构标识，该数据结构描述了从它可以到达的子图。结果是

• 具有相同后代的两个节点是不可区分的
• 检查两个“看起来相似”的子图是否相同可能会非常昂贵

一个简单的解决方法是在您的数据结构中包含一个唯一节点标识符(例如名称或编号)。要使用您的示例(稍作修改以使其更有趣):

make_graph(Graph) :-
    Graph = [A,B,C,D],
    A = node(a, [C,D]),
    B = node(b, [A,C]),
    C = node(c, [A,B]),
    D = node(d, [A]).

然后您可以使用该标识符来检查匹配的节点，例如在深度优先遍历中:

dfs_visit_nodes([], Seen, Seen).
dfs_visit_nodes([node(Id,Children)|Nodes], Seen1, Seen) :-
    ( member(Id, Seen1) ->
        Seen2 = Seen1
    ;
        writeln(visiting(Id)),
        dfs_visit_nodes(Children, [Id|Seen1], Seen2)
    ),
    dfs_visit_nodes(Nodes, Seen2, Seen).

样本运行:

?- make_graph(G), dfs_visit_nodes(G, [], Seen).
visiting(a)
visiting(c)
visiting(b)
visiting(d)

G = [...]
Seen = [d, b, c, a]
Yes (0.00s cpu)