[转帖]Jess应用与爱因斯坦的难题

wusk

━━━━━━━━━━━━━

提纲：

━━━━━━━━━━━━━

一、数学课上的较量

二、超越逻辑谜题

━━━━━━━━━━━━━

正文：

━━━━━━━━━━━━━

Internet上流传着一个Email，它描述了一个据说是爱因斯坦的难题，而且引用爱因斯坦的话说，全世界只有2%的人能够解决这个难题。实际上，这个难题是一个单词问题，属于演绎推理的一个基本应用。本文介绍了如何用Jess（Java平台的规则引擎）来求解此类问题。另外，从技术上看，求解单词问题和解决服务器端Java编程中的常见问题没有什么太大的不同，所有本文后面还将探讨如何在Java开发实践中应用Jess。

一、数学课上的较量

“答案呢？请回答！”

严厉的声音让你一惊。你又在Mrs. Krabapple的数学课上睡着了，但马上就意识到她问的正是你。

“哦……”

你看着黑板，那是一个逻辑题。Mrs. Krabapple正等着你给出答案。你很快地浏览了一篇她干瘪的手涂在黑板上的字迹：

⑴ 四个高尔夫球员站在球座上，从左到右站成一排。每个球员都穿不同的裤子；其中一个穿着红色裤子。紧挨Fred右边的球员穿的是蓝色裤子。

⑵ Joe是队伍中的第二位。

⑶ Bob穿的是格子花裤子。

⑷ Tom不是第一或第四位，也不穿难看的橙色裤子。

⑸ 请给出这四位球员具体排列次序，他们各穿什么颜色的裤子？

你很快搞清了题目的意思，但究竟怎样才能找出答案呢？没有现成的公式，分析思路也模糊不清。代数学肯定是另外一回事情，那么这个问题……为什么上课不好好听呢？

让“规则”来帮你忙！一个基于规则的程序能够满足Mrs. Krabapple的要求，迅速找出符合所有约束条件的球员姓名、位置、裤子颜色组合。你可以将问题说明直接转换成规则，由规则来找出合理的答案。

让我们写出这个程序，看看基于规则的系统如何求解这类问题。我们要用Jess语言来编写这个程序，如果你还不懂Jess语言，不要担心——现在你需要了解的只是解决问题的过程。我们将：

⑴ 选择一种方式来描述可能的球员姓名、位置、裤子颜色组合。

⑵ 写出描述该问题的规则。

⑶ Jess规则引擎将自动找出问题的答案。

第一步是定义数据结构，描述可能答案的最小有用单元，即球员姓名与位置或裤子颜色之间的关联：

(deftemplate pants-color (slot of) (slot is))
(deftemplate position (slot of) (slot is))



deftemplate有点象Java中的类声明。Java类的对象有成员变量，相似地，deftemplate有slot（插槽、空位的意思）。每一个slot代表一个占位符，可以放入特定的信息。例如，pants-color模板有一个名称为of的slot，用来保存球员的姓名；还有一个名称为is的slot，用来保存颜色信息。在Java中，类是对象类型的定义；而在Jess中，模板是事实类型的定义（“事实”在这里的含义基本上可以按照其通常的意思理解，它代表着一则可能有用的信息）。pants-color描述了：一个特定的球员（在名称为of的slot中指定）拥有特定颜色的裤子（在名称为is的slot中指定）。

我们将用这些模板来创建事实（相当于Java中用类创建对象），描述每一种可能的组合。这种组合总共有32种，例如：

(pants-color (of Bob) (is red))
(position (of Joe) (is 3))



我们可以写出一个规则来创建所有这32个事实，并把它们放入工作内存（Working Memory）。工作内存是Jess用来保存已知（可能）事实的临时内存空间：

(defrule generate-possibilities
    =>
    (foreach ?name (create$ Fred Joe Bob Tom)
        (foreach ?color (create$ red blue plaid orange)
            (assert (pants-color (of ?name)
                                (is ?color))))

        (foreach ?position (create$ 1 2 3 4)
            (assert (position (of ?name)
                             (is ?position))))))



上面的代码利用foreach循环问题涉及的4个姓名，利用assert为每一种可能的姓名/颜色组合创建一个pants-color事实，为每一种可能的姓名/位置组合创建一个position事实，总共得到32个事实。create$函数返回一个输入参数的清单。

现在我们已经编写好了创建所有可能组合的规则，接下来要做的是扫描这些可能的组合，找出其中可以作为问题答案的事实。这是最有趣的部分，我们要把问题描述中的每一个条件用代码表达出来。首先请注意以问号开头的符号，例如“?c”，在Jess中代表一个变量。下面我们将用“?c”来代表“某种颜色”，用“?p”来代表“某个位置”，用“?n”来代表“某个姓名”，而“?c1...?c4”和“?p1...?p4”则分别表示Fred、Joe、Bob和Tom的裤子颜色、位置。

下面是第一个有用的判断条件——紧挨Fred右边的球员穿蓝色（blue）裤子：

(defrule find-solution
;; 有一个球员，他的姓名是Fred，位置是?p1，
;; 裤子颜色是?c1。
    (position (of Fred) (is ?p1))
    (pants-color (of Fred) (is ?c1))

    ;; 紧挨Fred右边的球员身穿蓝色裤子
    (position (of ?n&~Fred)
              (is ?p&eq ?p (+ ?p1 1))))
    (pants-color (of ?n&~Fred)
                 (is blue&~?c1))



在上面的代码片段中，变量?n代表Fred右边球员的未知姓名，?p1是Fred的未知位置，?c1是Fred裤子的未知颜色，?p是未知球员的位置。另外，&表示and，~表示not，因此(name ?n&~Fred)表示这个人的姓名暂称之为?n，但不是Fred。下面是第二个判断条件：

;; Joe位于第二个位置
    (position (of Joe) (is ?p2&2&~?p1))
    (pants-color (of Joe) (is ?c2&~?c1))



注意编写规则时务必仔细小心。我们知道每一个球员有一个不同的位置，因而可以肯定地说，?p2&2&~?p1即Joe的位置，称之为?p2，它的值是2，必然和Bob的位置?p1不同。另一方面，?p2和?p却有可能是相同的，Joe可能正好紧挨Fred的右边，因此这里我们不用?p。

再看下一个条件，Bob穿的是格子花（plaid）裤：

;; Bob穿格子花裤
    (position (of Bob)
     (is ?p3&~?p1&~?p&~?p2))
    (pants-color (of Bob&~?n)
     (is plaid&?c3&~?c1&~?c2))



现在我们已经知道许多有关Bob位置?p3和裤子颜色?c3的情况了。我们知道?p3不同于?p1或?p2，而且它也不同于?p。为什么呢？因为在位置?p的球员穿的是蓝色裤子，而Bob的裤子是格子花库，且?p1和?p2位置的球员叫做Fred和Joe，不是Bob。

wusk

最后，关于Tom我们也知道很多情况。Tom不在第一、第四个位置，而且他不穿橙色的裤子：


;; Tom不在第一、第四个位置
    ;; 而且他不穿橙色裤子
    (position (of Tom&~?n)
              (is ?p4&~1&~4&~?p1&~?p2&~?p3))
    (pants-color (of Tom)
                 (is ?c4&~orange&~blue&~?c1&~?c2&~?c3))



总共只有四个位置，但我们知道Tom的位置不是1，不是4，而且不是?p1、?p2、?p3——约束条件非常严格。实际上，约束条件越严格越好，它表示我们有足够的信息来求得有效的答案。对于Tom的裤子颜色，我们也放入类似的约束条件。

最后剩下的工作就是输出?p1...?p4和?c1...?c4变量的值，这些变量的值就是问题的答案：

=>
    (printout t Fred " " ?p1 " " ?c1 crlf)
    (printout t Joe "  " ?p2 " " ?c2 crlf)
    (printout t Bob "  " ?p3 " " ?c3 crlf)
    (printout t Tom "  " ?p4 " " ?c4 crlf crlf))



符号“=>”用来分割规则的if部分和then部分——它的意思是，当所有的条件满足时，该规则应当采取什么动作，在本例中它的动作是输出结果表格。只要我们将上述代码提供给Jess，然后运行，马上就可以得到结果。假设源代码保存在krabapple.clp文件，我们可以用如下命令运行它：

C:\Jess61> java -classpath jess.jar jess.Main Krabapple.clp
Fred 1 orange
Joe 2 blue
Bob 4 plaid
Tom 3 red



可以看到，实际上只有一组变量的值满足条件，原来Joe就是那个穿蓝色裤子的神秘人物……

如果我们删除其中的某些条件，会出现什么情况？例如，假设我们不知道Joe排在队列中的第二个位置——这会对结果产生哪些影响？让我们试它一试。如果我们把程序中有关Joe的那一部分改成：

;; 现在关于Joe的情况我们所知不多

(position (of Joe) (is ?p2&~?p1))
    (pants-color (of Joe) (is ?c2&~?c1))



然后再运行程序，得到的结果是：

Fred 3 orange
Joe 4 blue
Bob 1 plaid
Tom 2 red

Fred 2 orange
Joe 4 blue
Bob 1 plaid
Tom 3 red

Fred 2 orange
Joe 1 blue
Bob 4 plaid
Tom 3 red

Fred 1 orange
Joe 2 blue
Bob 4 plaid
Tom 3 red

Fred 1 orange
Joe 3 blue
Bob 4 plaid
Tom 2 red

Fred 1 orange
Joe 4 blue
Bob 3 plaid
Tom 2 red



总共有六种不同的有效答案，Jess找出并报告了所有这些答案。这就是基于规则的编程带来的第二个优点：如果出现不完整的信息，基于规则的系统能够逐步降级——你不必花力气为Jess程序构造这类功能，这是它天生拥有的功能。

二、超越逻辑谜题

当你从数学课上的噩梦之中回过神来，也许还会庆幸地想：幸好解决逻辑难题与一个普通程序员的日常工作毫无关系。如果你确实这样想，那就错了。由于对问题的定义不够清晰，业务环境中到处都有类似逻辑难题的情形。下面我们来看一个典型的例子。

假设你正在编写一个程序，它的功能是接收客户的订单，按照统一格式整理订单，然后将订单发送给仓库提货。每一个订单包含一个商品、数量、客户、日期的清单。你很快写出了程序，一切顺利。

然后，你的老板来了，说：“给每一位消费金额大于100元的客户10%的折扣。”没问题，你加入了一行if语句，再次编译，程序重新运行起来了。

你的老板又来了，这次他说：“如果客户购买了以前没有买过的商品，给这种商品25%的折扣。”好吧，你现在要加入一些数据库查询了。但用不了多少时间，你又完成了任务。

现在老板又来了，提出了新的要求：“作废以前针对每个订单打的10%折扣，现在打10%折扣的条件是你必须每月花250或以上。另外，如果有人买了一个CD刻录机，送他一张免费的样品CD-RW盘——前提是客户必须是一个回头客。哦，对了，现在我们要按照地理位置计算送货费用，不过如果客户有多个送货地点，那就执行原来的送货费用政策……”

如此这般，几个星期之后，如果你使用的是传统的编程技术，代码已经变成一团乱麻了——而且代码的性能肯定也不会好，因为它要为每一个输入的订单执行各种各样的数据库查询。

反之，如果你使用了一个规则引擎，就可以保持代码整洁、富有条理，每一个定价政策可以用一个规则来描述。如果有人要查找“古怪的星期三”定价政策在哪些代码中实现，他可以很轻松地找到。

如果你使用Jess，那么代码的性能也不会差；规则引擎会索引所有的订单，不需要耗用大量时间去查找；规则引擎“掌握了”它必须知道的有关历史订单的信息。

结束语：基于规则的程序无所不在，它们的应用也无所不在，从邮件过滤到订单配置、化学车间监视、疾病诊断，以及贷款处理，等等。当问题很难用传统的算法求解时，基于规则的程序也许能够很轻松地解决问题，而且它们在输入数据不完整时也能给出答案。有关Jess的更多信息，请参见http://herzberg.ca.sandia.gov/jess。

【本文译自】http://www.developer.com/java/other/article.php/3089641。