Prolog 列表表示图遍历

Question

我正在尝试遍历我在序言中构建的图。该图表示为以下形式的转换列表： next(FromState, ToState, Symbol) 其中 FromState 和 ToState 是图形的节点，表示为：state(Number, IrrelevantVariable)。符号可以取很多值，但我只对以 epsilon 为符号的转换感兴趣。给定一组 StartStates，我需要查看哪些转换具有 FromState = StartState 和 Symbol = epsilon。如果这两个条件成立，我将把 ToState 添加到末尾的 StartStates 并将 FromState 添加到已访问节点的列表中。我在这样做时遇到了麻烦，而且我当前的程序由于某种原因无法运行。任何想法为什么它不起作用？其中一个问题似乎是，当我使用成员谓词来查看我是否访问了列表头部的状态时，它最终统一使成员谓词为真，而不是在第一次调用 espsilon_closure_helper3

epsilon_closure_helper3([], [Transitions], Visited).

epsilon_closure_helper3([Head|Tail], Transitions, Visited) :-
  member(Head, Visited)
  ->
  epsilon_closure_helper2(Tail, Transitions, Visited)
  ;
  epsilon_closure_helper2(Head, Transitions, ClosureStates1),
  append(Tail, ClosureStates1, Tail1),
  sort(Tail1, Tail2),
  append(Vistited, [Head], Visited1),
  epsilon_closure_helper3(Tail2, Transitions, Visited1).


epsilon_closure_helper2(State, [], States) :-
  States = [State].

epsilon_closure_helper2(State, Transitions, States) :-
   Transitions = [Head|Tail],
   epsilon_closure_helper2(State, Tail, States1),
   Head = next(A, B, Symbol),
   (
   test_state(State, A, Symbol) -> append(States1, [B], States) ; 
   States = States1
   ).

  test_state(TargetState, State, Symbol) :-
    State = TargetState,
    Symbol = epsilon.

示例输入： epsilon_closure_helper3([state(0, iv)], [next(state(0, iv), state(1, iv), epsilon), next(state(1, iv), state(2, iv) , epsilon] 已访问，关闭）。

输出：闭包 = [state(0, iv), state(1, iv), state(2, iv)]

Answer 1

我知道结构与问题中给出的不一样，但我也知道你是一名学生，需要理解和学习代码，所以这里有一个解决方案，没有使用与问题中相同的结构你的，但应该可以帮助你学习和完成作业。

图表来自此page。

transistion(a,b,0).
transistion(a,c,0).
transistion(a,a,1).
transistion(a,b,epsilon).
transistion(b,b,1).
transistion(b,c,epsilon).
transistion(c,c,0).
transistion(c,c,1).

epsilon_closure(End_state,States) :-
    epsilon_closure(End_state,[],States).

epsilon_closure(End_state,States0,States) :-
    bagof([Start,End,Transistion],transistion(Start,End,Transistion),Transitions),
    epsilon_closure_rec(End_state,Transitions,States0,States), !.

epsilon_closure_rec(End,[[Start_state,End,epsilon]|Transitions],States0,States) :-
    \+ memberchk(Start_state,States0),
    epsilon_closure(Start_state,States0,States1),
    epsilon_closure_rec(End,Transitions,States1,States).
epsilon_closure_rec(End,[[_,_,_]|Transitions],States0,States) :-
    epsilon_closure_rec(End,Transitions,States0,States).
% A state is an epsilon transition to itself
epsilon_closure_rec(End_state,[],States0,[End_state|States0]).

请注意代码中没有任何 append/3、sort/2、=/2 或 ->/2.

示例运行：

?- epsilon_closure(a,States).
States = [a].

?- epsilon_closure(b,States).
States = [b, a].

?- epsilon_closure(c,States).
States = [c, b, a].

Prolog 列表表示图遍历

Prolog List Represented Graph Traversal

finite-automata

prolog

transitive-closure