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

该图将定义如下:

  • 一对Vertex-Variable对的列表,其中Vertex是代表顶点的常量,而Variable是对应的变量,将用作对顶点的“引用”。例如。:
    [a-A, b-B, c-C, d-D]
  • 一对VertexVar-NeighboursList对,其中VertexVarNeighboursList中的各个邻居是“参考变量”。例如。:
    [A-[B, C, D], B-[A, C], C-[A, B], D-[A]]的含义bcda等的邻居。

  • 然后,在某些可以使用从原始图中构建的树的图算法(例如搜索组件或简单的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_1S_2(又名bc),因为X = [something, Y], Y = [something, X], X == Ytrue。共享相同邻居的顶点也会遇到同样的问题。例如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)
    

  • 09-11 18:55
    查看更多