`
hxpwork
  • 浏览: 109446 次
  • 性别: Icon_minigender_1
  • 来自: 广州
文章分类
社区版块
存档分类
最新评论

Drools4：Manners示例分析

算法UP 
阅读更多
  1. /*  
  2.     manners示例是一个安排座位的例子，它的要求如下：  
  3.     1、客人应当按照男女性别相邻而坐，围成一圈  
  4.     2、假设客人会有2-3个个人爱好（爱好的可选范围是3种），为了让大家能够更好的交流，  
  5.        要安排每个人都和相邻座位的两个人有共同的爱好，并且与左右两边的共同爱好不要相同  
  6.     3、客人的人数在本例中为64人，男女各一半  
  7.       
  8.     解题思路：  
  9.     1) 按照规则引擎的特性，首先应当将所有可能的数据准备好，从本例来看，客人是主要的数据对象，  
  10.        姓名/性别/兴趣 是三个主要属性，姓名和性别是固定的，可能有多个选择的就是兴趣爱好，  
  11.        那么首先应当将客人的兴趣分别与姓名/性别组合后放入WorkingMemory  
  12.     2) 再考虑一下，本例中规定了每个客人都会有三种爱好里的两种，也就是说任意两个人都必然有相同爱好  
  13.        只要注意不要性别相同以及两边爱好一致就可以；那么只要先安排一个人坐下（这个人应当三种爱好都有），  
  14.        然后找一个性别不同，有一种相同爱好的客人A坐在左边；接下去找一个坐在A旁边的客人B，同样与A性别  
  15.        不同，并且和前一位的共同爱好也不同。这样一直排下去，直到最后一个座位。这里解释一下为什么一开始  
  16.        第一个人要三种爱好齐备，因为这种算法有一个漏洞是没有考虑第一个客人和最后一个客人是相邻而坐的，  
  17.        如果第一个客人和最后一个客人只有一个共同兴趣而这个兴趣又正好是第一和第二个客人的共同兴趣，那么  
  18.        这种算法会得到不正确的结果，但只要第一个坐下来的人三种爱好都有，那么必然和两边的人都有不同爱好，  
  19.        这也弥补了算法的不同。  
  20.        注：从本例中准备的数据和算法来看并没有考虑到这个问题，虽然按照原始数据可以得到正确的结果，但是  
  21.        进行针对性的调整后就会发现结果会有问题  
  22.     3) 因为座位是一个一个找出来的，因此要有合适的流程控制方法。    
  23.       
  24. */  
  25.   
  26.   
  27. package org.drools.benchmark.manners   
  28.   
  29. # 从客人中找出一位放入第一个座位   
  30. # 根据Drools引擎的特性，应当是最后一个加入的Guest   
  31. # 利用Context.state属性控制该规则只执行一次   
  32. rule assignFirstSeat   
  33.     when   
  34.         # Context用于流程控制   
  35.         context : Context( state == Context.START_UP )   
  36.         #   
  37.         #   原例中使用的是  Guest() ， 获得最后插入的Fact，但是这样会引起之前提到的Bug   
  38.         #   因此在下面进行了改进，保证找出三个兴趣都有的客人   
  39.         #   
  40.         guest : Guest( $name:name , $hobby : hobby )   
  41.         Guest ( name == $name , hobby != $hobby , $hobby1 : hobby )   
  42.         Guest ( name == $name , hobby != $hobby , hobby != $hobby1 )   
  43.            
  44.         count : Count()   
  45.     then   
  46.         String guestName = guest.getName();   
  47.            
  48.         # Seating用于记录每个座位上的客人，是寻找下一个座位的客人的依据   
  49.         Seating seating =  new Seating( count.getValue(), 1, true, 1, guestName, 1, guestName);   
  50.         insert( seating );   
  51.            
  52.         # Path用来避免已经入座的客人再次被选中   
  53.         Path path = new Path( count.getValue(), 1, guestName );   
  54.         insert( path );   
  55.            
  56.         # 用于计数，并作为Seating的ID   
  57.         count.setValue(  count.getValue() + 1 );           
  58.         update( count );   
  59.   
  60.         System.out.println( "assign first seat :  " + seating + " : " + path );   
  61.   
  62.         # 进入找下一个座位环节   
  63.         context.setState( Context.ASSIGN_SEATS );           
  64.         update( context );   
  65. end   
  66.   
  67. # 寻找相邻的同伴   
  68. rule findSeating   
  69.    when    
  70.        context : Context( state == Context.ASSIGN_SEATS )   
  71.        # 获得最近安排好座位的客人   
  72.        $s:Seating( seatingId:id, seatingPid:pid, pathDone == true, seatingRightSeat:rightSeat, seatingRightGuestName:rightGuestName )   
  73.        # 找到一位有共同兴趣但性别不同的相邻客人   
  74.        Guest( name == seatingRightGuestName, rightGuestSex:sex, rightGuestHobby:hobby )   
  75.        Guest( leftGuestName:name , sex != rightGuestSex, hobby == rightGuestHobby )   
  76.   
  77.        count : Count()   
  78.        # 排除已经入座的客人   
  79.        #   
  80.        # 原例中使用了Path.id作为一个约束条件，而事实上要排除已经入座的客人只要判断guestName就可以了   
  81.        # 因此原例中的makePath规则如果注释掉，然后将下面的语句改为   
  82.        # not ( Path( guestName == leftGuestName) )   
  83.        # 执行后也可以得到完全相同的结果   
  84.        # Manners是作为规则引擎的测试基准发布的，因此这里完全按照标准实现，所以这里虽然
  85.        # 可以进行改进，但是可能因为为了测试规则引擎，因此保留这种算法
  86.        #
  87.        not ( Path( id == seatingId, guestName == leftGuestName) )   
  88.           
  89.        # 排除入座客人已经和使用过的兴趣，保证两边相邻的客人共同兴趣不一样   
  90.        not ( Chosen( id == seatingId, guestName == leftGuestName, hobby == rightGuestHobby) )   
  91.    then   
  92.        int rightSeat = seatingRightSeat;   
  93.        int seatId = seatingId;   
  94.        int countValue = count.getValue();   
  95.           
  96.        # 安排一个新的座位   
  97.        Seating seating = new Seating( countValue, seatId, false, rightSeat, seatingRightGuestName, rightSeat + 1, leftGuestName );   
  98.        insert( seating );        
  99.        # 记录已经入座的客人                       
  100.        Path path = new Path( countValue, rightSeat + 1, leftGuestName  );   
  101.        insert( path );   
  102.        # 记录已经使用的兴趣爱好   
  103.        Chosen chosen = new Chosen( seatId, leftGuestName, rightGuestHobby );   
  104.        insert( chosen  );   
  105.   
  106.        System.err.println( "find seating : " + seating + " : " + path + " : " + chosen);   
  107.        count.setValue(  countValue + 1 );   
  108.        update( count );          
  109.   
  110.        context.setState( Context.MAKE_PATH );   
  111.        update( context );   
  112.           
  113.        retract ( $s );   
  114. end   
  115.   
  116. /*  
  117.   这个规则的执行将为之前所有入座的客人建立一个路径  
  118.   如果使用一个打印语句，部分打印内容如下：  
  119.   makePath :[Path id=1, seat=1, guest=63]  
  120.   makePath :[Path id=2, seat=1, guest=63]  
  121.   makePath :[Path id=2, seat=2, guest=52]  
  122.   makePath :[Path id=3, seat=2, guest=52]  
  123.   makePath :[Path id=3, seat=1, guest=63]  
  124.   makePath :[Path id=3, seat=3, guest=64]  
  125.   makePath :[Path id=4, seat=3, guest=64]  
  126.   makePath :[Path id=4, seat=1, guest=63]  
  127.   makePath :[Path id=4, seat=2, guest=52]  
  128.   makePath :[Path id=4, seat=4, guest=50]  
  129.   makePath :[Path id=5, seat=4, guest=50]  
  130.   makePath :[Path id=5, seat=2, guest=52]  
  131.   makePath :[Path id=5, seat=1, guest=63]  
  132.   makePath :[Path id=5, seat=3, guest=64]  
  133.   makePath :[Path id=5, seat=5, guest=62]  
  134.   ......  
  135.   也就是每个id的数值就对应有多少个Path，而事实上这种数据模型对本例来说并不是太需要  
  136.   在之前的findSeating规则中有说明。  
  137. */  
  138. rule makePath   
  139.     when    
  140.         Context( state == Context.MAKE_PATH )   
  141.         Seating( seatingId:id, seatingPid:pid, pathDone == false )   
  142.         $path : Path( id == seatingPid, pathGuestName:guestName, pathSeat:seat )   
  143.         not Path( id == seatingId, guestName == pathGuestName )   
  144.     then   
  145.         System.out.println ( "makePath :" + $path  );   
  146.         insert( new Path( seatingId, pathSeat, pathGuestName ) );   
  147. end    
  148.   
  149. # 结束座位的路径设置   
  150. rule pathDone   
  151.     when   
  152.         context : Context( state == Context.MAKE_PATH )    
  153.         seating : Seating( pathDone == false )    
  154.     then   
  155.         seating.setPathDone( true );    
  156.         update( seating );   
  157.            
  158.         context.setState( Context.CHECK_DONE );    
  159.         update( context );   
  160. end   
  161.   
  162. # 检查是否安排的客人座位已经到达指定人数，结束规则运算   
  163. rule areWeDone   
  164.     when   
  165.         context : Context( state == Context.CHECK_DONE )    
  166.         LastSeat( lastSeat: seat )   
  167.         Seating( rightSeat == lastSeat )    
  168.     then   
  169.         context.setState(Context.PRINT_RESULTS );    
  170.         update( context );   
  171. end   
  172.   
  173. # 如果之前的areWeDone规则没有允许，则继续座位查找   
  174. rule continue  
  175.     when   
  176.         context : Context( state == Context.CHECK_DONE )    
  177.     then   
  178.         context.setState( Context.ASSIGN_SEATS );    
  179.         update( context );   
  180. end   
  181.   
  182. # 打印完成提示   
  183. rule allDone   
  184.     when   
  185.         context : Context( state == Context.PRINT_RESULTS )    
  186.     then   
  187.         System.out.println( "All Done" );   
  188. end   
  189.   
  190. //query getResults   
  191. //  context : Context( state == Context.PRINT_RESULTS )    
  192. //end    
  193.    
分享到：
drools4: Conway示例分析
评论
1 楼 hxpwork 2007-08-15  
另外补充一点，Manners是作为对规则引擎的基准测试发布的，这里的例子是完全按照论文中要求的实现，所以MakePath规则虽然可能有更好的实现方式，但是它存在的目的是为了测验规则引擎的性能，因此被保留下来。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics