人工智能原理ch3_1and3_2.ppt

3. 圆盘梵塔问题归约图： 先用表列形式描述状态: （1 1 1）?（3 3 3） 习题：用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。 (1 1 1 1)?(3 3 3 3) 4.问题归约机理 问题归约技术：能够成功地把状态空间有哪些信誉好的足球投注网站问题归约为越来越简单的有哪些信誉好的足球投注网站问题，直至所有问题能够被归约为平凡解为止。 关键算符：对问题求解有决定性作用的算符叫做关键算符。 对梵塔难题（3圆盘）：移动圆盘C至柱3是关键算符。 如何根据当前状况选关键算符，以消除差别、归约求解呢？ 对猴子和香蕉问题，4个算符的作用结果和适用条件如下： 走f1：（W，0，Y，Z） goto(U) （U，0，Y，Z） 推f2：（W，0，W，Z） pushbox(V) （V，0，V，Z） 爬f3：（W，0，W，Z） climbbox （W，1，W，Z） 抓f4：（c，1，c，0） grasp （c，1，c，1） (a,0,b,0),F,(c,1,c,1) (1)合适的关键算符：抓 (a,0,b,0),F1,(c,1,c,0) (c,1,c,0),f4,(c,1,c,1) 本原问题 (2) 合适的关键算符：爬 (a,0,b,0),F2,(c,0,c,0) (c,0,c,0),f3,(c,1,c,0)本原问题 (3) 合适的关键算符：推 (a,0,b,0),F3,(b,0,b,0) (b,0,b,0),f2,(c,0,c,0) 本原问题 (4) 合适的关键算符：走 (a,0,b,0),f1,(b,0,b,0) 本原问题 解答由回溯得到。 第三章 知识表示 3.3 谓词逻辑法 表示一个知识库的主要方法是采用一阶谓词逻辑。 使用量词（ ， ）和逻辑连接符（∨，∧， ，=，=）能作出有关对象、特征、场景和关系的陈述。 例如：所有人都有头，可描述为 X人(X)=有(X，头) 优点：记号简单，描述易于理解。 每个事实仅需表示一次。 证明过程的推理规则是有效的。 缺点：难以表示过程性和启发性知识。 由于缺少结构上统一的规则，致使大型知识库难以管理，对证明过程进行操作的能力差。当事实的数量很大时，鉴于证明过程的每一步都需使用规则，而有可能导致组合爆炸。 第二章中对命题演算和谓词演算的有关语法、语义、恒等式等作了较详细的介绍。以下主要通过几个应用例子，以巩固一下前面所学的知识。 例1：旅游组团问题（原史密斯家族聚会问题） 某市几个老人院联合组团出去旅游度假。委托旅游公司办理。由于外出时间较长，故需要考虑安排兴趣爱好和习惯较一致的老人在一起（走一条线）。于是旅游公司就发了一张有关饮食爱好、娱乐偏爱、度假偏爱和起床习惯的调查表。该公司收回了填好的表，根据有关数据完成了旅游线路和人员分配的工作。 所发的表包含以下几方面的内容： 饮食爱好和习惯（蔬菜、肉类） 娱乐偏爱（电影、看戏、跳舞） 度假偏爱（城市、乡村） 起床时间（早起、晚起） 定义谓词: 饮食（X，D） 娱乐（X，E） 度假（X，L） 起床时间（X，R） 相同兴趣（X，Y） XYD1D2E1E2L1L2R1R2相同兴趣（X，Y）= （X=Y）∧（饮食（X，D1）∧饮食（Y，D2）∧（D1=D2）） ∧（娱乐（X，E1）∧娱乐（Y，E2）∧（E1=E2）） ∧（度假（X，L1）∧度假（Y，L2）∧（L1=L2）） ∧（起床时间（X，R1）∧起床时间（Y，R2）∧（R1=R2）） 然后根据以上规则，逐条匹配数据库中的事实，把兴趣和习惯相同的老人找出并归类。 原始数据已有，可以定不同规则。比如定义度假兴趣相同谓词（以度假为重点），给出解释性谓词演算表达式，以进行不同目的的统计检索。 例2：修道士和野人问题（有状态改变） 在河的左岸有三个修道士、三个野人和一条船。希望全部安全渡到右岸。 限制： （1）假定都会划船，船一次最多装两人。 （2）在任何岸边，野人数≤修道士数。否则修道士就会被野人吃掉。 假定野人愿服从任何一种过