[eclipse-users] Minimum cost path and branch-and-bound

From: Francesco Santini <safran.f_at_gmail.com>
Date: Tue, 25 Mar 2008 17:16:55 +0100
Hi everybody,

I am an ECLiPSe newbie even if I have some experience with Prolog.
I need to compute the minimum cost path from a node A to a node B.
My Prolog code could be something very simple like:

-
edge(n0, n1, 1).
edge(n1, n2, 6).
edge(n1, n3, 2).
edge(n1, n4, 3).
edge(n2, n4, 5).
edge(n3, n5, 9).
edge(n3, n6, 5).
edge(n4, n5, 2).
edge(n4, n9, 3).
edge(n5, n7, 1).
edge(n5, n8, 1).

path(X, Y, C):-
  edge(X, Y, C).

path(X, Y, C):-
  edge(X, Z, C1),
  path(Z, Y, C2),
  C is C1 + C2.

allpath(X, Y, L):-
  findall(C, path(X, Y, C), L).
-

Given the query: allpath(n0,n9,L) it returns the list [15,7], i.e. the
list of the costs of all the possible paths going from n0 to n9.

I would like to use ECLiPSe to apply the branch-and-bound technique to
the cost of the path in order to speed up the search (for a wider
network) and find the best path between two given nodes (minimum cost
path).
Clearly, replacing the above allpath clause with

searchpath(X, Y, C):-
  bb_min( path(X, Y, C), C).

(from library(branch_and_bound)) does not work (I have put it only to
show what I want to obtain).
I think I should rewrite the cost (i.e. C) of the path as a constraint
in order to apply branch-and-bound on it, but I have some problems in
rewriting the problem as a (ECLiPSe ) *constraint* problem instead of
a Prolog problem.

Is there any code examples that are already available for this
(simple) problem? Just to understand how it can be written.....

Thanks a lot,



     Francesco
Received on Tue Mar 25 2008 - 16:17:02 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET