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

Date: Tue, 25 Mar 2008 20:16:36 +0000

Date: Tue, 25 Mar 2008 20:16:36 +0000

Joachim Schimpf (Independent Contractor) wrote: > 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) Sorry, that answer was probably unhelpful... Although it works, it will not give you any speedup: the search tree will only be pruned at its leaves, i.e. when a complete path to the destination has been found and the cost variable becomes instantiated. To get earlier pruning, you will indeed need to change the distance computation to use constraints, so that the cost bound can be applied to partially computed path costs. Simply add :- lib(ic). for using the ic constraint solver. Then you have to change the "lazy" computation of the cost (after the choices have been done) into an eager one (before the choices are done), by moving it to the left and by using constraints instead of ground arithmetic: path(X, Y, C):- C1 #>= 0, C2 #>=0, C #= C1+C2, edge(X, Z, C1), path(Z, Y, C2). If you now run bb_min(path(n0, n9, C), C, _) with the Query->PortProfile option in tkeclipse, you can see that the number of calls (and exits) to edge/3 has been reduced significantly: PREDICATE CALLER call exit fail *exit redoresume delay next edge /3 path /3 24 7 17 6 6 . . 2 compared to the naive code: edge /3 path /3 36 11 25 8 8 . . . In your example, calls to edge/3 correspond to nodes of the search tree. -- JoachimReceived on Tue Mar 25 2008 - 20:16:47 CET

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