Logic Programming Prolog 5
اسلاید 1: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem1If there are no rooms to go to from the current room then we backtrack to the previous room to try a different alternative. An example (Clocksin and Mellish)Searching a mazeProblem: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 a phone.To avoid going around in cycles, we keep a record of the rooms that we visit. We use the list of rooms visited and every time we go to a room we check the list to make sure it is not on the list. If we go to a room that we have visited before, we go back to the previous room and try a different room to go to.
اسلاید 2: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem21. 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 visited4. Look for a telephone in the room5. 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. An algorithm
اسلاید 3: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem3Representing the information about the doors and the room containing a phone as a series of facts: door(a, b). door(b, c). door(b, e). door(c, d). door(d, e). door(e, f). door(e, g). hasphone(g).
اسلاید 4: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem4go(X, X, T). % we are already therego(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 Is this complete?Doors are one way doorsaccording to the facts representing them. ?- go(b,g,[ ]).Yes?- go(d,b,[ ]).NoWhy?
اسلاید 5: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem5Solution 1Instead of declaring duplicate facts for each door we can use an additional rule.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, [Z|T]). door(a, b). door(b, c). door(b, e). door(c, d). door(d, e). door(e, f). door(e, g). hasphone(g).
اسلاید 6: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem6We have to be careful not to forget the 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]). would mean go(X, Y, T) :- door(X, Z); ( door(Z, X), not(member(Z, T)), go(Z, Y, [Z|T]) ). which is incorrect and certainly not what we meant.Solution 2We 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]).
اسلاید 7: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem7get_to_phone(X,Y):-hasphone( Y ), go( X, Y, [ ] ).get_to_phone(X,Y):- go(X, Y, [ ]), hasphone(Y) If we knew where the phone was, we would have gone directly there without wondering from room to room. The above rule would then have been written as:?- get_to_phone(a,Y).Y = g YesThe 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 possible solutions. The “Generate and test” strategy is, however, not efficient.Going to the room where there is a phone.
اسلاید 8: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem8The Russian Farmer Problem
اسلاید 9: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem9(F,W,G,C)(l, l, l, l)(r, r, l, l) (r, l, l, l) (r, l, r, l)(r, l, l, r)(l, l, l, l) (l, l, r, l) (r, r, r, l) (r, l, r, l)(r, l, r, r)(l, r, r, l) (l, r, l, l) (l, l, r, l) (l, l, r, r) (l, l, l, r) (l, l, r, l)(r, r, r, l) (r, r, l, r) (r, r, l, l) (r, l, l, r) (r, r, l, r) (r, l, r, r)(l, l, l, r) (l, r, l, l) (l, r, l, r) (l, l, l, r) (l, r, l, r) (l, r, l, l)(r, r, l, r) (r, r, r, r) (r, r, r, r) (r, r, l, r)XXXXXXXXXXXXXXXXXXX
اسلاید 10: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem10(F,W,G,C)(l, l, l, l)(r, l, r, l)(l, l, r, l) (r, r, r, l) (r, l, r, r)(l, r, l, l) (l, l, l, r) (r, r, l, r) (r, r, l, r) (l, r, l, r) (l, r, l, r) (r, r, r, r)
اسلاید 11: Lecture 23 Maze Searching/Farmer, Goat, Cabbage and Wolf Problem11path(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),!.path(Target, Target,Path,Path). % Reached the goalgo(Start,Target):- path(Start, Target,[Start],Path), write(‘A solution is:’),nl, write_path(Path).
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.