Home > Archive > Prolog > October 2006 > programming problem
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
programming problem
|
|
| joseph.rivers@yahoo.com 2006-10-01, 7:02 pm |
| Suppose that I had a bunch of predicates of the form
r(a1,a2).
r(a2,a3).
r(a3,a1).
r(a4,a1).
r(a3,a2).
....
and I defined
relation(X,Y) :- r(X,Y) ; r(Y,X).
Given a and b, how would I compute the smallest number n such that
there exists a sequence x1=a, x2, ..., xn=b with relation(x1,x2) &
relation(x2,x3) & ... & relation(xn-1, xn) = True?
| |
| russell kym horsell 2006-10-02, 4:03 am |
| joseph.rivers@yahoo.com wrote:
} Suppose that I had a bunch of predicates of the form
} r(a1,a2).
} r(a2,a3).
} r(a3,a1).
} r(a4,a1).
} r(a3,a2).
} ...
} and I defined
} relation(X,Y) :- r(X,Y) ; r(Y,X).
} Given a and b, how would I compute the smallest number n such that
} there exists a sequence x1=a, x2, ..., xn=b with relation(x1,x2) &
} relation(x2,x3) & ... & relation(xn-1, xn) = True?
This is called "the shortest path problem". There is an extensive
literature. Dijkstra and a couple Hungarians did some work on it. :)
If the relation commutes (as for your case) -- i.e. it's adjacency matrix
is symmetric -- there are some simplifications and you save maybe 1/2
the work. :)
| |
| Hans Aberg 2006-10-02, 7:03 pm |
| In article <efq76s$6lq$2@chessie.cirr.com>, russell kym horsell
<kym@ukato.freeshell.org> wrote:
> joseph.rivers@yahoo.com wrote:
> } Suppose that I had a bunch of predicates of the form
> } r(a1,a2).
> } r(a2,a3).
> } r(a3,a1).
> } r(a4,a1).
> } r(a3,a2).
> } ...
> } and I defined
> } relation(X,Y) :- r(X,Y) ; r(Y,X).
> } Given a and b, how would I compute the smallest number n such that
> } there exists a sequence x1=a, x2, ..., xn=b with relation(x1,x2) &
> } relation(x2,x3) & ... & relation(xn-1, xn) = True?
>
> This is called "the shortest path problem". There is an extensive
> literature. Dijkstra and a couple Hungarians did some work on it. :)
> If the relation commutes (as for your case) -- i.e. it's adjacency matrix
> is symmetric -- there are some simplifications and you save maybe 1/2
> the work. :)
Also see:
http://en.wikipedia.org/wiki/Shortest_path_problem
--
Hans Aberg
|
|
|
|
|