I have take this program that implement BFS visit algorithm from Ivan Bratko book: "Programming for Artificial Intelligence".
It's logic is pretty clear form me (I have commented the lines of code with its meaning) but don't work.
My code is:
s(a, b).
s(b, c).
s(c, d).
s(a, d).
% GOAL: il raggiungimento del nodo d:
goal(d).
/* solve(Start, Solution): Solution is a path (in reverse order) from Start to a goal it is TRUE
if it is TRUE breadthfirst(Paths, Solution) (it is TRUE if some path from a candidate set of paths Paths
can be extended to a goal nod. Solution is such an extended path
*/
solve(Start, Solution) :- breadthfirst([[Start]], Solution).
/* breadthfirst([Path1, Path2, ...], Solution) it is TRUE if:
Solution is an extension to a goal of one of the paths in the Paths list of candidates paths
SET CANDIDATES PATH RAPPRESENTATIONS: The set will be represented as a list of paths, and each path will
be a list of nodes in the inverse order; that is, the head will be the most recently generated node, and
the last element of the list will be the start node of the search
*/
/* BASE CASE: If the HEAD of the FIRST PATH (in Paths list) is a GOAL then this path is a Solution of the problem
*/
breadthfirst([[Node|Path]|_], [Node|Path]) :- goal(Node).
/* GENERAL CASE: Otherwise (if the head of the first path is not a goal node) remove the first path from the
candidates set and generate the set of all possible one-step extensions of this paths, add this set of
extension at the end of the candidate set, and execute breath-first search on this updated set
*/
breadthfirst([Path|Paths], Solution) :-
/* Remove the first path from the Paths list and extends it (generate the set of
all possible one-step extensions of this paths that is NewPaths list */
extend(Path, NewPaths),
/* Paths1 = [Paths|NewPaths] */
conc(Paths, NewPaths, Paths1),
/* Execute BFS on Paths1 */
breadthfirst(Paths1, Solution).
/* extended/2 predicate take a Path that is a list of node and generate the set of all possible one-step
extensions of this paths
*/
extend([Node|Path], NewPaths) :- bagof([NewNode, Node|Path],
(s(Node, NewNode), not member(NewNode,[Node|Path]) ),
NewPaths),
!.
extend(Path, []). % bagof failed: Node has no successor
conc([],L,L).
conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).
The problem is that when I try to execute a query it always respond me with FALSE (also if exist a path from a start node X to another note Y)
For example (doing a trace of the situation) I have that:
[trace] ?- solve(a,Solution).
Call: (6) solve(a, _G367) ? creep
Call: (7) breadthfirst([[a]], _G367) ? creep
Call: (8) goal(a) ? creep
Fail: (8) goal(a) ? creep
Redo: (7) breadthfirst([[a]], _G367) ? creep
Call: (8) extend([a], _G443) ? creep
Exit: (8) extend([a], []) ? creep
Call: (8) conc([], [], _G444) ? creep
Exit: (8) conc([], [], []) ? creep
Call: (8) breadthfirst([], _G367) ? creep
Fail: (8) breadthfirst([], _G367) ? creep
Fail: (7) breadthfirst([[a]], _G367) ? creep
Fail: (6) solve(a, _G367) ? creep
false.
As you can see the problem seems occur when it try to extend the current node that is not a goal node (in this case a). Extend a node mean delete the first path from the head of Paths list (the list of candidates paths), and since the elements in this path, create a new list named NewPath containing all the one-step neighbors nodes of these nodes.
Then, using the conc/2 predicate it builds a new Paths1 list of candidates path putting at the end of the Paths list (the old list of candidates paths without the head) the NewPaths list
Then execute breadthfirst on this new list (Paths1)
The problem seems occur when it try to extend the current node because seems the extends/2 predicate don't work well (in fact the NewPath apper void):
extend([Node|Path], NewPaths) :- bagof([NewNode, Node|Path],
(s(Node, NewNode), not member(NewNode,[Node|Path]) ),
NewPaths),
!.
For more information I obtain the following error message when I consult my program:
[debug] ?- consult(bfs).
ERROR: /home/andrea/Documenti/prolog/lezione10/bfs.pl:47:62: Syntax error: Operator expected
Warning: /home/andrea/Documenti/prolog/lezione10/bfs.pl:51:
Singleton variables: [Path]
% bfs compiled 0.00 sec, 160 bytes
true.
Why? Do you have some idea to solve this problem?
