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

Francesco Santini wrote:
> 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 

Yes it does - have you not tried?

?- bb_min(path(n0, n9, C), C, _).
Found a solution with cost 15
Found a solution with cost 7
Found no solution with cost -1.0Inf .. 6
C = 7
Yes (0.00s cpu)


-- Joachim