Reputation: 1139
Breadth First Search code won't output BFS result
This is the code I found, and it was fixed in another post I made.
s(a, b).
s(a, c).
s(b, g).
s(b, f).
s(c, r).
s(c, e).
goal(g).
solve( Start, Solution) :-
breadthfirst( [ [Start] ], Solution).
breadthfirst( [ [Node | Path] |_], [Node | Path] ) :-
goal( Node).
breadthfirst( [ [N | Path] | Paths], Solution) :-
bagof([M,N|Path],
( s( N, M), \+ member( M, [N | Path] ) ), NewPaths),
%conc( Paths, NewPaths, Pathsl), !,
append(Paths, NewPaths, Pathsl), !,
breadthfirst( Pathsl, Solution);
breadthfirst( Paths, Solution).
However, I found that the output is :
?- solve(a,S).
S = [g, b, a] ;
I took all the facts and draw a tree to represent them, and in the tree, we have a gives b and c which are at the same level, at level 1. Therefore they should be visited first. And then after, g will be visited in the 2nd level through b.
So the output should be :
?- solve(a,S).
S = [g, c, b, a] ;
But it isn't giving me that output and I don't know why.
Now, there's also a problem of reversing the output, I would appreciate it if that is solved too.
Upvotes: 0
Views: 1267
Answers (1)
Reputation: 24976
It isn't giving me that output and I don't know why.
Your code is giving the correct answer as noted in my earlier answer.
?- solve(a,S).
S = [g, b, a] ;
The problem is not the answer the code gives, but I believe in your understanding of either how the algorithm works or the layout of the graph from the facts.
Using paper and pen to work on a problem before converting it to code is a wise decision.
Here is the graph in a visual form with the root (a) at the top.
a Level 0
/ \
b c Level 1
/ \ / \
g f r e Level 2
Notice that the shortest path from a to g is a,b,g and not a,b,c,g as you expect. Even though c is connected to a, it is not on the path from a to g and so is not part of the solution.
You are correct in that with Breadth First Search (BFS) you start at Level 0 then process ALL the nodes connected to it, which are shown at Level 1. Then do the same for each node in Level 1 creating Level 2 before repeating again for each new level.
In processing each node, BFS just looks for any node connected to that current node that it has not visited already and records any information it needs in a table or other data structure. If your example included weights on each vertex then the cost to get to the current node being processed would be recorded with the current node in the data structure. Visiting a node for processing a node is not the same as visiting a node as part of the shortest path from one node to another.
Another way to think about this is that both BFS and Depth First Search (DFS) should both give the same answers, the difference is in the algorithm. If you use DFS on this you will get the same answer of a,b, and g, without c.
dfs_1(N,N,[N]).
dfs_1(Start,End,[Start|Rest] ) :-
s(Start,Next),
dfs_1(Next,End,Rest).
?- dfs_1(a,g,Path).
Path = [a, b, g] ;
false.
From comment:
Okay, I see, so the actual working of the algorithm is as I printed it including c, but then when it wants to print the final path, it will exclude c since it's not on the path.
I would not agree with that.
In running the query with trace on in SWI-Prolog
line 1 [trace] 133 ?- solve_1(a,S).
line 2 Call: (8) solve_1(a, _12870)
line 3 Call: (9) breadthfirst_1([[a]], _12870)
line 4 Call: (10) goal_1(a)
line 5 Fail: (10) goal_1(a)
line 6 Redo: (9) breadthfirst_1([[a]], _12870)
line 7 ^ Call: (10) bagof([_13076, a], (s(a, _13076), \+member(_13076, [a])), _13134)
line 8 Call: (17) s(a, _13076)
line 9 Exit: (17) s(a, b)
line 10 Call: (17) lists:member(b, [a])
line 11 Fail: (17) lists:member(b, [a])
line 12 Redo: (17) s(a, _13076)
line 13 Exit: (17) s(a, c)
line 14 Call: (17) lists:member(c, [a])
line 15 Fail: (17) lists:member(c, [a])
line 16 ^ Exit: (10) bagof([_13076, a], user:(s(a, _13076), \+member(_13076, [a])), [[b, a], [c, a]])
line 17 Call: (10) lists:append([], [[b, a], [c, a]], _13216)
line 18 Exit: (10) lists:append([], [[b, a], [c, a]], [[b, a], [c, a]])
line 19 Call: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line 20 Call: (11) goal_1(b)
line 21 Fail: (11) goal_1(b)
line 22 Redo: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line 23 ^ Call: (11) bagof([_13198, b, a], (s(b, _13198), \+member(_13198, [b, a])), _13256)
line 24 Call: (18) s(b, _13198)
line 25 Exit: (18) s(b, g)
line 26 Call: (18) lists:member(g, [b, a])
line 27 Fail: (18) lists:member(g, [b, a])
line 28 Redo: (18) s(b, _13198)
line 29 Exit: (18) s(b, f)
line 30 Call: (18) lists:member(f, [b, a])
line 31 Fail: (18) lists:member(f, [b, a])
line 32 ^ Exit: (11) bagof([_13198, b, a], user:(s(b, _13198), \+member(_13198, [b, a])), [[g, b, a], [f, b, a]])
line 33 Call: (11) lists:append([[c, a]], [[g, b, a], [f, b, a]], _13350)
line 34 Exit: (11) lists:append([[c, a]], [[g, b, a], [f, b, a]], [[c, a], [g, b, a], [f, b, a]])
line 35 Call: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line 36 Call: (12) goal_1(c)
line 37 Fail: (12) goal_1(c)
line 38 Redo: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line 39 ^ Call: (12) bagof([_13338, c, a], (s(c, _13338), \+member(_13338, [c, a])), _13396)
line 40 Call: (19) s(c, _13338)
line 41 Exit: (19) s(c, r)
line 42 Call: (19) lists:member(r, [c, a])
line 43 Fail: (19) lists:member(r, [c, a])
line 44 Redo: (19) s(c, _13338)
line 45 Exit: (19) s(c, e)
line 46 Call: (19) lists:member(e, [c, a])
line 47 Fail: (19) lists:member(e, [c, a])
line 48 ^ Exit: (12) bagof([_13338, c, a], user:(s(c, _13338), \+member(_13338, [c, a])), [[r, c, a], [e, c, a]])
line 49 Call: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], _13490)
line 50 Exit: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]])
line 51 Call: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line 52 Call: (13) goal_1(g)
line 53 Exit: (13) goal_1(g)
line 54 Exit: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], [g, b, a])
line 55 Exit: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], [g, b, a])
line 56 Exit: (10) breadthfirst_1([[b, a], [c, a]], [g, b, a])
line 57 Exit: (9) breadthfirst_1([[a]], [g, b, a])
line 58 Exit: (8) solve_1(a, [g, b, a])
line 59 S = [g, b, a] ;
line 60 Redo: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line 61 ^ Call: (13) bagof([_13484, g, b, a], (s(g, _13484), \+member(_13484, [g, b, a])), _13542)
line 62 Call: (20) s(g, _13484)
line 63 Fail: (20) s(g, _13484)
line 64 ^ Fail: (13) bagof([_13484, g, b, a], user:(s(g, _13484), \+member(_13484, [g, b, a])), _13548)
line 65 Redo: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line 66 Call: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line 67 Call: (14) goal_1(f)
line 68 Fail: (14) goal_1(f)
line 69 Redo: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line 70 ^ Call: (14) bagof([_13484, f, b, a], (s(f, _13484), \+member(_13484, [f, b, a])), _13542)
line 71 Call: (21) s(f, _13484)
line 72 Fail: (21) s(f, _13484)
line 73 ^ Fail: (14) bagof([_13484, f, b, a], user:(s(f, _13484), \+member(_13484, [f, b, a])), _13548)
line 74 Redo: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line 75 Call: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line 76 Call: (15) goal_1(r)
line 77 Fail: (15) goal_1(r)
line 78 Redo: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line 79 ^ Call: (15) bagof([_13484, r, c, a], (s(r, _13484), \+member(_13484, [r, c, a])), _13542)
line 80 Call: (22) s(r, _13484)
line 81 Fail: (22) s(r, _13484)
line 82 ^ Fail: (15) bagof([_13484, r, c, a], user:(s(r, _13484), \+member(_13484, [r, c, a])), _13548)
line 83 Redo: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line 84 Call: (15) breadthfirst_1([[e, c, a]], _12870)
line 85 Call: (16) goal_1(e)
line 86 Fail: (16) goal_1(e)
line 87 Redo: (15) breadthfirst_1([[e, c, a]], _12870)
line 88 ^ Call: (16) bagof([_13484, e, c, a], (s(e, _13484), \+member(_13484, [e, c, a])), _13542)
line 89 Call: (23) s(e, _13484)
line 90 Fail: (23) s(e, _13484)
line 91 ^ Fail: (16) bagof([_13484, e, c, a], user:(s(e, _13484), \+member(_13484, [e, c, a])), _13548)
line 92 Redo: (15) breadthfirst_1([[e, c, a]], _12870)
line 93 Call: (16) breadthfirst_1([], _12870)
line 94 Fail: (16) breadthfirst_1([], _12870)
line 95 Fail: (15) breadthfirst_1([[e, c, a]], _12870)
line 96 Fail: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line 97 Fail: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line 98 Fail: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line 99 Fail: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line 100 Fail: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line 101 Fail: (9) breadthfirst_1([[a]], _12870)
line 102 Fail: (8) solve_1(a, _12870)
line 103 false.
At
line 7 ^ Call: (10) bagof([_13076, a], (s(a, _13076), \+member(_13076, [a])), _13134)
it shows the result of visiting the start node a which is just the path a and in a list of known paths is [a].
at
line 16 ^ Exit: (10) bagof([_13076, a], user:(s(a, _13076), \+member(_13076, [a])), [[b, a], [c, a]])
for path [a] a new list is created by using the item at the head of the list and visiting one of it's neighbors that have not been visited and adding that new path into a new list.
So
with with path [a] and using the item at the head of the list a visit one of its neighbors s(a,b) and add that new path into a new list, [[b,a]].
with with path [a] and using the item at the head of the list a visit one of its neighbors s(a, c). and add that new path into a new list, [[b,a],[c,a]].
at
line 32 ^ Exit: (11) bagof([_13198, b, a], user:(s(b, _13198), \+member(_13198, [b, a])), [[g, b, a], [f, b, a]])
for path [b, a] a new list is created by using the item at the head of the list and visiting one of it's neighbors that have not been visited and adding that new path into a new list.
So
with with path [b, a] and using the item at the head of the list b visit one of its neighbors s(b, g). and add that new path into a new list, [[g, b, a]].
with path [b, a] and using the item at the head of the list b visit one of its neighbors s(b, f). and add that new path into a new list, [[g, b, a], [f, b, a]].
Notice that the answer [g, b, a] is now in the new list but it does not have c in the path.
At
line 50 Exit: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]])
all of the paths have been created
[[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]]
by using all of the s/2 facts and still the path with the answer [g, b, a] has no c in it.
Why the change from conc/3 to append/3 ?
Even though it is not one of your questions I need to answer it for others that read this question, especially people learning Prolog on their own for the first time.
This is my version of the events related to conc/3 and append/3 if there is another story about it do tell; I will even ask it as a posted question if need be.
One of the best if not the best books for introductory learning/teaching Prolog is "Prolog Programming for Artificial Intelligence" By Ivan Bratko. (WorldCat) (Amazon).
When first learning Prolog, people tend to spend their life in the list data structure and get a healthy diet of append/3 but in the book he chose to have the students create their own version of append/3 and named it conc/3. So through out the book is the use of conc/3 and hardly any use of append/3. Now those people are use to conc/3 and start writing code with it, posting it, etc. and it is very infectious, and you happen to have caught it. So I gave your code the remedy.
Problem of reversing the output.
When recursion is used to solve a problem it typically stores the intermediate result on the stack. Depending on the order on the stack the results are in the correct order, or in a reversed order.
There are a few ways to get the results to be returned from recursion in the correct order.
For most beginners it is to get the results and than if need be just reverse the results. For Prolog if the result is a list then reverse/2 works.
?- reverse([g, b, a],R).
R = [a, b, g].
The predicates for reverse/2
?- listing(reverse/2).
lists:reverse(A, B) :-
reverse(A, [], B, B).
true.
?- listing(reverse/4).
lists:reverse([], A, A, []).
lists:reverse([B|A], C, D, [_|E]) :-
reverse(A, [B|C], D, E).
true.
When you get into larger problems constantly reversing the result even between different predicate calls starts to add up time. This is especially true in functional programming.
Another way is by passing an accumulator. To demonstrate this I will use this simpler version of reverse.
reverse_2(L,Result) :-
accumulator_reverse(L,[],Result).
accumulator_reverse([],A,A).
accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
The first clause initializes the accumulator to an empty list [] for use with accumulator_reverse/3
reverse_2(L,Result) :-
accumulator_reverse(L,[],Result).
The other two clauses just recursively process a list with this clause being the base case
accumulator_reverse([],A,A).
which is when the input list is empty ([]) and
this clause
accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
to take the list apart [H|T] (AKA deconstruct) and append the head H to the accumulator [H|A] (AKA construct).
As the list is processed through
accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
the original list gets smaller and smaller because the head is always being removed from the list and the accumulator grows because the head from the list is always being added to the accumulator. Since the order in which list is deconstructed, (front to back) and the accumulator is constructed (back to front) the list becomes reversed.
Normally when you look at refactored Prolog code if you see recursion and a base case that looks like
base([],A,A)
where one of the arguments is an empty list or bottom, and two other parameters are the same, but one is bound when the call is made and the other is unbound when the call is made, look to see if accumulator passing has been factored into the code.
Upvotes: 2
Related Questions
- BFS same way different result (python)
- Unable to figure out the bug in BFS
- Breadth First Search in Prolog
- CSR and BFS always finds with 0 steps
- Breadth first search in prolog gives me an error
- Inconsistent results in BFS in Java
- Prolog breadth-first search (BFS)
- What's wrong with my Breadth First Search Algorithm
- Code is not traversing correctly when using BFS
- Trying to implement simple BFS in python...Not able to print the value if search is successful