gpt4 book ai didi

Prolog 同构图

转载 作者:行者123 更新时间:2023-12-01 00:52:02 24 4
gpt4 key购买 nike

试图在这里解决同构图问题。

任务信息:

  • 确定 2 个无向图是否同构。
  • 没有孤立的顶点。
  • 顶点数小于 30
  • 图的边缘作为谓词给出,即
    e(1, 2).
    f(1, 2).

  • 我正在尝试使用以下方法:
  • 对于每对边(即图 1 和 2 中的每条边)
  • 尝试绑定(bind)2条边的顶点
  • 如果顶点绑定(bind)是不可能的(即已经存在与其中一个顶点的另一个绑定(bind)),则回溯并尝试另一对边。
  • 否则添加绑定(bind)并继续处理其余的图(即从每个图中删除一条边并再次应用程序)。

  • 除非两个图都是空的(意味着所有顶点都从一个图绑定(bind)到另一个图),否则程序会重复,这意味着成功。
    否则程序应该总是失败(即没有其他可用的绑定(bind)组合等)

    我的代码似乎可以工作,但仅适用于小图(猜测是因为它尝试了所有对:))。

    因此,如果有人知道如何优化代码(我相信可以插入多个剪辑,并且 try_bind 可以以更好的方式编写)或者可以提前告知更好的方法。

    附:为了检查非同构,我知道我们可以检查不变量等。现在这并不重要。

    代码:
    %define graph, i.e. graph is a list of edges
    graph1(RES):-findall(edge(X,Y), e(X, Y), RES).
    graph2(RES):-findall(edge(X,Y), f(X, Y), RES).

    %define required predicate
    iso:-graph1(G1), graph2(G2), iso_acc(G1, G2, [], _).
    %same as above but outputs result
    iso_w:-graph1(G1), graph2(G2), iso_acc(G1, G2, [], RES_MAP), write(RES_MAP).

    iso_acc([], [], MAP, RES):-append(MAP, [], RES), !.
    iso_acc([X|X_Rest], Y_LS, MAP, RES_MAP):-
    select(Y, Y_LS, Y_Rest),
    bind(X, Y, MAP, UPD_MAP),
    iso_acc(X_Rest, Y_Rest, UPD_MAP, RES_MAP).

    % if edges bind is successful then in RES or UPD_MAP updated binding map is returned (may return the same map
    % if bindings are already defined), otherwise fails
    bind([], [], MAP, RES):-append(MAP, [], RES), !.

    bind(edge(X1, Y1), edge(X2, Y2), MAP, UPD_MAP):-
    try_bind(b(X1, X2), MAP, RES),
    try_bind(b(Y1, Y2), RES, UPD_MAP).

    bind(edge(X1, Y1), edge(X2, Y2), MAP, UPD_MAP):-
    try_bind(b(X1, Y2), MAP, RES),
    try_bind(b(Y1, X2), RES, UPD_MAP).

    %if an absolute member, we're OK (absolute member means b(X,Y) is already defined
    try_bind(b(X, Y), MAP, UPD_MAP):-
    member(b(X, Y), MAP),
    append(MAP, [], UPD_MAP), !.

    %otherwise check that we don't have other binding to X or to Y
    try_bind(b(X, Y), MAP, UPD_MAP):-
    member(b(X, Z), MAP),
    %check if Z != Y
    Z=Y,
    append(MAP, [], UPD_MAP).

    try_bind(b(X, Y), MAP, UPD_MAP):-
    member(b(W, Y), MAP),
    %check if W == X
    W=X,
    append(MAP, [], UPD_MAP).

    %finally if we not an absolute member and if no other bindings to X and Y we add new binding
    try_bind(b(X, Y), MAP, UPD_MAP):-
    not(member(b(X, Z), MAP)),
    not(member(b(W, Y), MAP)),
    append([b(X, Y)], MAP, UPD_MAP).

    最佳答案

    首先,祝贺您很好地介绍了问题并提出了详尽的解决方案建议。

    在下一段中,我将讨论您的解决方案的实现细节。

    不幸的是,我必须说我看不到这种解决方案可扩展到更大尺寸的方法。假设有 10 条边的图。 iso_acc/4尝试将第一条边分配给第二条边中的任何一条边(10 种可能性),第二条边也绑定(bind)到任何一条边(每个前面的 10 种可能性:10*10),...。如果不是一些运气,那就有 10^10 种可能性,10!考虑到它们中的大多数被修剪得更快。

    次要意见是:

    您可以跳过 append(X,[],Y) 的使用, 所以

    bind([],[],MAP,RES) :- append(MAP,[],RES), !.

    可:
    bind([],[],MAP,MAP).
    try_bind/3 中的第二条和第三条规则似乎没有必要,在上一个中你已经验证了 no b(X,Y)属于 MAP .换句话说, member(b(X,Y),MAP)相当于 member(b(X,Z),MAP), Z=Y .

    附录

    让我们试试下面的方法。让示例图 e是:
            +----3----+
    1 ---2--+ | +---5
    +----4----+

    和图表 f是:
            +----3----+
    2 ---5--+ | +---1
    +----4----+

    基本算法可以是:
    memb( X-A, [X-B|_] ) :- permutation(A,B).
    memb( X, [_|Q] ) :- memb(X, Q).

    match( [], _ ).
    match( [H|Q], G2 ) :-
    memb(H,G2),
    match(Q,G2).

    graph_equal(G1,G2,MAP) :-
    bagof( X, graph_to_list(G1,X), L1 ),
    length(MAP,40),
    bagof( X, graph_to_list_vars(G2,MAP,X), L2 ), !,
    length( L1, S ),
    length( L2, S ),
    match( L1, L2 ).

    从这个出发点,可以进行优化。

    该算法需要一些初始数据转换器,以将每个图形转换为 node-[peer1,peer2,...] 形式的项目列表。 .此转换的规则是:
    bidir(G,X,Y) :- ( call(G,X,Y); call(G,Y,X) ).

    bidir_vars(G,MAP,VX,VY) :-
    bidir(G,X,Y), nth0(X,MAP,VX), nth0(Y,MAP,VY).

    graph_to_list( G, N-XL ) :-
    setof( X, bidir(G,N,X), XL).

    graph_to_list_vars( G, MAP, N-XL ) :-
    setof( X, bidir_vars(G,MAP,N,X), XL).

    附录 2

    此示例的初始数据为:
    e(1,2).
    e(2,3).
    e(2,4).
    e(3,4).
    e(3,5).
    e(4,5).

    f(2,5).
    f(3,5).
    f(4,5).
    f(3,4).
    f(1,4).
    f(1,3).

    附录 3

    现在使用示例图查询完整算法时 ef ,结果是:
    [debug]  ?- graph_equal(e,f,MAP).
    MAP = [_G2295, 5, 1, 3, 4, 2, _G2313, _G2316, _G2319|...] ;
    MAP = [_G2295, 5, 1, 4, 3, 2, _G2313, _G2316, _G2319|...] ;

    这意味着这些图是同构的,具有可能的节点映射 e:[5,1,3,4,2] => f:[1,2,3,4,5]e:[5,1,4,3,2] => f:[1,2,3,4,5] .

    附录 4

    基本基准。单一解决方案:
    ?- time( graph_equal(e,f,_) ). 
    % 443 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 1718453 Lips)

    所有解决方案:
    ?- time( (graph_equal(e,f,_),fail) ).
    % 567 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 2027266 Lips)

    关于Prolog 同构图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30609969/

    24 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com