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和cX = [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).

在这里，\== 操作符并不是我想要的，它会创建一些冲突。

- egst

---

我不完全理解你的想法...也许你忽略了变量是局部于子句的这一点？ - CapelliC

我会添加一个例子。 - egst

提供给顶点的变量在处理图搜索的子句内是局部的。 - egst

Answer 1

Prolog有一个内在的特性，即一旦你将变量绑定到一个项上，它就与项本身无法区分。换句话说，如果你将两个变量绑定到相同的项上，那么你就有了两个相同的事物，并且没有办法区分它们。

应用于你的例子：一旦你将每个顶点变量与相应的邻居列表统一，所有变量都消失了：你只剩下一个嵌套的（很可能是循环的）数据结构，由列表、列表的列表等组成...

但正如你所建议的那样，嵌套结构是一个吸引人的想法，因为它直接给你访问相邻节点的方式。虽然不同的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)

- jschimpf

Answer 2

感谢 @jschimpf 的回答。它为我澄清了很多事情。我刚刚回到一些 Prolog 图问题，并想再次尝试这个递归数据结构，于是我想出了以下谓词来从边的列表构建此数据结构：

如 @jschimpf 所建议的，手动创建数据结构：

my_graph(Nodes) :-
    Vars  = [A, B, C, D, E],
    Nodes = [
        node(a, [edgeTo(1, B), edgeTo(5, D)]),
        node(b, [edgeTo(1, A), edgeTo(4, E), edgeTo(2, C)]),
        node(c, [edgeTo(2, B), edgeTo(6, F)]),
        node(d, [edgeTo(5, A), edgeTo(3, E)]),
        node(e, [edgeTo(3, D), edgeTo(4, B), edgeTo(1, F)]),
        node(e, [edgeTo(1, E), edgeTo(6, C)])
    ],
    Vars = Nodes.

edgeTo(Weight, VertexVar) 表示到某个顶点的边，其中 Weight 是权重，可以自定义为任何其他信息。 node(Vertex, [edgeTo(Weight, VertexVar), ...]) 表示一个带有邻居的顶点。

更加“用户友好”的输入格式：

[edge(Weight, FromVertex, ToVertex), ...]

带有可选的顶点列表：

[Vertex, ...]

对于上面的例子：

[edge(1, a, b), edge(5, a, d), edge(2, b, c), edge(4, b, e), edge(6, c, f), edge(3, d, e), edge(1, e, f)]

可以使用以下谓词将此列表转换为递归数据结构：

% make_directed_graph(+Edges, -Nodes)
make_directed_graph(Edges, Nodes) :-
    vertices(Edges, Vertices),
    vars(Vertices, Vars),
    pairs(Vertices, Vars, Pairs),
    nodes(Pairs, Edges, Nodes),
    Vars = Nodes.

% make_graph(+Edges, -Nodes)
make_graph(Edges, Nodes) :-
    vertices(Edges, Vertices),
    vars(Vertices, Vars),
    pairs(Vertices, Vars, Pairs),
    directed(Edges, DiretedEdges),
    nodes(Pairs, DiretedEdges, Nodes),
    Vars = Nodes.

% make_graph(+Edges, -Nodes)
make_graph(Edges, Nodes) :-
    vertices(Edges, Vertices),
    vars(Vertices, Vars),
    pairs(Vertices, Vars, Pairs),
    directed(Edges, DiretedEdges),
    nodes(Pairs, DiretedEdges, Nodes),
    Vars = Nodes.

% make_directed_graph(+Vertices, +Edges, -Nodes)
make_directed_graph(Vertices, Edges, Nodes) :-
    vars(Vertices, Vars),
    pairs(Vertices, Vars, Pairs),
    nodes(Pairs, Edges, Nodes),
    Vars = Nodes.

这些谓词的二元版本假设每个顶点仅可以从边列表中获得，图中没有“无边”顶点。三元版本则为这些情况提供了额外的顶点列表。 make_directed_graph 假设输入的边是有向的，make_graph 则假设它们是无向的，因此创建相反方向的额外有向边。

% directed(+UndirectedEdges, -DiretedEdges)
directed([], []).
directed([edge(W, A, B)|UndirectedRest], [edge(W, A, B), edge(W, B, A)|DirectedRest]) :-
    directed(UndirectedRest, DirectedRest).

从边的列表中获取所有的顶点：

% vertices(+Edges, -Vertices)
vertices([], []).
vertices([edge(_, A, B)|EdgesRest], [A, B|VerticesRest]) :-
    vertices(EdgesRest, VerticesRest),
    \+ member(A, VerticesRest),
    \+ member(B, VerticesRest).
vertices([edge(_, A, B)|EdgesRest], [A|VerticesRest]) :-
    vertices(EdgesRest, VerticesRest),
    \+ member(A, VerticesRest),
    member(B, VerticesRest).
vertices([edge(_, A, B)|EdgesRest], [B|VerticesRest]) :-
    vertices(EdgesRest, VerticesRest),
    member(A, VerticesRest),
    \+ member(B, VerticesRest).
vertices([edge(_, A, B)|EdgesRest], VerticesRest) :-
    vertices(EdgesRest, VerticesRest),
    member(A, VerticesRest),
    member(B, VerticesRest).

为每个顶点构建未初始化的变量：

% vars(+List, -Vars)
vars([], []).
vars([_|ListRest], [_|VarsRest]) :-
    vars(ListRest, VarsRest).

将顶点和顶点变量配对：

% pairs(+ListA, +ListB, -Pairs)
pairs([], [], []).
pairs([AFirst|ARest], [BFirst|BRest], [AFirst-BFirst|PairsRest]) :-
    pairs(ARest, BRest, PairsRest).

构建递归节点：

% nodes(+Pairs, +Edges, -Nodes)
nodes(Pairs, [], Nodes) :-
    init_nodes(Pairs, Nodes).
nodes(Pairs, [EdgesFirst|EdgesRest], Nodes) :-
    nodes(Pairs, EdgesRest, Nodes0),
    insert_edge(Pairs, EdgesFirst, Nodes0, Nodes).

首先，为每个顶点初始化一个空节点列表：

% init_nodes(+Pairs, -EmptyNodes)
init_nodes([], []).
init_nodes([Vertex-_|PairsRest], [node(Vertex, [])|NodesRest]) :-
    init_nodes(PairsRest, NodesRest).

然后边逐一插入：

% insert_edge(+Pairs, +Edge, +Nodes, -ResultingNodes)
insert_edge(Pairs, edge(W, A, B), [], [node(A, [edgeTo(W, BVar)])]) :-
    vertex_var(Pairs, B, BVar).
insert_edge(Pairs, edge(W, A, B), [node(A, EdgesTo)|NodesRest], [node(A, [edgeTo(W, BVar)|EdgesTo])|NodesRest]) :-
    vertex_var(Pairs, B, BVar).
insert_edge(Pairs, edge(W, A, B), [node(X, EdgesTo)|NodesRest], [node(X, EdgesTo)|ResultingNodes]) :-
    A \= X,
    insert_edge(Pairs, edge(W, A, B), NodesRest, ResultingNodes).

获取给定顶点的顶点变量：（实际上可以双向工作。）

% vertex_var(+Pairs, +Vertex, -Var)
vertex_var(Pairs, Vertex, Var) :-
    member(Vertex-Var, Pairs).
```Prolog

This, of course, brings additional time overhead, but you can do this once and then just copy this data structure every time you need to perform some graph algorithm on it and access neighbours in constant time.

You can also add additional information to the `node` predicate. For example:

```Prolog
node(Vertex, Neighbours, OrderingVar)

在图的部分排序中，可以使用有关顶点位置的信息将未初始化的变量OrderingVar“分配”（初始化）为常数时间。因此，这可以用作输出。（有时在Prolog注释中用+-表示 - 未初始化的变量作为输入项的一部分，由使用的谓词初始化并提供输出。）

- egst