Prolog回溯

Question

我一直在尝试编写一个 prolog 程序，但我遇到了它的回溯问题，这对我来说毫无意义。这是我遇到麻烦的条款之一：

edge(g1,a,b).
edge(g1,b,c).
edge(g1,a,c).
edge(g1,d,a).
edge(g1,d,b).
edge(g1,d,c).


spider(Grafo, AristasArana) :-
  findall(edge(Grafo,X,Y),edge(Grafo,X,Y),AristasTotales),
  member(edge(Grafo,X1,Y1),AristasTotales),
  zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana),
  length(AristasArana,L),
  L > 2.

zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana) :-
  member(edge(Grafo,A1,A2), AristasTotales),
  X1 \= A1,
  Y1 = A2,
  findall(edge(Grafo,X,Y),(Y = A2),ListaAux1),
  findall(edge(Grafo,X,Y),(X = A2),ListaAux2),
  % Pueden haber repetidos y no se eliminan.
  append(ListaAux2,ListaAux1,AristasArana).

zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana) :-
  member(edge(Grafo,A1,A2), AristasTotales),
  X1 \= A1,
  Y1 = A1,
  findall(edge(Grafo,X,Y),(Y = A1),ListaAux1),
  findall(edge(Grafo,X,Y),(X = A1),ListaAux2),
  % Pueden haber repetidos y no se eliminan.
  append(ListaAux2,ListaAux1,AristasArana).

zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana) :-
  member(edge(Grafo,A1,A2), AristasTotales),
  X1 = A1,
  Y1 \= A2,
  findall(edge(Grafo,X,Y),(Y = A1),ListaAux1),
  findall(edge(Grafo,X,Y),(X = A1),ListaAux2),
  % Pueden haber repetidos y no se eliminan.
  append(ListaAux2,ListaAux1,AristasArana).

zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana) :-
  member(edge(Grafo,A1,A2), AristasTotales),
  X1 = A2,
  Y1 \= A2,
  findall(edge(Grafo,X,Y),(Y = A2),ListaAux1),
  findall(edge(Grafo,X,Y),(X = A2),ListaAux2),
  % Pueden haber repetidos y no se eliminan.
  append(ListaAux2,ListaAux1,AristasArana).

整个程序在应该统一的时候没有统一，所以我尝试在 gprolog 上 trace. 它，这是我发现的第一个问题：

 5    3  Exit: member(edge(g1,a,b),[edge(g1,a,b),edge(g1,b,c),edge(g1,a,c),edge(g1,d,a),edge(g1,d,b),edge(g1,d,c)]) ? 
      6    3  Call: a\=a ? 
      7    4  Call: a=a ? 
      7    4  Exit: a=a ? 
      6    3  Fail: a\=a ? 
      5    3  Redo: member(edge(g1,a,b),[edge(g1,a,b),edge(g1,b,c),edge(g1,a,c),edge(g1,d,a),edge(g1,d,b),edge(g1,d,c)]) ? 
      5    3  Exit: member(edge(g1,b,c),[edge(g1,a,b),edge(g1,b,c),edge(g1,a,c),edge(g1,d,a),edge(g1,d,b),edge(g1,d,c)]) ? 
      6    3  Call: a\=b ? 
      7    4  Call: a=b ? 
      7    4  Fail: a=b ? 
      6    3  Exit: a\=b ? 
      5    3  Redo: member(edge(g1,b,c),[edge(g1,a,b),edge(g1,b,c),edge(g1,a,c),edge(g1,d,a),edge(g1,d,b),edge(g1,d,c)]) ?

不知为什么，它在这里胜利后6 3 Exit: a\=b ?它会重做前面的子句，直到它失败，我不明白为什么。

编辑：如果有一个节点附有 3 个或更多边（无论这些边来自或指向该节点，都无关紧要），这个想法是为了让程序统一。请注意，如果不止一个节点连接了三个或更多边，则可以多次统一。如您所见，边是作为事实给出的。

Answer 1

首先，您大量使用 "idiom"：findall(Foo,Foo,T), member(Foo,T)。你最好只做 Foo。您正在将知识存储具体化为一个列表变量，大概是因为您更熟悉它并且您认为它会更容易使用，但它并没有真正给您带来任何好处。它把你盘子里的食物推来推去。特别是因为你没有用 T 做任何可能证明工作合理的事情，比如使用 select/3 来限制你的搜索。

其次，zpider/3 有四个子句。为什么？您正在对第一个节点和后续节点在第一个或第二个参数上匹配或不匹配的情况进行某种奇怪的细分。我认为您不清楚 这些子句中的每一个都将执行一次，然后回溯到 。您无法按顺序获得所有这四个运行的好处。它们中的每一个都代表一个替代解决方案。这就是为什么你会有意想不到的回溯！

我的结论是您的代码非常离谱。但是，您遇到的部分问题是图形的节点都是解决方案，因此很难调试。让我们制作一个更有趣的图表。我想出了这个，在 graphviz 语法中：

graph g {
    a -- c;
    b -- c;  b -- e;
    c -- d;  c -- e;
    d -- e;
}

我用绿色突出显示了两个节点，表示它们符合您的标准（三个边）；其余的则没有，所以如果我们成功了，我们应该只看到 c 和 e 作为我们返回的节点。

让我们试着低效地做这个，只是为了好玩。我们需要三个链接，所以我们去具体获取它们。

uedge(Graph, X, Y) :- edge(Graph, X, Y).
uedge(Graph, X, Y) :- edge(Graph, Y, X).

thrice_connected(Graph, Node) :-
    uedge(Graph, Node, A),
    uedge(Graph, Node, B),
    uedge(Graph, Node, C),
    A \== B, B \== C, A \== C.

对于初学者，我定义了 uedge/3，它给了我们无向图边，我定义了 thrice_connected/2，它使用它来找到到这个节点的三个不同的连接。您可以通过运行看到它的工作原理，尽管效率低下，但是您会得到很多重复的值，因为 A、B 和 C 会以各种方式排列。所以，我在这里所做的工作有效，但实际上并不是那么有效。它效率低下，因为每次失败时，它都会重新开始最后的 uedge/3 搜索，直到完成所有三个搜索。三个就很糟糕，更多只会变得更糟！

要更有效地执行此操作，您必须意识到您需要一个唯一的节点列表。在您的代码中，您努力为您的事实数据库制作一个 edge/3 结构列表。您不需要重新创建您拥有的结构，您可以通过使用 setof/3 创建一些更有用的东西，顺便说一句，它立即为您购买了独特性：

?- setof(Adjacent, uedge(g, Node, Adjacent), AdjacentNodes).
Node = a,
AdjacentNodes = [c] ;
Node = b,
AdjacentNodes = [c, e] ;
Node = c,
AdjacentNodes = [a, b, d, e] ;
Node = d,
AdjacentNodes = [c, e] ;
Node = e,
AdjacentNodes = [b, c, d].

看看那个，它是如此接近它实际上伤害的解决方案。一个二阶查询说 "give me the set of Adjacent nodes, defined as edges in g from Node to Adjacent." 因为我们没有指定 Node，Prolog 将生成它们，并且我们为图中的每个节点获得一个解决方案。完美的！从这里开始，解决方案几乎是微不足道的：

thrice_connected(Graph, Node) :-
    setof(Adjacent, uedge(Graph, Node, Adjacent), AdjacentNodes),
    length(AdjacentNodes, Len),
    Len >= 3.

我们实际上只是采用之前的查询，对其进行一些概括并使其执行 >= 3 测试。

?- thrice_connected(Graph, Node).
Graph = g,
Node = c ;
Graph = g,
Node = e.

而且有效！

Prolog回溯

Prolog Bactracking

prolog

backtracking