Prolog - Route

Author

Route

emced

2006-01-10, 4:10 am

Dear all,

I am working on the following problem and stuck at this level. Can any
one please tell me how the above rules and facts can be extended to
find the routine route from point X to Y and the following facts and
rules can be extended to find the quickest route from X to Y including
the delay time in different locations to travel time?

route(S, S, R).
route(S, D, R) :- (link(S, Z, _, _) ; link(Z, S, _, _)),
legal(Z, R), route(Z, D, [Z|R]).

legal(X, []).
legal(X, [H|T]) :- \+ X = H, legal(X, T).

Format: link(<from>, <to>, <road_name>, <distance> ).

Can any one please tell me how the above rules and facts can be
extended
to find the routine route from point X to Y and the following facts and
rules
can be extended to find the quickest route from X to Y including the
delay time in different locations to travel time?

route(S, S, R).
route(S, D, R) :- link(S, Z, _, _, _), legal(Z, R), route(Z, D, [Z|R]).

legal(X, []).
legal(X, [H|T]) :- \+ X = H, legal(X, T).

Format: link(<from>, <to>, <road_name>, <distance>, <time> ).

where the <time> is the time in seconds to travel the distance.

Format: locn(<loc_name>, <grid_ref>, <delay> ).

<delay> is the average transit time in seconds.

Thank you. - emced

Happy New Year 2006.

Marco Gavanelli

2006-01-10, 4:10 am

emced wrote:
> Dear all,
>
> I am working on the following problem and stuck at this level. Can any
> one please tell me how the above rules and facts can be extended to
> find the routine route from point X to Y and the following facts and
> rules can be extended to find the quickest route from X to Y including
> the delay time in different locations to travel time?
>
> route(S, S, R).
> route(S, D, R) :- (link(S, Z, _, _) ; link(Z, S, _, _)),
> legal(Z, R), route(Z, D, [Z|R]).

I think there are a few errors, in your code.
For example, the first fact says that in order to go from one city to
the very same city, you can take any possible route you might imagine.
For example, in order to go from Ferrara to Ferrara, you might go to
Venice, Paris, London, Moscow, and then you stop.
I think you should say that in order to go from one place to the same
place, you don't need any route: you are already there.

The second rule says that you can go from S to D using the route R,
provided that you can go to Z, and that from Z you can take a route to
D. But, you also say that the total route from Z to D is longer than the
route from S to D!

> Can any one please tell me how the above rules and facts can be
> extended
> to find the routine route from point X to Y and the following facts and
> rules
> can be extended to find the quickest route from X to Y including the
> delay time in different locations to travel time?

If you want to optimise with respect to some objective function, you
might consider moving to CLP. In CLP you have the minimize predicate.

If you want to use pure Prolog, you might consider the following
implementation (although it is not very efficient):

A route R from S to D is the quickest one if two conditions are met:
1. R is indeed a route from S to D
2. there is no route R1 which is a route from S to D, and which is
quicker than R.

I hope this can help you.

Best,
Marco

--
http://www.ing.unife.it/docenti/MarcoGavanelli/

emced

2006-01-10, 4:10 am

Dear Marco / all

Many thanks for the reply and the help you provided. I have moved on
with the resolution of the problem as you can see below. I have been
able to solve the route problem code as given hereafter. But I am still
not able to get Prolog code to make the application do the following.

"Print the route R along with the bus number, which is given as
argument N in link (S,Z,N,M) and link(Z,S,N,M)."

route(S, S, R).
route(S, D, R) :- (link(S, Z, _, _) ; link(Z, S, _, _)),
legal(Z, R), route(Z, D, [Z|R]).

legal(X, []).
legal(X, [H|T]) :- \+ X = H, legal(X, T).

Format: link(<from>, <to>, <road_name>, <distance> ).

"Can anyone please tell me how the above rules and facts can be
extended
to find the routine route from point X to Y and the following facts and
rules
can be extended to find the quickest route from X to Y including the
delay time in different locations to travel time?"

route(S, S, R).
route(S, D, R) :- link(S, Z, _, _, _), legal(Z, R), route(Z, D, [Z|R]).

legal(X, []).
legal(X, [H|T]) :- \+ X = H, legal(X, T).

Format: link(<from>, <to>, <road_name>, <distance>, <time> ).

where the <time> is the time in seconds to travel the distance.

Format: locn(<loc_name>, <grid_ref>, <delay> ).

<delay> is the average transit time in seconds.

Thank you very much for your appreciated help. Happy New Year 2006 and
all the best to you

- emced

Marco Gavanelli

2006-01-10, 4:10 am

emced wrote:
> Dear Marco / all
>
> Many thanks for the reply and the help you provided. I have moved on
> with the resolution of the problem as you can see below.

Dear emced,

the code you provide here is not different from the one you posted
earlier. Have you tried it? I believe it will not give the answer you
expect.

> I have been
> able to solve the route problem code as given hereafter. But I am still
> not able to get Prolog code to make the application do the following.
>
> "Print the route R along with the bus number, which is given as
> argument N in link (S,Z,N,M) and link(Z,S,N,M)."

Once you make your code work, this extension is very easy: instead of
providing the list of places as third parameter of "route", you should
provide the list of buses. Then, in the "legal" predicate, you should
check that you do not take twice the same bus (instead of checking
you're not passing twice in the same place).

Cheers,
Marco

--
http://www.ing.unife.it/docenti/MarcoGavanelli/

emced

2006-01-10, 4:10 am

Thank you Marco for your kind help. -emced

Sponsored Links