Prolog 图路径搜索与循环路径 [英] Prolog graph path search with cyclic path

问题描述

我是 Prolog 的新手.我试图找出一个问题，我需要检查边缘之间是否存在路径.我完成了循环的非循环图形代码，我的代码将进入无限循环.

I am a complete newbie in Prolog. I am trying to figure out a problem where I need to check if path is present between edges. I am done with acyclic graph code for cyclic my code is going to infinite loop.

path(Start, End) :- edge(Start, End).
path(Start, End) :- edge(Start, Z), path(Z, End).

我需要通过定义一个新的谓词来处理这种情况:新路径(开始，结束，路径)这应该消除无限循环.请让我知道如何进行.

I need to handle this case by defining a new predicate: new_path(Start,End,path) which should eliminate infinite loop. Please let me know how to proceed with it.

推荐答案

您需要随时跟踪访问过的节点，使用 prolog 列表作为 LIFO 堆栈.大致如下:

You need to keep track of what nodes you've visited as you go, using a prolog list as a LIFO stack. Something along these lines:

path( A , Z , P ) :-           % to find a path from A to Z
  traverse( A , Z , [] , P ) , % take a walk, visiting A to see if we can get to Z, seeding the visited list with the empty string.
  reverse(P,Path)              % once we find a path, let's reverse it, since it's in LIFO order.
  .                            % That's all there is to it, really.

traverse( Z , Z , V , [Z|V] )     % if current node is the destination node, we've arrived.
  .                               % - just push the destination vertice onto the visited list and unify that with the path
traverse( A , Z , V , P ) :-      % Otherwise...
  edge( A , Z ) ,                 % - if the current node is directly connected to the destination node,
  traverse( Z , Z , [A|V] , P)    % - go visit the destination, marking the current node as visited
  .                               %
traverse( A, Z , V , P ) :-       % Otherwise...
  A = Z,
  edge( A , B ) ,                 % - if the current node is connected to a node
  B = Z ,                        % - that is not the destination node, and
  unvisited([A|V],B) ,            % - we have not yet visited that node,
  traverse( B , Z , [A|V] , P )   % - go visit the intermediate node, marking the current node as visited.
  .                               % Easy!

unvisited( []    , _ ) .                   % We succeed if the visited list is empty.
unvisited( [A|_] , A ) :- ! , fail .       % We fail deterministically if we find the node in the visited list.
unvisited( [_|L] , A ) :- unvisited(L,A) . % otherwise, we keep looking.

这篇关于Prolog 图路径搜索与循环路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！