2

this might be a simple problem but I need to do it differently. The problem is that I have to find in prolog the possible routes of airflights. I have this knowledge base

from_to(fresno,seattle).
from_to(fresno,albany).          
from_to(albany,dallas).     
from_to(fresno,boston). 
from_to(dallas,seattle).         
from_to(dallas,albany).
from_to(seattle,dallas).           
from_to(seattle,omaha).         
from_to(atlanta,albany).
from_to(atlanta,dallas).
from_to(atlanta,boston).
from_to(omaha,atlanta).         
from_to(omaha,albany).
from_to(albany,seattle).

And I have to make a predicate route(X,Y) that checks if we can go from X to Y. What I did is this:

route(X,Y):-from_to(X,Y).
route(X,Y):-from_to(X,Z), route(Z,Y).

But it doesn't work because the graph is cyclic. I searched on the internet and the only thing everyone said is to use a list and check the visited paths. But I can't use lists! I have to make a predicate route(X,Y) without using lists, how can I accomplish this without a list? Thank you

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
SasukeItachi UchihaClan
  • 49
  • 1
  • 1
  • 7

4 Answers4

1
route(X0,X) :-
   from_to(X0,X1),
   closure0(from_to,X1,X).

See this question for a definition of closure0/3.

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
  • thank you for your answer but this still uses lists, I am asking if it is possible without lists, it is surely an easy problem because it is the first exercise but I simply can't do it. – SasukeItachi UchihaClan Nov 26 '14 at 22:59
  • @SasukeItachiUchihaClan: You can do it with assert, but this is extremely error prone! – false Nov 26 '14 at 23:00
  • thanks for the information, the exercise is really simple but I don't know how to do it,this is really frustrating... – SasukeItachi UchihaClan Nov 27 '14 at 00:51
  • @SasukeItachiUchihaClan: Just to be clear: By using this solution you are using a meta-predicate providing a higher-order solution for the reflexive-transitive closure operator. Lists? As far as you are concerned there are no lists - and they could be easily replaced by, say, trees! – false Nov 27 '14 at 15:32
1

If you are not strictly required to use SWI-Prolog, you can easily do this in a Prolog system with tabling support. In B-Prolog, I just added :- table route/2. and now it works:

?- route(fresno, omaha).
yes

?- route(fresno, fresno).
no

?- route(atlanta, atlanta).
yes

?- route(atlanta, X).
X = albany ?;
X = dallas ?;
X = boston ?;
X = seattle ?;
X = omaha ?;
X = atlanta
yes
Sergii Dymchenko
  • 6,890
  • 1
  • 21
  • 46
1

So you can't use lists (I wonder why) but can you use a counter variable? Try iteratively deepening search where you do depth-first search first in the depth of 1, then 2, and so on. That would prevent the infinite loops with cycles.

Remember to have an upper limit for search depth to avoid infinite looping in case where there is no connection.

drippingtap
  • 32
  • 3
0

I would try

:- dynamic visited/1.

route(X,Y) :- retractall(visited(_)), route_(X,Y).
route_(X,Y) :- from_to(X,Y).
route_(X,Y) :- from_to(X,Z), \+ visited(Z), asserta(visited(Z)), route_(Z,Y).

test:

1 ?- route(fresno, omaha).
true ;
false.

2 ?- route(fresno, omaha).
true ;
false.

3 ?- route(fresno, fresno).
false.

4 ?- route(atlanta, atlanta).
true ;
false.

Since the graph is defined in source code, an alternative could be:

:- dynamic from_to/2.

route(X,Y):-retract(from_to(X,Y)).
route(X,Y):-retract(from_to(X,Z)), route(Z,Y).

but after the first call, a reload of the KB is needed.

CapelliC
  • 59,646
  • 5
  • 47
  • 90