人工智能第二章上

为0，关状态为1，全部可能的状态为：Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0)Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1)Q6=(1,1,0) ; Q7=(1,1,1)。

翻动琴键的操作抽象为改变上述状态的算子，即F＝{a, b, c} a:把第一个琴键q0翻转一次b:把第二个琴键q1翻转一次c:把第三个琴键q2翻转一次问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}>问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。

二阶梵塔的全部状态这里的状态转换规则就是金盘的搬动规则，分别用A盘从第i号杆移到第j号杆上号杆移到第j号杆上。

经分析，共有(1,3),　A(2,1),　A(2,3),　A(1,3),　B(2,1),　B(2,3),　B(3,1),代价树如下图所示：分别给出宽度优先及深度优先搜索策略下的、I、 J、L是目标节点。

宽度优先搜索过程：B－﹥ G－﹥E2. 求下列谓词公式的子句集(1)∃x ∃y(P(x,y) ∧Q(x,y))解：去掉存在量词变为：P(a,b)∧Q(a,b)变成子句集{ P(a,b),Q(a,b )}(2)∀x ∀y(P(x,y) →Q(x,y))解：去掉蕴涵符号变为：∀x ∀y(¬ P(x,y) ∨ Q(x,y))去掉全称量词变为：¬ P(x,y) ∨ Q(x,y)变成子句集{ ¬ P(x,y) ∨ Q(x,y)}(3) {()[(,)(,,)]}x P x y zQ x z zR x y z ∀→∃∀∨∀()(,)(,(),)P x Q x z R x f x z ⌝∨∨(4)((,,,,,)(,,,,,)(,,,,,))x y z u v w P x y z y v w Q x y z y v w R x y z u v w ∃∀∃∃∀∃∨∧{p(a,y,f(y),y,v,g(y,v)) ∨Q(a,y,f(y),y,v,g(y,v)),p(a,x,f(x),x,z,g(x,z)) ∨R(a,x,f(x),h(x),z,g(x,z))}3. 试判断下列子句集中哪些是不可满足的 （1）使用删除策略 （2）归结4.用合一算法求下列公式集的最一般合一。

21 典型的例子:下棋、迷宫及各种游戏。

2123初始棋局目标棋局为每个棋牌制定一套可能的走步：左、上、右、下四种移动。

这样就需32个仅为空格制定这4种走步，因为只有紧靠空格的棋牌才能移动。

* 空格移动的唯一约束是不能移出棋盘。

25根据问题状态、操作算符和目标条件选择各种表示，是高效率求解必须的。

在问题求解过程中，会不断取得经验，获得一些简化的表示。

八数码难题部分状态图2626从初始棋局开始，试探由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。

这样继续下去，直至达到目标棋局为止。

把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。

这种图称为状态图。

图中每个节点标有它所代表的棋局。

首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。

…,n ik ）当j=2,3j=2,3j=2,3,…k 时，如果都有一个后继节点n n ij 存在，那么就把这至节点n n ik 的长度为k k 的路28，由节点（不一定是有限的节点）的集合构成。

，是指图中的一对节点用弧线连接起来，从一个节31操作（算符）：333334该初始状态变换为目标状态的操作序列为：{goto(b),,pushbox(c),),),climbbox, grasp}343535 例2.1 推销员旅行问题（旅行商问题）一个推销员计划出访推销产品。

他从一个城市（如A）出发，访问每个城市一次，且最多一次，然后返回城市A。

要求寻找最短路线。

图2.3 推销员旅行问题状态描述：目前为止访问过的城市列表（A初始状态：（A）目标状态：（A……A）101038图2.4 推销员旅行问题状态空间图算符：下一步走向的城市(a)(b)(c)(d)(e) 约束：每个城市只能走过一次，A除外梵塔难题个柱子(1(1(1，，2，3)3)和和3个不同尺寸的圆盘个不同尺寸的圆盘(A (A (A，，在每个圆盘的中心有个孔在每个圆盘的中心有个孔，，所以圆盘可以堆叠在柱子上以堆叠在柱子上。

第二章知识表示方法2-1 状态空间法、问题归约法、谓词逻辑法和语义网络法的要点是什么？它们有何本质上的联系及异同点?2-2 设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。

该船的负载能力为两人。

在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。

他们怎样才能用这条船安全地把所有人都渡过河去?用S i(nC, nY) 表示第i次渡河后，河对岸的状态，nC表示传教士的数目，nY表示野人的数目，由于总人数的确定的，河对岸的状态确定了，河这边的状态也即确定了。

考虑到题目的限制条件，要同时保证，河两岸的传教士数目不少于野人数目，故在整个渡河的过程中，允许出现的状态为以下3种情况：1. nC=02. nC=33. nC=nY>=0 (当nC不等于0或3)用d i(dC, dY)表示渡河过程中，对岸状态的变化，dC表示，第i次渡河后，对岸传教士数目的变化，dY表示，第i次渡河后，对岸野人数目的变化。

当i为偶数时，dC,dY同时为非负数，表示船驶向对岸，i为奇数时，dC, dY同时为非正数，表示船驶回岸边。

初始状态为S0(0, 0)，目标状态为S0(3, 3)，用深度优先搜索的方法可寻找渡河方案。

在此，用图求法该问题，令横坐标为nY, 纵坐标为nC，可行状态为空心点表示，每次可以在格子上，沿对角线移动一格，也可以沿坐标轴方向移动1格，或沿坐标轴方向移动2格。

第奇数次数状态转移，沿右方，上方，或右上方移动，第偶数次数状态转移，沿左方，下方，或左下方移动。

从(0,0)开始，依次沿箭头方向改变状态，经过11步之后，即可以到达目标状态(3,3)，相应的渡河方案为：d1(1,1)--→d2(-1,0)--→d3(0,2)--→d4(0,-1)--→d5(2,0)--→d6(-1,-1)--→d7(2,0)--→d8(0,-1)--→d9(0,2)--→d10(-1,0)--→d11(1,1)2-3 利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A 开始，访问其他城市不多于一次，并返回A 。

第2章知识表示方法参考答案2.8设有如下语句，请用相应的谓词公式分别把他们表示出来：(1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。

解：定义谓词P(x)：x是人L(x,y)：x喜欢y其中，y的个体域是{梅花，菊花}。

将知识用谓词表示为：(∃x )(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花))(2) 有人每天下午都去打篮球。

解：定义谓词P(x)：x是人B(x)：x打篮球A(y)：y是下午将知识用谓词表示为：(∃x )(∀y) (A(y)→B(x)∧P(x))(3)新型计算机速度又快，存储容量又大。

解：定义谓词NC(x)：x是新型计算机F(x)：x速度快B(x)：x容量大将知识用谓词表示为：(∀x) (NC(x)→F(x)∧B(x))(4) 不是每个计算机系的学生都喜欢在计算机上编程序。

解：定义谓词S(x)：x是计算机系学生L(x, pragramming)：x喜欢编程序U(x,computer)：x使用计算机将知识用谓词表示为：¬(∀x) (S(x)→L(x, pragramming)∧U(x,computer))(5)凡是喜欢编程序的人都喜欢计算机。

解：定义谓词P(x)：x是人L(x, y)：x喜欢y将知识用谓词表示为：(∀x) (P(x)∧L(x,pragramming)→L(x, computer))2.9用谓词表示法求解机器人摞积木问题。

设机器人有一只机械手，要处理的世界有一张桌子，桌上可堆放若干相同的方积木块。

机械手有4个操作积木的典型动作：从桌上拣起一块积木；将手中的积木放到桌之上；在积木上再摞上一块积木；从积木上面拣起一块积木。

积木世界的布局如下图所示。

图机器人摞积木问题解：(1) 先定义描述状态的谓词CLEAR(x)：积木x上面是空的。

ON(x, y)：积木x在积木y的上面。

ONTABLE(x)：积木x在桌子上。

HOLDING(x)：机械手抓住x。

第2章知识表示方法参考答案2.8设有如下语句，请用相应的谓词公式分别把他们表示出来：(1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。

解：定义谓词P(x)：x是人L(x,y)：x喜欢y其中，y的个体域是{梅花，菊花}。

将知识用谓词表示为：(∃x )(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花))(2) 有人每天下午都去打篮球。

解：定义谓词P(x)：x是人B(x)：x打篮球A(y)：y是下午将知识用谓词表示为：(∃x )(∀y) (A(y)→B(x)∧P(x))(3)新型计算机速度又快，存储容量又大。

解：定义谓词NC(x)：x是新型计算机F(x)：x速度快B(x)：x容量大将知识用谓词表示为：(∀x) (NC(x)→F(x)∧B(x))(4) 不是每个计算机系的学生都喜欢在计算机上编程序。

解：定义谓词S(x)：x是计算机系学生L(x, pragramming)：x喜欢编程序U(x,computer)：x使用计算机将知识用谓词表示为：¬(∀x) (S(x)→L(x, pragramming)∧U(x,computer))(5)凡是喜欢编程序的人都喜欢计算机。

解：定义谓词P(x)：x是人L(x, y)：x喜欢y将知识用谓词表示为：(∀x) (P(x)∧L(x,pragramming)→L(x, computer))2.9用谓词表示法求解机器人摞积木问题。

设机器人有一只机械手，要处理的世界有一张桌子，桌上可堆放若干相同的方积木块。

机械手有4个操作积木的典型动作：从桌上拣起一块积木；将手中的积木放到桌之上；在积木上再摞上一块积木；从积木上面拣起一块积木。

积木世界的布局如下图所示。

图机器人摞积木问题解：(1) 先定义描述状态的谓词CLEAR(x)：积木x上面是空的。

ON(x, y)：积木x在积木y的上面。

ONTABLE(x)：积木x在桌子上。

HOLDING(x)：机械手抓住x。

习题一、选择题1.人工智能的目的是让机器能够（A ），以实现某些脑力劳动的机械化。

A．模拟、延伸和扩展人的智能 B. 具有完全的智能C．完全替代人 D. 和人脑一样考虑问题2.人工智能研究的最重要最广泛的两大领域是（D ）。

A．专家系统自动规划 B. 专家系统机器学习C．机器学习自动规划 D. 机器学习自然语言理解3.要想让机器具有智能，必须让机器具有知识。

因此，在人工智能中有一个研究领域，主要研究计算机如何自动获取知识和技能，实现自我完善，这门研究分支科学叫（B ）。

A．专家系统 B.机器学习C．神经网络 D. 编译原理4.大数据技术目前在以下哪个领域运用最为广泛（C ）。

A．金融 B.电信C．互联网 D. 公共管理5.下列关于大数据的分析理念的说法中，错误的是（D ）。

A．在数据基础上倾向于全体数据而不是抽样数据B．在分析方法上更注重相关分析而不是因果分析C．在分析效果上更追究效率而不是绝对精确D．在数据规模上强调相对数据而不是绝对数据6.大数据时代，数据使用的关键是（C ）A．数据收集 B. 数据存储 C. 数据分析 D. 数据再利用7.当前，大数据产业发展的特点是（ACE ）（多选题）。

A．规模较大 B. 规模较小 C. 增速很快D. 增速缓慢E. 多产业交叉融合8.下列关于基于大数据的营销模式和传统营销模式的说法中，错误的是（AB ）（多选题）。

A．传统营销模式比基于大数据的营销模式投入更小B．传统营销模式比基于大数据的营销模式针对性更强C．传统营销模式比基于大数据的营销模式转化率低D．基于大数据的营销模式比传统营销模式实时性更强E．基于大数据的营销模式比传统营销模式精准性更强二、填空题1.大数据的4V特征是指规模庞大Volume、__种类繁多Variety ___、_变化频繁Velocity___和价值巨大但价值密度低Value。

2.人工智能的核心是算法设计，但是人工智能的基础却是数据_。