我试图在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).
\==
运算符不是我真正想要的,它会引起这些冲突。 最佳答案
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)