How to find list of shortest length from an infinite set (Prolog)

Question

I have a Prolog function path(A,B,Path) that yields all the valid paths on a board from A to B.

The output of this function looks like this:

?- path(0,2,Path).
Path = [0, 1, 2] ;
Path = [0, 3, 2] ;
Path = [0, 1, 4, 2] ;
Path = [0, 3, 4, 2] ;
Path = [0, 1, 4, 5, 3, 2] ;

etc, etc.

It generates an infinite set of lists containing valid paths. I would simply like to get the shortest of these paths (however many there are). That is, I want a function shortest(A,B,Path) that wil yield the shortest valid paths on a board from A to B.

The output I want is:

?- shortest(0,2,Path).
Path = [0, 1, 2] ;
Path = [0, 3, 2] ;
false.

I've been playing around with the setof function in Prolog to bind all of the paths to a set where I impose some length restriction on it, but I haven't gotten that to work yet.

My poor work so far looks like this. It's definitely wrong, and I'd appreciate any help understanding how setof works and how I can find the shortest lists from this set. Thanks!

shortest(A,B,MinPath) :-
    setof(Path,path(A,B,Path),MinPath),
    min(length(Path), length(MinPath)).

false · Accepted Answer · 2020-03-03T14:44:46.400

This is a classical case for iterative deepening. Just enter at the toplevel:

?- length(Path, N), path(0, 2, Path).

The first answer will be of shortest length. And that's what you can do in Prolog very elegantly: You are starting to enumerate an infinite set, hoping that you will find what you are searching for after a finite amount of time.

Since probably all paths of that length are of equal interest to you, you want all of them. Otherwise, you be happy with above. Also, you might enumerate the shortest paths for different nodes, so node/1 should be the nodes occurring in your graph. Say, you have nodes 0 to 10, then node/1 could be defined as:

node(N) :-
   between(0,10,N).

shortest(A,B, Minpath) :-
   setof(Min, Path ^ ( node(A), node(B),
                       once( ( length(Path, Min), path(A, B, Path) ) ) ), [Min]),
   length(Minpath, Min),
   path(A, B, Minpath).

However this solution has a catch ; a very ugly catch, indeed. You said:

(however many there are)

In case there is no path at all, this solution will loop forever. You have been warned.

Edit: For completeness: I assumed that path/3 terminates if the length of the list is fixed.

And to conclude: For a concrete simple graph a more explicit method avoiding cycles is preferable. However, there are many situations where it is not clear at all what a cycle actually is (think of simulating some simple machine), and in such situations, iterative deepening is incredibly effective: No clever thinking in your head, just using the power of Prolog.

There is a final note about looping in case there is no path at all. To overcome this problem you need some kind of resource bounded computation. SICStus Prolog offers library(timeout), other systems have more or less comparable functionality. SWI (recently) introduced call_with_inference_limit/3 (with a quite arcane interface) to this end.

How to find list of shortest length from an infinite set (Prolog)

1 Answers1