Help with a breadth first search in prolog.
ajpowe...@googlemail.com
stuck! The task is a maze, at each node is a sound level the higher
the sound the closer the the exit you are. I have written a lot of
code for this task so far which I will post if anyone actually replys
to this message (prolog seems to be a hard area to get help for
online!)
Would anyone be able to help me get the solution to the task?
Chip Eastham
I'm not sure if breadth-first entirely explains what
one wants to do in a maze search task. Of course, if
that is in some sense a requirement of your coding,
then so be it. However I'd think a more natural
requirement would be that the path not "self-intersect".
Is that of some assistance?
regards, chip
Nick Wedd
<cfb27fa3-bc66-4489...@e10g2000prf.googlegroups.com>,
ajpowe...@googlemail.com writes
Does your solution work if you leave out the bit about the sound level?
(You have asked "I have written a program with at least one bug in it,
please help me to find the bug". I am doing my best.)
Nick
/--
Nick Wedd ni...@maproom.co.uk
ajpowe...@googlemail.com
> In message
> <cfb27fa3-bc66-4489-8964-9ff52ab4e...@e10g2000prf.googlegroups.com>,
> ajpowerran...@googlemail.com writes
>
> >I am trying to do a task I found on breadth first searchs but am
> >stuck! The task is a maze, at each node is a sound level the higher
> >the sound the closer the the exit you are. I have written a lot of
> >code for this task so far which I will post if anyone actually replys
> >to this message (prolog seems to be a hard area to get help for
> >online!)
>
> >Would anyone be able to help me get the solution to the task?
>
> Does your solution work if you leave out the bit about the sound level?
>
> (You have asked "I have written a program with at least one bug in it,
> please help me to find the bug". I am doing my best.)
>
> Nick
> /--
Thanks for the reply, I am new at prolog. The task is meant to sort
the nodes by noise level and then output the quickest path from the
start of the maze to the end, this is the error i get when i run the
code: uncaught exception: error(existence_error(procedure,path/
3),findall/3)
Chip Eastham
Perhaps you've written a subgoal involving findall/3
which invokes solutions to path/3, but that predicate
(at least with arity 3) does not exist??
Certainly check your code for occurrences of findall,
and see if one of these matches the error message.
regards, chip
ajpowe...@googlemail.com
Thanks for the reply. Here is a section of the code that may make the
problem easier to solve:
solve(Start, Finish, Solution) :-
breadthfirst([[Start]], Finish, Solution).
breadthfirst([[Finish | Path ]], Finish, [Finish|Path]).
breadthfirst([Path | Paths], Finish, Solution) :-
extend(Path, NewPaths),
sortPath(NewPaths, Results),
append(Paths, Results, Paths1),
breadthfirst(Paths1, Finish, Solution).
extend([Node | Path], NewPaths) :-
findall([NewNode, Node |Path],
(path(Node, NewNode, Path),
not(member(NewNode, [Node | Path]))), NewPaths), !,
extend(Path ,[]).
findall(X,Goal,Xlist) :-
call(Goal),
assertz(queue(X)),
fail;
assertz(queue(bottom)),
collect(Xlist).
collect(L) :-
retract(queue(X) ) , !,
(X == bottom, !, L=[]
;
L=[X | Rest], collect(Rest) ).
I have the findall procedure so why do i get the error? and how can io
solve it?
Chip Eastham
My concern was not that findall is undefined (it is a builtin
predicate for most Prologs), but rather that path/3 is not
defined. Notice that findall, as invoked by extend/2, will
supply the compound goal:
(path(Node, NewNode, Path), not(member(NewNode, [Node | Path])))
Your code snippet shown above does not define path/3, but
I'd guess that what you want is for it to find NewNode
adjacent to Node (the rest of the compound goal being
a check to see that NewNode is distinct from the nodes
previously "visited" by Path.
But since Path is being passed as an argument to path/3,
I think it makes more sense to formulate a predicate
that combines both finding NewNode adjacent to Node
and checking NewNode is distinct from previous nodes
on Path.
regards, chip
ajpowe...@googlemail.com
Thanks, I am really new to prolog and that went over my head lol could
you help me get started with this please?
Chip Eastham
Let's start with what the standard findall/3 predicate
is supposed to do. The slash-3 means "this predicate
has three arguments".
findall(Instance,Goal,List)
The Instance here is a variable or term containing
variables that appear within the Goal expression.
findall succeeds by binding List to a list of all values
to which Instance binds when Goal succeeds. Typically
Goal is a nondeterministic predicate, meaning it
can succeed in more than one way, and thus List gets
to be a list of length greater than 1. However Goal
might not succeed at all, in which case List is an
empty list, or it might succeed in just one way
(determinism), in which case List has length 1.
Example: Suppose we have a fact-like predicate:
edge(a,b).
edge(b,c).
edge(c,d).
Then we could ask for:
findall(X:Y,edge(X,Y),List).
and get the result:
List = [a:b,b:c,c:d]
The items of the list have the same form as the
first argument of findall/3.
What you coded was a bit tricky in assigning a
compound goal (a goal with subgoals) to the second
argument. This is where your predicate path/3
comes in:
findall(
[NewNode, Node |Path],
(path(Node, NewNode, Path), not(member(NewNode, [Node | Path]))),
NewPaths )
as part of the Goal argument to findall.
So, how did you define predicate "path" (if you
did), and which version of Prolog are you using?
It seems strange that you found it necessary to
write an implementation of findall/3 for your
program.
regards, chip
Nick Wedd
<9e14cc38-bc72-449e...@s19g2000prg.googlegroups.com>,
ajpowe...@googlemail.com writes
Does the noise propagate along the passages, so that it will increase,
or at least not decrease, as we take the correct path to the exit? Or
does it propagate over the walls, so that it will be almost useless as a
guide? If the former, a breadth-first search, exhaustively searching
routes which we know are wrong, seems daft. If the latter, I recommend
ignoring the noise level.
As for your error message - Chip Eastham has now explained it.
Nick
--
Nick Wedd ni...@maproom.co.uk
ajpowe...@googlemail.com
> ajpowerran...@googlemail.com writes
At each node in the maze the noise level is different the higher it is
the closer to the exit your getting.