CODEWITHSUNDEEP
prologartificial-intelligencedepth-first-search
zead seam
zead seam

Reputation: 31

Prevent cycle in Depth first search using prolog

Is there any way to prevent cycle in this code.

move(a,b).
move(b,a).
move(a,c).
move(b,d).
move(b,e).
move(d,h).
move(d,i).
move(e,j).
move(e,k).
move(c,f).
move(c,g).
move(f,l).
move(f,m).
move(g,n).
move(g,o).
goal(n).


goSolveTheMaze(Start,Way) :-
    dfs(Start, Way),!.

dfs(Goal, [Goal]) :-
   goal(Goal),!.

dfs(Start, [Start|Way])  :-
    move(Start, N),
    dfs(N, Way).

so when move(a,b) move to (b,c) dont go back to (b,a), when run goSolveTheMaze(a,path). The output should be path=[a,c,g,n].

Upvotes: 1

Views: 199

Answers (1)

14241354
14241354

Reputation: 211

What if you add a third argument to dfs which is a list of where you've already visited? You could then use \+/1 and member/2 to avoid returning to places you've already been.

For example, if you use the following:

move(a,b).
move(b,a).
move(a,c).
move(b,d).
move(b,e).
move(d,h).
move(d,i).
move(e,j).
move(e,k).
move(c,f).
move(c,g).
move(f,l).
move(f,m).
move(g,n).
move(g,o).
goal(n).


goSolveTheMaze(Start,Way) :-
    dfs(Start, Way, [Start]),!.

dfs(Goal, [Goal], _) :-
   goal(Goal),!.

dfs(Start, [Start|Way], Visited)  :-
    move(Start, N),
    \+ member(N, Visited),
    dfs(N, Way, [N|Visited]).

Then the query:

?- goSolveTheMaze(a, X).

Will produce the result:

X = [a, c, g, n]

Update in response to comment "can you tell me what \+ do?":

The \+ predicate is true when its argument cannot be proven. Therefore in the above example the line \+ member(N, Visited) means "when N is not a member of the list Visited".

See: https://www.swi-prolog.org/pldoc/man?predicate=%5C%2B/1

Upvotes: 1

Related Questions