However ... the "generate-and-test" approach is still very memory-intensive and a still-better alternative would be to use the CCP approach implemented by Futtersack and Labat (http://www.droit.univ-paris5.fr/futtersack/english/research/CCP/). Although the approach discussed refers only to a CLIPS implementation, Jess code is also available for download. The basic idea behind CCP is to assert facts only as needed; and backtrack only to sensible alternative search paths. This can reduce memory use substantially and make some problems possible to solve (or possible to solve in reasonable times).
Win
Solutions to $2.00 variant:
Jess, the Java Expert System Shell Copyright (C) 2001 E.J. Friedman Hill and the Sandia Corporation Jess Version 6.1p4 7/8/2003
Solution : 15 pennies, 33 nickels, 2 dimes, 0 quarters, 0 half-dollars Solution : 45 pennies, 1 nickels, 0 dimes, 2 quarters, 2 half-dollars Solution : 40 pennies, 7 nickels, 0 dimes, 1 quarters, 2 half-dollars Solution : 40 pennies, 5 nickels, 1 dimes, 3 quarters, 1 half-dollars Solution : 40 pennies, 4 nickels, 4 dimes, 0 quarters, 2 half-dollars Solution : 40 pennies, 3 nickels, 2 dimes, 5 quarters, 0 half-dollars Solution : 40 pennies, 2 nickels, 5 dimes, 2 quarters, 1 half-dollars Solution : 40 pennies, 0 nickels, 6 dimes, 4 quarters, 0 half-dollars Solution : 35 pennies, 13 nickels, 0 dimes, 0 quarters, 2 half-dollars Solution : 35 pennies, 11 nickels, 1 dimes, 2 quarters, 1 half-dollars Solution : 35 pennies, 9 nickels, 2 dimes, 4 quarters, 0 half-dollars Solution : 35 pennies, 8 nickels, 5 dimes, 1 quarters, 1 half-dollars Solution : 35 pennies, 6 nickels, 6 dimes, 3 quarters, 0 half-dollars Solution : 35 pennies, 5 nickels, 9 dimes, 0 quarters, 1 half-dollars Solution : 35 pennies, 3 nickels, 10 dimes, 2 quarters, 0 half-dollars Solution : 35 pennies, 0 nickels, 14 dimes, 1 quarters, 0 half-dollars Solution : 30 pennies, 17 nickels, 1 dimes, 1 quarters, 1 half-dollars Solution : 30 pennies, 15 nickels, 2 dimes, 3 quarters, 0 half-dollars Solution : 30 pennies, 14 nickels, 5 dimes, 0 quarters, 1 half-dollars Solution : 30 pennies, 12 nickels, 6 dimes, 2 quarters, 0 half-dollars Solution : 30 pennies, 9 nickels, 10 dimes, 1 quarters, 0 half-dollars Solution : 30 pennies, 6 nickels, 14 dimes, 0 quarters, 0 half-dollars Solution : 25 pennies, 23 nickels, 1 dimes, 0 quarters, 1 half-dollars Solution : 25 pennies, 21 nickels, 2 dimes, 2 quarters, 0 half-dollars Solution : 25 pennies, 18 nickels, 6 dimes, 1 quarters, 0 half-dollars Solution : 25 pennies, 15 nickels, 10 dimes, 0 quarters, 0 half-dollars Solution : 20 pennies, 27 nickels, 2 dimes, 1 quarters, 0 half-dollars Solution : 20 pennies, 24 nickels, 6 dimes, 0 quarters, 0 half-dollars
[EMAIL PROTECTED] wrote:
I think Mitch Christensen wrote:
Thanks for the help.
In the interest of understanding (and optimization), I've included my solution.
I'd appreciate any feedback anyone can to provide (for instance, finding 50
coins that add up to $2.00 throws an OutOfMemory exception with standard JVM
settings).
The LHS of your rule makes a list every possible combination of coins, valid or not. It's this long list of combinations that causes the OutOfMemoryError. This is kind of the "procedural programmer" approach to writing the rule. Don't be scared of pattern-matching -- it's what makes rule engines useful!
What you want to do is to move the filtering from the right-hand-side of the rule (where it's done *after* the list is made) to the left-hand-side (where it is done during pattern-matching, *while* the list is made, resulting in a much shorter list and better performance. So, for example
(defrule find-solution-2 (coin (denomination penny) (count ?cp) (amount ?ap)) (coin (denomination nickel) (count ?cn&:(<= (+ ?cn ?cp) 50)) (amount ?an&:(<= (+ ?an ?ap) 100))) (coin (denomination dime) (count ?cd&:(<= (+ ?cd ?cn ?cp) 50)) (amount ?ad&:(<= (+ ?ad ?an ?ap) 100))) ... [use '=' instead of '<=' for the last pattern] => (printout t "Solution : " ?cp " pennies, " ?cn " nickels, " ?cd " dimes, " ?cq " quarters, " ?ch " half-dollars" crlf))
will be faster and use much less memory.
-Mitch
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Find a set of 50 coins that add up to $1.00 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; prepare working memory (clear) (reset)
;; define the parameters (play with these for different results) (bind ?coinCount 50) (bind ?totalAmt 100)
;; define the coin fact template (deftemplate coin (slot denomination) (slot count) (slot amount))
;; assert all possible coin facts (foreach ?denom (create$ half-dollar quarter dime nickel penny) (bind ?count 0) (bind ?total 0)
;; assign the appropriate amounts (if (eq ?denom half-dollar) then (bind ?amount 50) else (if (eq ?denom quarter) then (bind ?amount 25)) else (if (eq ?denom dime) then (bind ?amount 10)) else (if (eq ?denom nickel) then (bind ?amount 5)) else (if (eq ?denom penny) then (bind ?amount 1)))
;; assert the necessary coin facts (while (and (<= ?total ?totalAmt) (<= ?count ?coinCount)) do ;; add the fact (assert (coin (denomination ?denom) (count ?count) (amount ?total)))
;; tally the total amount (bind ?total (+ ?total ?amount)) (bind ?count (+ ?count 1)) ) )
;; define the rules to find the combination of facts such that ;; the coin count equals ?coinCount and the amount equals ?totalAmt. ;; ;; ?cX - # of coins, ?aX amount of currency (defrule find-solution (coin (denomination penny) (count ?cp) (amount ?ap)) (coin (denomination nickel) (count ?cn) (amount ?an)) (coin (denomination dime) (count ?cd) (amount ?ad)) (coin (denomination quarter) (count ?cq) (amount ?aq)) (coin (denomination half-dollar) (count ?ch) (amount ?ah)) => (if (and (eq (+ ?cp ?cn ?cd ?cq ?ch) ?coinCount) (eq (+ ?ap ?an ?ad ?aq ?ah) ?totalAmt)) then (printout t "Solution : " ?cp " pennies, " ?cn " nickels, " ?cd " dimes, " ?cq " quarters, " ?ch " half-dollars" crlf)))
;; solve... (run)
-----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of [EMAIL PROTECTED] Sent: Monday, August 11, 2003 8:27 AM To: [EMAIL PROTECTED] Subject: Re: JESS: Newbie question (Coin puzzle)
I think Mitch Christensen wrote:
[Charset iso-8859-1 unsupported, filtering to ASCII...]
(coins)PROBLEM: Define a set of coins amounting to exactly $1.00 using exactly 50 coins.
APPROACH: I thought I'd assert he following facts,
2 Half dollar facts 4 Quarter facts 10 Dime facts 20 Nickel facts 100 Penny facts
Then define a rule to print the facts such that the number of facts
is 50 and the value of the 50 facts equals 100 ($1.00).
Since the problem isn't to determine -which- of the 100 pennies to use, for example, it's really unnecessary to represent each one individually. If it -were- necessary, then you'd want to be able to distinguish them, somehow, so you'd give them an identifier:
(deftemplate coin (slot type) (slot id (default-value (gensym*)))) (deftemplate coin-type (slot type) (slot value))
(bind ?count 50) (while (> ?count 0) (assert (coin (type penny))))
Each penny would then be unique.
But I don't think I would do it this way. What if you had facts like
(penny-count 0) (penny-count 1) (penny-count 2) ... (penny-count 50)
(nickel-count 0) (nickel-count 1) (nickel-count 2) ...
And then wrote a rule that matched one penny-count fact, one nickel-count fact, etc, such that the counts summed to 50, and the amounts summed to $1.00?
--------------------------------------------------------- Ernest Friedman-Hill Distributed Systems Research Phone: (925) 294-2154 Sandia National Labs FAX: (925) 294-2234 PO Box 969, MS 9012 [EMAIL PROTECTED] Livermore, CA 94550 http://herzberg.ca.sandia.gov
-------------------------------------------------------------------- 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] --------------------------------------------------------------------
-------------------------------------------------------------------- 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] --------------------------------------------------------------------
---------------------------------------------------------
Ernest Friedman-Hill Distributed Systems Research Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
PO Box 969, MS 9012 [EMAIL PROTECTED]
Livermore, CA 94550 http://herzberg.ca.sandia.gov
-------------------------------------------------------------------- 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] --------------------------------------------------------------------
-------------------------------------------------------------------- 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] --------------------------------------------------------------------