3

I have an example problem in Answer Set Programming (ASP). When I try to make the equivalent code in Prolog, I keep getting stuck with the not blocked.

This is the ASP code:

road(berlin,potsdam).
road(potsdam,werder).
road(werder,brandenburg).
road(X,Y) :- road(Y,X).

blocked(werder,brandenburg).

route(X,Y) :- road(X,Y), not blocked(X,Y).
route(X,Y) :- route(X,Z), route(Z,Y).

drive(X) :- route(berlin,X).

#show drive/1

The answer is: drive(potsdam), drive(werder), drive(berlin).

In Prolog, I initially thought it would be as simple as changing the not to \+. When I query drive(X)., it recursively generates the X = potsdam answer. I know that Prolog and ASP work differently but I just can't figure it out.

RandomEli
  • 1,527
  • 5
  • 30
  • 53
becky
  • 33
  • 4

1 Answers1

2

The problem is road(X,Y) :- road(Y,X). This will recurse forever if there is no match among the facts:

is road(X,Y)?
is road(Y,X)?
is road(X,Y)?
is road(Y,X)? 
.....

You can replace the predicate:

road(X,Y) :- road(Y,X).

with

road(X,X).

and add:

reachable(X,Y):-
     road(X,Y)
  ;  road(Y,X).

and modify:

route(X,Y) :- road(X,Y), \+ blocked(X,Y).

to:

route(X,Y) :- reachable(X,Y), \+ blocked(X,Y).
false
  • 10,264
  • 13
  • 101
  • 209
Limmen
  • 1,407
  • 11
  • 17
  • 1
    If you add road(werder,city). it does not give as a result city ,as it should. – coder Aug 23 '16 at 17:59
  • Your right, was to quick on the update. The previous version still works but gives duplicate answers. – Limmen Aug 23 '16 at 18:05