Hi Eric, Thanks for your reply. But,
1. Jess work fine even when the data has cycle, such as (edge (first 1) (second 2)) (edge (first 2) (second 3)) (edge (first 3) (second 1)) Jess will keep an counter of each fact and avoid infinite loops. 2. What if I only want the node that are reachable from "1", by querying path(1, X) in prolog? In this case we do not want to compute all the conclusions and then querying only paths reachable from "1". I do not know how to achieve this. Thanks again, Senlin On Thu, Aug 28, 2008 at 1:48 AM, Eric Wang-6 <[EMAIL PROTECTED]> wrote: > > I think your code is already close to ideal. It essentially does a > breadth-first expansion over path length, using forward chaining. > > > Senlin Liang wrote: >> >> (defrule pathRule >> (or (edge (first ?first) (second ?second)) >> (and (edge (first ?first) (second ?mid)) >> (path (first ?mid) (second ?second)) >> ) >> ) >> => >> (assert (path (first ?first) (second ?second))) >> ) >> > > You could split this up into two rules, a "base case" and an "induction > case", > just to make it explicit that it's like a mathematical induction. > > (defrule path-base (edge (f ?f) (s ?s)) => (assert (path (f f?) (s s?))) > (defrule path-indu (edge (f ?f) (s ?m)) (path ...) => ...) > > Some potential pitfalls in your code: > > 1. Naming your slots "first" and "second" implies that your edges are > directed. > > 2. If your edge data contains any cyclic loops, this rule will go into an > infinite loop, as well. > (If your data is always directed acyclic, then you're OK.) > > To handle cyclic data, you could add a nodes multislot to your path > template, > and extend your rule to skip any edge whose node is already a member of > the > path's nodes multislot. > > -------- > > I think you're confusing "Jess backward inferences" with "reverse > sequencing" > of your own paths. You happen to build up your paths in reverse order, by > grabbing an existing tail-path (path ?first mid) etc) and prepending a new > head edge before it. That's indeed "backward" within your path domain, but > it's not related to Jess's own forward/backward inferencing mechanism. You > could easily build your paths "forward", e.g. grab a head-path and append a > new tail edge to it, just by switching the "edge" and "path" words in the > "and" > portion of your rule. > > Jess's "forward-chaining" roughly means that it adds new facts like new > layers of an onion: from existing facts (e.g. paths of length N-1 and edges > of length 1), it asserts new facts (paths of length N). Meanwhile, it > caches > (saves in the rete) every fact it found before, so that it never repeats > work > (unless you explicitly retract a fact) -- this is how rete-based reasoners > like > Jess trade off space to save time. > > As a result, Jess can express mathematical induction in a very natural way. > This means Jess can easily give you a nice breadth-first enumeration through > a solution space, which for many small problems is essentially optimal. > You > exploit this correctly by caching all intermediate results in (path) facts > of > length N-1, then prepending to them one at a time. In the field of domain- > independent AI planning, Graphplan introduced a similar forward-chaining > method > to pre-compute its planning graph, which led to some spectacular speed-ups > that > has revitalized AI planning research. > > -------- > > In contrast, Prolog would give you "backward chaining". One way to think of > it is that Prolog diligently constructs a proof tree from top-down (or dies > trying, > haha) per query, then throws that tree away, without memory. "Tree" implies > exponential size, which is always a pitfall -- a bad Prolog algorithm can > indeed > take exponential time. And since backward-chainers like Prolog don't have a > rete > network to cache any intermediate work, they will repeat each search as many > times as you keep asking for it. So you can get a big coefficient on your > exponential time :) > > I once had to debug a bad shortest-path algorithm in Prolog. The "typical" > Prolog-style code resulted in an exponential search for all possible paths. > I rewrote it as a breadth-first expansion, essentially using forward > chaining > (with explicit assertions to mimic a nano-rete), which ran in linear time. > That > cut its computation time down from 2-6 hours to a few milliseconds. > -- > View this message in context: > http://www.nabble.com/JESS%3A-Question-about-backward-inferences-tp19137062p19194584.html > Sent from the Jess mailing list archive at Nabble.com. > > > > -------------------------------------------------------------------- > To unsubscribe, send the words 'unsubscribe jess-users [EMAIL PROTECTED]' > in the BODY of a message to [EMAIL PROTECTED], NOT to the list > (use your own address!) List problems? Notify [EMAIL PROTECTED] > -------------------------------------------------------------------- > > -- Senlin Liang -------------------------------------------------------------------- To unsubscribe, send the words 'unsubscribe jess-users [EMAIL PROTECTED]' in the BODY of a message to [EMAIL PROTECTED], NOT to the list (use your own address!) List problems? Notify [EMAIL PROTECTED] --------------------------------------------------------------------
