回答集程序设计.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,回答集程序设计,华南师范大学,07,级研究生 吕勇全,主要内容,程序设计的一般步骤,常用前端和求解引擎,Lparse,支持的语法形式,例子：家庭关系,例子：图着色问题,语法和语义的扩展,Grounding,例子：积木世界,例子：自动排课,基于回答集的问题求解一般步骤,1.,编写回答集程序,2.,给出与具体问题相关的基事实和常量的值,3.,调用回答集求解器求解,（,3.1,）程序的例化和化简,(front end),（,3.2,）求解基程序的回答集,常用的回答集求解器前端和求解引擎,常用的前端：,lparse,dlv-instantiate,gringo,plp,nlp,等。,常用的求解引擎：,Smodels,Cmodels,Assat,Clasp,等。,lparse,支持的语法形式（一）,常量,(constant),：常量是指问题域中的某一个体，可以是数字或符号，一般以小写字母开头。,如：,a,10,foo,bar.,变量,(Variable),：变量用来概括一类事情，在回答集程序中常通过求解来给变量赋予某一确定的值，变量一般用大写字母开头。,如：,X,，,Foo,Bar.,原子,(Atom),：原子由谓词符号后跟一串常量或变量的列表组成，常用来表达常量之间的关系。,如：,parent(john,jill).,lparse,支持的语法形式（二）,规则（,Rule):,规则允许我们对谓词进行推理，如果规则体的原子都为真，我们就能推出规则头的原子也必定为真。,sibling(X,Y):-parent(Z,X),parent(Z,Y).,事实（,Fact,）：,female(joan).,约束（,Constraint,）：规则头为空的规则。,:-parent(Z,X),parent(X,Z).,例子：一个家庭关系的回答集程序,程序,1,：,sibling(X,Y):-parent(Z,X),parent(Z,Y).,mother(X,Y):-parent(X,Y),female(X).,uncle(X,Y):-parent(Z,Y),sibling(Z,X),male(X).,female(joan).female(jill).male(jack).,parent(joan,jack).parent(joan,jill).,例子：图着色问题,程序,2,：,color(red).color(blue).color(yellow).,col(X,red):-node(X),not col(X,blue),not col(X,yellow).,col(X,blue):-node(X),not col(X,red),not col(X,yellow).,col(X,yellow):-node(X),not col(X,blue),not col(X,red).,:-edge(X,Y),col(X,C),col(Y,C),color(C).,node(a).node(b).node(c).node(d).,edge(a,b).edge(b,c).edge(c,d).edge(d,a).,hide.,show col(X,Y).,语法和语义的扩展（一）,(1),定义域谓词,(domain predicate),：定义域谓词可以表示为,color(1.k),的形式,相当于,color(1),，,color(2),，,color(k),。在规则体中：,b:-a(1.3),(2),Smodels,中的,选择规则（,choice rule,）：选择规则具有如下的两种形式：,语法和语义的扩展（二）,（,3,）,dlv,中的弱约束（,weak constraint,）：,dlv,中的弱约束特征允许我们用一种更容易和自然的方式来一些优化问题。,程序,3,：,a v b.,c:-b.,:a.,:b.,:c.,程序,3,在,dlv,上运行，所获得的最佳模型是,a,。但程序,avb.c:-b.,的回答集是,a,，,b,，,c,。,语法和语义的扩展（三）,（,4,）析取规则：,析取程序的回答集是,规则体被满足时,规则头的最小模型，规则（,2,）的回答集为：,sun,，,light,语法和语义的扩展（四）,（,5,）经典否定,(Classical Negation),（,6,）嵌套逻辑程序,(Nested logic programs),与下面的两条规则含意相同：,Grounding,（一）,A grounding transforms a normal logic program into an equivalent ground logic program where the equivalence is defined as having the same set of stable models.,程序,4,：,man(a).man(b).man(c).,male(X):-man(X),not female(X).,female(X):-man(X),not male(X).,Grounding,（二）,程序,4,做,Grounding,后得到程序,5,程序,5,：,man(a).man(b).man(c).,male(a):-man(a),not female(a).,male(b):-man(b),not female(b).,male(c):-man(c),not female(c).,female(a):-man(a),not male(a).,female(b):-man(b),not male(b).,female(c):-man(c),not male(c).,例子：积木世界,constant,：,Lasttime:,最大步数；,grippers:,机器手的数量；,domain predicate:,time(T):,时间；,block(B),：积木；,location(L),：位置；,predicate,：,on(B,L,T):,积木,B,在时间,T,的位置为,L,；,move(B,L,T),：将积木,B,在时间,T,移动到位置,L,；,例子：积木世界,const grippers=2,const lasttime=3 time(0.lasttime).,block(1.6).,location(B):-block(B).location(table).,*,初始状态,on(1,2,0).on(2,table,0).on(3,4,0).,on(4,table,0).on(5,6,0).on(6,table,0).,*,目标状态,:-not on(3,2,lasttime).,:-not on(2,1,lasttime).,:-not on(1,table,lasttime).,:-not on(6,5,lasttime).,:-not on(5,4,lasttime).,:-not on(4,table,lasttime).,积木世界（模型生成）,*生成动作,move(B,L,T):block(B):location(L)grippers:-time(T),Tlasttime.,*,动作的效果,on(B,L,T+1):-move(B,L,T),，,block(B),，,location(L),，,time(T),，,Tlasttime.,*,frame problem,on(B,L,T+1):-on(B,L,T),not -on(B,L,T+1),location(L),block(B),t ime(T),Tlasttime.,位置的唯一性,-on(B,L1,T):-on(B,L,T),，,L!=L1,，,block(B),，,location(L),，,location(L1),time(T).,积木世界（模型测试）,*两个积木不能在同一个积木上,:-2on(B1,B,T):block(B1),block(B),t ime(T).,*,只有在积木上面为空时才能移动,:-move(B,L,T),，,on(B1,B,T),block(B),block(B1),location(L),，,time(T),Tlasttime.,*,一个积木不能移动到另一个正在移动的积木上,:-move(B,B1,T),move(B1,L,T),block(B),block(B1),location(L),t ime(T),Tlasttime.,%,运行命令：,lparse true-negation block.lp block_world.lp|smodels,例子：自动排课,问题描述：,时间表问题（,Time Table Problems,）是典型的组合优化和不确定调度问题，被证明为是,NP,完全问题,排课问题主要是利用有限的资源将每门课安排在何时、何地，并且教师、班级以及教室的安排不会发生冲突，同时又满足所有约束。,排课中面临的主要问题是约束条件复杂，条件不断变化,排课问题约束条件,基本硬约束,(Basehard Constraints),B1,同一时间同一教师不能给两门不同课程上课；,B2,同一时间同一班级不能安排两门不同课程；,硬约束,(Hard Constraints),H1,某些班级的某些课程可以先行手工安排时间点；,H2,某些教师或班级在某个时间上可能不能够利用；,H3,体育课安排在上午,3,一,4,节或者下午，体育课之后不安排课程，实验课、实习课等课程有自身的安排方式；,H4,某一时间段不安排课程；,H5,某课程连堂。,软约束,(Soft Constraints),S1,班级课程表在星期上尽量分布均匀；,S2,课表中的每个时间有一定优度；,S3,主课尽量排上午，副课尽量排下午；,S4,教师对上课时间存在一定的喜好；,排课问题的回答集程序表示（一）,事实：,班级：,class(L),教师：,teacher(G),课程：,course(C),、,course_teacher(C,G),、,course_class(C,，,L),时间元：,time(T),排课系统首要的规则：,排课问题的回答集程序表示（二）,基本硬约束,B1,：,基本硬约束,B2,：,排课问题的回答集程序表示（三）,H1,：某些班级的某些课程可以先行手工安排时间点,H2(1),：某一教师不能在某些时间点上课,H2,（,2,）：某一班级某些时间段固定无课,H3,：,体育课安排在上午,3,一,4,节或者下午，体育课之后不安排课程,排课问题的回答集程序表示（三）,H4,：,某一时间段不安排课程,H5,：,某课程连堂,软约束：,S1,班级课程表在星期上尽量分布均匀；,S2,课表中的每个时间有一定优度；,S3,主课尽量排上午，副课尽量排下午；,S4,教师对上课时间存在一定的喜好；,