Пролог в списке представленных графов - PullRequest
Новая
       32

Пролог в списке представленных графов

1 голос
/ 06 марта 2019

Я пытаюсь просмотреть график, который я построил в прологе. График представлен в виде списка переходов вида: next (FromState, ToState, Symbol), где FromState и ToState - узлы графа, представленные в виде: state (Number, IrrelevantVariable). Символ может принимать много значений, но меня интересуют только переходы с эпсилоном в качестве символа. Учитывая группу StartStates, мне нужно посмотреть, какие переходы имеют FromState = StartState и Symbol = epsilon. Если эти два условия выполняются, я добавлю ToState в конец StartStates и добавлю FromState в список посещенных узлов. У меня проблемы с этим, и моя текущая программа по какой-то причине не работает. Есть идеи, почему это не работает? Одна из проблем заключается в том, что когда я использую предикат участника, чтобы увидеть, посетил ли я состояние в заголовке списка, оно заканчивается объединением, чтобы сделать предикат участника истинным, вместо того, чтобы фактически проверять Visited for Head при первом вызове 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 ([состояние (0, iv)], [следующее (состояние (0, iv), состояние (1, iv), эпсилон), следующее (состояние (1, iv), состояние (2, iv), эпсилон] Посещено , Закрытие).

Выход: Закрытие = [состояние (0, iv), состояние (1, iv), состояние (2, iv)]

1 Ответ

1 голос
/ 06 марта 2019

Я знаю, что структура не совпадает с приведенной в вопросе, но я также знаю, что вы студент, и вам нужно понимать и изучать код, так что вот решение, которое не использует те же структуры, что и у вас,но должен помочь вам выучить и выполнить задание.

График взят из этой страницы . 

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].
...