如果先前的解决方案不符合某些条件,如何尝试新的排列？

Question

所以,这是我一直试图解决的练习.我得到一个像这样的输入列表[a-b,b-c],它们是连接节点的节点和弧.条件是:

节点需要有一个唯一的编号,从1到N,

和弧需要有一个唯一的编号,从1到N-1,并且该编号必须是减去弧连接的节点的结果.

所以答案是:

EnumNodos = [enum(3,a), enum(1,b), enum(2,c)],
EnumArcos = [enum(2,a?b), enum(1,b?c)]

因为我还没有能够为此提出算法,我也不知道是否有一个算法,我想,我可以尝试每一种可能性,因为我知道如果输入是正确的,有一个解决方案,并且那样早晚我会得到它.

我找到了一个prolog排列的例子,其中,如果我给它一些输入列表,它给出了它的排列.然后(在控制台中),如果我点击';' 它给了我另一个,依此类推.我试图自己包含该代码.

我还没有完成,但我会提供一些帮助,特别是我试图置换选项的"循环"方法.我真的不知道你会怎么说,在prolog中,如果这个动作失败了,尝试另一个新的排列,不同于之前尝试的每个排列(没有给出';'作为解决方案的输入.因为有许多排列正在进行失败,我想检查它是否失败,如果失败,请尝试另一个.

编辑所以我刚刚发现了...我一直在尝试,我想我仍然缺少一个关键部分.截至目前,我觉得我可以通过这个获得我需要的所有可能性列表:setof(Out,perm(ListaEnum, SalidaPerm),X),

但是我仍然遇到FAILING然后重试的想法.到目前为止,我的想法是:我得到了X结果,然后像任何列表一样旅行.我检查它是否有唯一的数字等,如果没有,我想继续旅行那个X.所以我会努力失败而不是成功？我应该这样做吗？

% enumerate(CONNECTIONS_IN, NODES_OUT, ARCS_OUT)
%TODO query example of call: enumerate([a-b,b-c], EnumNodos, EnumArcos).

enumerate(C, EnumNodos, EnumArcos) :-
    enum_nodes(C, [], NodeListUnique, [], PermNodes, 1),
    loopPerm(C, NodeListUnique, EnumArcos, PermNodes, SalidaPerm).

% enum_nodes(CONNECTIONS_IN, NODES_IN, NODES_OUT, IDS_IN, IDS_OUT, START_ID) 
% Fills up NODES_OUT with unique nodes, and PERMOUT with IDS. New IDs start at START_ID...

enum_nodes([], N, N, M, M, _).
enum_nodes([A-B | T], N, NOUT, M, PERMOUT, ID) :-
    ensure_node(A, N, NTMP1, M, PERMNODESOUTA, ID, ID1),
    ensure_node(B, NTMP1, NTMP2, PERMNODESOUTA, PERMNODESOUTB, ID1, ID2),
    enum_nodes(T, NTMP2, NOUT, PERMNODESOUTB, PERMOUT, ID2).

% ensure_node(NODE, NODES_IN, NODES_OUT,IDS_IN, IDS_OUT, ID_IN, ID_OUT)
% Adds enum(ID_IN, NODE) to NODES_IN to produce NODES_OUT if NODE does not already exist in NODES_IN

ensure_node(NODE, NODES_IN, NODES_IN, PermNodesNOVALENin, PermNodesNOVALENin, ID, ID) :-
    member(NODE, NODES_IN), !.

ensure_node(NODE, NODES_IN, [NODE | NODES_IN], PERMIN, [ID_IN|PERMIN], ID_IN, ID_OUT) :-
    ID_OUT is ID_IN + 1.

%At this point I have a list of unique nodes and a list of IDs for said nodes, and I want to start calculatin permutations of this two lists until I find one that works.
loopPerm(C, NodeListUnique, EnumArcos, PermNodes, SalidaPerm):-
    crearEnum(NodeListUnique, PermNodes, ListaEnum),
    perm(ListaEnum, SalidaPerm),
    create_arcs(C, SalidaPerm, []),
    %%here is where code stops working properly
    loopPerm(C, EnumNodos, EnumArcos, PermNodes, SalidaPerm).

%crear_enum(NODES_IN, IDS_IN, enumLISTout)
%creates a list of enums to be permuted, TODO the idea here is that each call will change the list, so if it failed before, it should try a new one.
crearEnum([], [], []).
crearEnum([H1 | NodeListUnique], [H2| PermNodes], [enum(H2,H1)|Salida]):-
    crearEnum(NodeListUnique, PermNodes, Salida).


% create_arcs(CONNECTIONS_IN, NODES_IN, ARCS_OUT).  
% Create arcs - makes a list of arc(NODE_ID_1, NODE_ID_2)...

create_arcs([], _, _).
create_arcs([A-B | T], NODES, LISTARCS) :-
    ensure_arcs(A,B,NODES, LISTARCS, LISTARCS2),
    create_arcs(T, NODES, LISTARCS2).

%ensure_arcs(NODE_A, NODE_B, NODELIST, LISTARCSIN, LISTARCSOUT)
%builds a list of arcs TODO works WRONG when arc already was in the input. It should fail, but it just checks that is a member and moves on. So basically it works when arcs are new, because they are added properly, but not when arcs were already found (and as per the exercise it should fail and try another permutation).
ensure_arcs(A,B,NODES, LISTARCSIN, LISTARCSIN):-
    member(enum(NODE_ID_A, A), NODES),
    member(enum(NODE_ID_B, B), NODES),
    REMAINDER is abs(NODE_ID_A-NODE_ID_B),
    member(enum(REMAINDER,_), LISTARCSIN), !.

ensure_arcs(A,B,NODES, LISTARCSIN,[enum(REMAINDER, A-B) | LISTARCSIN]):-
    member(enum(NODE_ID_A, A), NODES),
    member(enum(NODE_ID_B, B), NODES),
    REMAINDER is abs(NODE_ID_A-NODE_ID_B).


perm([H|T], Perm) :-
   perm(T, SP),
   insert(H, SP, Perm).
perm([], []).

insert(X, T, [X|T]).
insert(X, [H|T], [H|NT]) :-
   insert(X, T, NT).

以下是我需要手工处理的其他一些例子.我也想道歉,因为我对代码一点都不满意,只是我需要继续前进,而不是修复我确定的痛苦错误(但是我真的无法修复,因为现在,我花了太长时间才能得到任何有效的代码,即使几乎没有.

    6a
  5    4
1b      2e
2       3
3c      5f
1
4d

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

EnumArcos = [enum(5,a?b), enum(4,a-e), enum(3,e-f), , enum(2,b-c), enum(1,c-d)]


    5a
  4   3
1b      2e
1       2
3c      4f

EnumNodos = [enum(5,a), enum(1,b), enum(2,e), enum(3,c), enum(4,f)],

EnumArcos = [enum(4,a?b), enum(3,a-e), enum(1,b-c), , enum(2,e-f)]

    5a
  4    3
1b      2e
2
3c      
1
4d

Answer 1

简短的回答是,你想要做的就是Prolog 自动做的事情:它被称为回溯,意味着Prolog将尝试各种可能性,直到他们都筋疲力尽.

因此,在您的情况下,您可以在概念上将您的整个任务表述为:

solution(S) :-
    candidate(S),
    satisfies_all_constraints(S).

而已.Prolog将生成所有候选解决方案,并准确报告那些"满足所有约束",这是您需要描述的内容satisfies_all_constraints/1

出于这个原因,Prolog被称为声明性语言:您描述了您希望它找到的内容.您并不特别关心它如何找到这些解决方案.

请注意,通过使用setof/3您绕过此隐式回溯并将所有解决方案重新化为Prolog术语,您可以在程序中进行推理.例如,如果您想以不同的顺序探索分支,或者在 Prolog中完全实现其他搜索策略,这可能很有用.对于天真的方法,setof/3不需要,但需要清楚地描述您想要找到的解决方案.

更长的答案是这种方法(也称为"生成和测试")在某些情况下肯定非常有吸引力,有用和有启发性,例如:

1. 在任何情况下,你完全不知道如何找到你的结果
2. 你想在任何情况下生成所有解决方案
3. 在任何情况下产生所有可能性都不会花费很多时间
4. 等等

但是,寻找特定解决方案的方法通常要快得多,而且您的问题 - 虽然我不知道您真正想要找到什么 - 似乎属于这一类.

尽管如此,因为这也是你所要求的,我建议你至少尝试一下天真的方法(生成和测试),因为它经常导致你真正想要的非常简短和明确的规格,并且运气好,足以也得到它,至少在小的情况下.