Path Finding

23 views
Skip to first unread message

Alin Roman

unread,
Jul 2, 2018, 12:32:36 PM7/2/18
to SWI-Prolog
I'm new to Prolog and I'm struggling doing a task. So, we have 2 types of edges, one for car and one for bus. They are symmetrical. There is no distance, just direction. For example:
car(berlin, munich).
car(berlin, stuttgart).
car(mainz, munich).

bus(augsburg, berlin).
bus(köln, dortmund).
bus(dortmund, stuttgart).

My task is to find if there is a path between a 'Start' and 'End Location', which has been resolved but now comes the "hard" part. We have to find a path that changes max ONE time between bus and car. Also if I'm in a bus I have to get to my end location just within buses or change one time the bus with a car(of course we can then change between cars, but not back to bus).

Also I've found a way to find the path but just for bus paths, not cars and it looks like this.

isPath(from, to) :- isPath(from, to, []).
isPath(from, to, _) :- bus(from, to).
isPath(from, to, visited) :- 
   \+ member(from, visited),
   bus(from, X),
   isPath(X, to, [from|visited]).

I'm sure it is not that hard, I just have to save somehow the fact that the bus/car has been changed with the other one.

Can someone help me?

Thanks!

Carlo Capelli

unread,
Jul 2, 2018, 12:39:48 PM7/2/18
to Alin Roman, SWI-Prolog
Dear Alin, I feel that giving you a solution is not good for your apprenticeships...
Just to start, try to understanding your code (using ?- trace.) *after* you properly changed atoms to *variables*, for instance
isPath(From, To) :- isPath(From, To, []).
etc

HTH, ciao


--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

Martin

unread,
Jul 2, 2018, 12:41:46 PM7/2/18
to swi-p...@googlegroups.com
First, have you tried if actually find the connection from augsburg to
berlin? Try the query isPath(augsburg, berlin) and see why this does not
give any results. Hint: variable names start with capital letters.

You could add one more argument to isPath/3 and make it remember the
history (this is just a sketch, you need to fix the bug i mentioned
above first):

isPath(from, to, visited, only_bus) :-
\+ member(from, visited),
bus(from, X),
isPath(X, to, [from|visited], only_bus).

isPath(from, to, visited, only_car) :-
\+ member(from, visited),
car(from, X),
isPath(X, to, [from|visited], only_car).

and add soem rule that allows to switch from car to bus.

good luck,
Martin
> --
> You received this message because you are subscribed to the Google
> Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to swi-prolog+...@googlegroups.com
> <mailto:swi-prolog+...@googlegroups.com>.
Reply all
Reply to author
Forward
0 new messages