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]
--------------------------------------------------------------------
