From: Joachim Schimpf (Independent Contractor) <jschimpf_at_cisco.com>

Date: Tue, 25 Mar 2008 17:03:11 +0000

Date: Tue, 25 Mar 2008 17:03:11 +0000

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) -- JoachimReceived on Tue Mar 25 2008 - 17:03:33 CET

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