Path finding.
* Write a program to find path from one node to another.
* Must avoid cycles
* A template for the clause is
path(start, Finish, Visited, Path).
Start - the name of the starting node.
Finish - the name of the finishing node.
Visited - the list of nodes aready visited.
Path - the list of nodes on the path, including Start and Finish.
Program for finding a Path.
* The search for a path terminates when we have nowhere t0o go.
path {Node, Node,.., [Node]}
A path from start to Finish, starts with a node, X,connected to start followed by a path from X to Finish.
path (Start, Finish, Visited, {Start [ Path]} :-
edge (Start,X),
not (member( X,Visited)),
path(x,Finish, {X [vISITED],Path)
member (X,[X I_ I).
member (X,I_ IYI):- member(X,Y).
Representing the state
Now we returen to the peoblem or rrepresenting tyhe missionaries and cannibals problem;
A State is one "snapshot" in time.
For this problem the only infoemation we need to fully characterize the state is :
the number of missionaries on the left bank,
the number of cannibals on the left bank,
the side the boat is on.
All other information can be deduced from these thres items.
In PROLOG, the state can be representted by a 3-arity term, state (Missionaries,Cannibals, State).
Representing the solution
The solution consists of a list of moves, e.g.
[move( I.I. right), move 2.0, lift)].
We take this to mean that I missionary and i cannibal moved to the right bank, then 2 missionaries moved to hte left bank.
Like the graph search problem, we must avoid returing to state we have visited before.
The visited list will have the form:
[Most Recent State I list of previousstates]
Overview of solution
We follow a simple graph search procedure:
Start from an initial state
Find a neighbouring state
Check that the now stae has not been visited before
Find a path from the neighbour to the goal.
The search terminates when we have found the state:
PROLOG Code.
% mandc(CurrentState, Visited, Path)
mandc(start(0, 0, right), -,[]).
mande(Currentstate, visited,[Move I Rest O fMoves]):-
newstate (Current state, NestState, Move).
not (member(NestState,Visited)0,
make., move(Current state, NestState, Move),
mande((Nextstate I visited,[Move I Rest O fMoves])
make_move (state(M1,C1,left) state (M2,C2,right) move(M,C,right)) :-
M is M1 - M2.
C is C1 - C2.
make_move(state(M1,C1,right),state(M2,C2,right),move M,C,left)) :-
M is M2 -M1
C is C2 - C1.
A move is characterized by the nummber of missionar5ies and the number of canniblls taken in the boal at6 one time.
Since the boat can carry no more than two peopel at once, the only possible combinations are:
carry (2,0)
carry (1,0)
carry (1,1)
carry (0,1)
carry (0,2).
Where carry (M,C) means the boat will carry M, missionaries and C.cannibals on one trip.
Feasible Moves
*Once we hafe found a possible move, we have to confirm that it is feasible It is not feasible to move more missionaries or more cannibals than that are present on one bank.
When the stae is stae(M1,C1,left) and we try carry (M,C)then
*When the state is state(M1, C1, left) and we try carry (M,C) then
M + M1 ≤ AND C + C1 ≤ 3
must be true.
Legal Moves.
* Once we have found a feasible move, we must check that it is legal, i.e no Missionaries must be eaten.
legal(X,X).
legal(3,X).
legal(O,X).
*The only safe combinations are when there are equal numbers of Missionaries and cannibals or all the Missionaries are on one side.
Generating the Next State.
newstate(state(M1,C1,left), state(M2,C2,right)):-
carry(M,C),
M ≤ M1
C ≤ C1
M2 is M1 - M2,
C2 is C1 - C,
legal(M2,C2)
newstate(M1, C1, right), state(M2, C2, left)):-
carry(M,C),
M2 is M1 + M,
C2 is C1 + C,
M2 ≤ 3,C2 ≤ 3,
legal(M2, C2).
Thank You Sir. A very good job indeed . Just one question can the same be implemented in C ?
ReplyDeletethnxx a lot dude... you have maintained a good web site.. 10/10
ReplyDeletehow to run this program ?
ReplyDelete