صفحه 1:
An example (Clocksin and Mellish)
Searching a maze
Problem:
\We need to enter a palace that has many rooms to
look for a phone which is in one of the rooms.
Solution:
We go from room to room to get to a room that has
hone.
0 3 boing around in cycles, we keep a record of the rooms tf
sit. We use the list of rooms visited and every time we go t
we check the list to make sure it is not on the list.
2 to a room that we have visited before, we go back to th¢
us room and try a different room to go to.
If there are no rooms to go to from the current room
then we backtrack to the previous room to try a
صفحه 2:
An algorithm
1. Go to the door of a room
2. If the room is on the list of rooms visited, ignore
the
room and go to 1.
3. Add the room to the list of rooms visited
4. Look for a telephone in the room
5. If there is no telephone, go to step 1.
Otherwise, stop and the list has the path that we
took to come to
the correct room.
Lecture 23 Maze
Searching/Farmer, Goat,
SE Oe زر 27
صفحه 3:
Representing the
information about the
doors and the room d
containing a phone as a
series of facts:
door(a, b).
door(b, c).
door(b, e). 9
door(c, d).
door(d, e). 72
door(e, f).
door(e, g).
hasphone(g).
Lecture 23 Maze
hing/Farmer, Goat,
> لوج و اجو رو
صفحه 4:
go(X, X, T). % we are already there
go(X, Y, T) :- door(X, Z), % there is a door from X to Z
not(member(Z, T)), % Z not visited before
go(Z, Y, [Z|T]). % go from Z to Y and
add Z to the list
s this complete?
?- go(b,g,t J).
Yes
?- go(d,b,[ ۰
No
Why?
1001-5 are one way doors 272
ccording to the facts
epresenting them.
Lecture 23 Maze 4
hi G
صفحه 5:
Solution 1
Instead of declaring duplicate facts for each door
we can use an
هدع گس ها
“door(a, b).
door(b, c).
door(b, e).
door(c, d). toe b 5
door(d, e).
door(e, f). 3
door(e, g). 72
hasphone(g).
go(X, X, T).
go(X, Y, T) :- door(X, Z), not(member(Z, T)), go(Z, Y,
(Z|T)).
go(X, Y, T) :- door(Z, X), not(member(Z, T)), go(Z, Y,
TIT).
صفحه 6:
Solution 2
We can use disjunction.
go(X, X, T).
go(X, Y, T) :- (door(X, Z); door(Z, X)),
not(member(Z, T)), go(Z, Y,
(Z|T]).
we nave to be Carerul NOt to lorget tne brackets
around the disjoined goals. Not using the brackets:
go(X, Y, T) :- door(X, Z); door(Z, X),
not(member(Z, T)), go(Z, Y,
Z|T)).
mena 0
go(X, Y, T) :- door(X, Z);
( door(Z, X), not(member(Z, T)), go(Z, Y,
[Z|T)) ).
جر is incorrect and certainly not what we meant.
Lecture 23 Maze 6
Searching/Farmer, Goat,
SE Oe زر 27
صفحه 7:
ing to the room where there is a phone.
get_to_phone(X,Y):- go(X, Y, [ ]), hasphone(Y)
?- get_to_phone(a,Y).
۲ 9
Yes
The solution obove uses a strategy known as the
“generate and test” strategy. A possible solution is
generated and then tested until a solution is found or
no more possible solutions can be generated. In the
maze example the “go” clause generates solutions and
“hasphone” clause is used to test the generated
krmassitie roth qisondhe dS emeratadhddestgone atiegytis, tl
uthowieveringpfreffiaieoia to room. The above rule would the
een written as:
st_to_phone(X,Y):-hasphone( Y ), go( X, Y, [ ]).
Lecture 23 Maze z
Searching/Farmer, Goat,
SE Oe زر 27
صفحه 8:
The Russian Farmer Problem
Lecture 23 Maze
hi
صفحه 9:
(F,W,G,C)
41101 1
£ 1 1
rl) @LL) @ br) با یام
|
G@LLy (Lr, 1)
|
Mea 1¥ (Lr) 0
iS es 1 1 1
arr) Gri SC ie) دبای
yin) 117)
سوه ی fy
rely) 02 517 5 11 (r, 1,1, r)
aoe in (aren aed
allo Ga Darla) Pa Lees
1, r) و گرا erie
(rr, Lr) ۳, r) a r, Yr),
Pt)
Lecture 23 Maze 9
hi 6
صفحه 10:
(F,W,G,C)
0
0 1 ely
Ge)
(E02, 1 ا 8
Gra ١ (Pia 0
رل رام (Bp)
0 ae “Gn Te)
صفحه 11:
go(Start,Target):-
path(Start, Target,[Start],Path),
write(‘A solution is:’),nl,
write_path(Path).
path(Start, Target, Visited, Path):-
move(Start, NextNode), %
Generate a move
not( unsafe(NextNode) ), % Check
that it is safe
not( member(NextNode, Visited) ), %
Check for recurrence
path(NextNode, Target,[NextNode |Visited],Path),!.
nath(Taraqet Tarcet Path Path) 0, Raarhad the.
