1、第2章 知识表示方法及搜索方法主要内容 知识表示 搜索方法知识表示 状态空间法状态空间法1 1、状态（、状态（StateState）的基本概念）的基本概念状态状态(state)(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合，其矢量形式如下：Q=q0,q1,qnT (2.1)式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=qk,q1k,，qnkT (2.2)算符算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态
2、空间问题的状态空间(state space)(state space)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。状态空间的表示法举例状态空间的表示法举例 问题：问题：猴子与香蕉的问题：在一个房间内有一只猴子、一个箱子和一束香蕉，初始的方位示意如图2-1所示。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能如图2-2所示摘到香蕉呢?知识表示状态空间法状态空间法 状态空间表示状态空间表示 用四元组（W，x，y，z）其中：W猴子的水平位置；x当猴子在箱
3、子顶上时取x=1；否则取x=0；Y箱子的水平位置；z当猴子摘到香蕉时取z=1；否则取z=0。算符：算符：（1）goto(U)猴子走到水平位置U；（2）pushbox(V)猴子把箱子推到水平位置V；（3）climbbox猴子爬上箱顶；（4）grasp猴子摘到香蕉。知识表示状态空间法状态空间法 求解过程求解过程 令初始状态为(a,0,b,0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U，0，b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有适用的操作 继续应用于每个状态，我们就能够得到状态空间图，如图2-3所示。从图中不难看出
4、，把该初始状态变换为目标状态的操作序列为：goto(b),pushbox(c),climbbox,grasp知识表示状态空间法状态空间法 状态空间图知识表示状态空间法状态空间法 问题归约法问题归约法 1 1、问题归约法的概念、问题归约法的概念 已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。2 2、问题归约法的组成部分、问题归约法的组成部分（1）一个初始问题描述；（2）一套把问题变换为子
5、问题的操作符；（3）一套本原问题描述。知识表示 示例：梵塔难题示例：梵塔难题 问题问题 有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部，如图2-4所示。要求：把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上，具体的移动过程如图2-5所示。知识表示问题归约法问题归约法 归约描述归约描述 问题归约方法是应用算符来把问题描述变换为子问题描述。归约过程如下：归约过程如下：（1）移动圆盘A和B至柱子2
6、的双圆盘难题；（2）移动圆盘C至柱子3的单圆盘难题；（3）移动圆盘A和B至柱子3的双圆盘难题。知识表示问题归约法问题归约法三阶梵塔问题的归约图知识表示问题归约法问题归约法 与或图表示法与或图表示法 与或图的概念与或图的概念 用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示。2 2、与或图的有关术语、与或图的有关术语 父节点父节点 是一个初始问题或是可分解为子问题的问题节点；子节点子节点 是一个初始问题或是子问题分解的子
7、问题节点；或节点或节点 只要解决某个问题就可解决其父辈问题的节点集合；与节点与节点 只有解决所有子问题，才能解决其父辈问题的节点集合；弧线弧线 是父辈节点指向子节点的圆弧连线；终叶节点终叶节点 是对应于原问题的本原节点。知识表示知识表示 与或树示意图与或图表示法与或图表示法知识表示 可解节点可解节点 与或图中一个可解节点的一般定义可以归纳如下：(1)终叶节点是可解节点(因为它们与本原问题相关连)。(2)如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解
8、的。不可解节点不可解节点 不可解节点的一般定义归纳于下：(1)没有后裔的非终叶节点为不可解节点。(2)如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。与或图表示法与或图表示法知识表示 谓词逻辑法 1 1、语法和语义、语法和语义 谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。原子公式是由若干谓词符号和项组成，只有当其对应的语句在定义域内为真时，才具有值T(真)；而当其对应的语
9、句在定义域内为假时，该原子公式才具有值F(假)。2 2、连词和量词、连词和量词 连词有(与)、(或)，全称量词(x)，存在量词(x)。原子公式是谓词演算的基本积木块，运用连词能够组合多个原子公式以构成比较复杂的合适公式。谓词逻辑法谓词逻辑法知识表示谓词逻辑法举例-以猴子和香蕉问题为例描述状态的谓词：AT(x,y)：x在y处ONBOX：猴子在箱子上HB：猴子得到香蕉个体域：x：monkey,box,bananay：a,b,c问题的初始状态AT(monkey,a)AT(box,b)ONBOX HB问题的目标状态AT(monkey,c)AT(box,c)ONBOX HB 谓词逻辑法谓词逻辑法知识表示
10、 描述操作的谓词描述操作的谓词 Goto(u,v)：猴子从u处走到v处 条件：ONBOX，AT(monkey,u)动作：删除表：AT(monkey,u)；添加表：AT(monkey,v)Pushbox(v,w)：猴子推着箱子从v处移到w处 条件：ONBOX，AT(monkey,v)，AT(box,v)动作：删除表：AT(monkey,v)，AT(box,v)添加表：AT(monkey,w)，AT(box,w)谓词逻辑法谓词逻辑法知识表示 Climbbox：猴子爬上箱子 条件：ONBOX，AT(monkey,w)，AT(box,w)动作：删除表：ONBOX；添加表：ONBOX Grasp：猴子摘
11、取香蕉 条件：ONBOX，AT(box,c)动作：删除表：HB；添加表：HB谓词逻辑法谓词逻辑法知识表示猴子摘香蕉的谓词逻辑法谓词逻辑法谓词逻辑法知识表示 语义网络法语义网络法 语义网络是奎廉(J.R.Quillian)1968年在研究人类联想记忆时提出的一种心理学模型，认为记忆是由概念间的联系实现的。随后，奎廉又把它用作知识表示。1972年，西蒙在他的自然语言理解系统中也采用了语义网络表示法。语义网络是一种表达能力强而且灵活的知识表示方法，目前已经广泛应用于人工智能领域，尤其是在自然语言处理方面。知识的语义网络表示法是通过节点和弧线来构成语义网络。语义网络法语义网络法知识表示 语义网络的基本
12、概念 语义网络是知识的一种结构化图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。语义网络表示由下列4个相关部分组成：(1)词法部分 决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。(2)结构部分 叙述符号排列的约束条件，指定各弧线连接的节点对。(3)过程部分 说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。(4)语义部分 确定与描述相关的(联想)意义的方法即确定有关节点的排列及其占有物和对应弧线。语义网络法语义网络法知识表示 语义网络具有下列特点：(1)能把实体的结构、属性与实体间的因果关系显式地和简明地表达出来，与实体相关的事
13、实、特征和关系可以通过相应的节点弧线推导出来。(2)由于与概念相关的属性和联系被组织在一个相应的节点中，因而使概念易于受访和学习。(3)表现问题更加直观，更易于理解，适于知识工程师与领域专家沟通。(4)语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定，因而得到的推理不能保证像谓词逻辑法那样有效。(5)节点间的联系可能是线状、树状或网状的，甚至是递归状的结构，使相应的知识存储和检索可能需要比较复杂的过程。语义网络法语义网络法知识表示 二元语义网络的表示二元语义网络的表示 用两个节点和一条弧线可以表示一个简单的事实，对于表示占有关系的语义网络，是通过允许节点既可以表示一个物体或一组物体
14、，也可以表示情况和动作。每一情况节点可以有一组向外的弧(事例弧)，称为事例框，用以说明与该事例有关的各种变量。例如：若有语义基元（A,R,B），其中，A、B分别表示两个结点，R表示A与B之间的某种语义联系，则它所对应的基本语义如图2-9所示：语义网络法语义网络法知识表示 语义网络法举例 例如：用语义网络表示：1）动物能运动、会吃；2）鸟是一种动物，鸟有翅膀、会飞；3）鱼是一种动物，生活在水中、会游泳。这个问题的语义网络图如图所示。语义网络法语义网络法知识表示 框架表示法框架表示法 框架表示法是在框架理论的基础上发展起来的一种结构化知识表示方法。框架理论是明斯基于1975年作为理解视觉、自然语言
15、对话及其它复杂行为的一种基础提出来的。框架理论认为，人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的。当遇到一个新事物时，就从记忆中找出一个合适的框架，并根据新的情况对其细节加以修改、补充，从而形成对这个新事物的认识。知识表示 框架的构成框架的构成框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可以拥有若干个值。一个框架的一般结构如下：框架名槽1侧面11值111 侧面12值121 槽2侧面21值211 槽n侧面n1值n11 侧面nm值nm1框架表示法框架表示法知识表示 较简单的情景是用框架来表示诸如人和房子等事物。例如例如，一个人可以用其职业、
16、身高和体重等项描述，因而可以用这些项目组成框架的槽。当描述一个具体的人时，再用这些项目的具体值填入到相应的槽中。表2-1给出的是描述John的框架。JOHNIsa:PERSONProfession:PROGRAMMERHeight:1.8mWeight:79kg框架表示法框架表示法知识表示 剧本表示法剧本表示法剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列，就像剧本中的事件序列一样，故称为“剧本”或脚本。剧本的构成剧本的构成一个剧本一般由以下各部分组成：(1)开场条件 给出在剧本中描述的事件发生的前提条件。(2)角色 用来表示在剧本所描述的事件中可能出现的有关人物的一些槽。(3)
17、道具 这是用来表示在剧本所描述的事件中可能出现的有关物体的一些槽。(4)场景 描述事件发生的真实顺序，可以由多个场景组成，每个场景又可以是其它的剧本。(5)结果 给出在剧本所描述的事件发生以后通常所产生的结果。知识表示 例子：例子：以餐厅剧本为例说明剧本各个部分的组成。开场条件开场条件(a)顾客饿了，需要进餐。(b)顾客有足够的钱。角色 顾客，服务员，厨师，老板。道具食品，桌子，菜单，钱。剧本表示法剧本表示法知识表示 场景：场景：5 5个场景个场景 场景1：进入餐厅(a)顾客走入餐厅。(b)寻找桌子。(c)在桌子旁坐下 场景2：点菜(a)服务员给顾客菜单。(b)顾客点菜。(c)顾客把菜单还给服
18、务员。(d)顾客等待服务员送菜。l场景3：等待(a)服务员把顾客所点的菜告诉厨师。(b)厨师做菜。场景4：吃菜(a)厨师把做好的菜给服务员。(b)服务员给顾客送菜。(c)顾客吃菜。场景：5个场景场景5：离开(a)服务员拿来帐单。(b)顾客付钱给服务员。(c)顾客离开餐厅。剧本表示法剧本表示法知识表示 结果结果(a)顾客吃了饭，不饿了。(b)顾客花了钱。(c)老板挣了钱。(d)餐厅食品少了。剧本表示法剧本表示法知识表示 剧本的推理剧本的推理一旦剧本被启用，则可以应用它来进行推理。其中最重要的是运用剧本可以预测没有明显提及的事件的发生。例如：对于以下情节：“昨晚，约翰到了餐厅。他点了牛排。当他要付
19、款时发现钱已用光。因为开始下雨了，所以他赶紧回家了“。推理：“昨晚，约翰吃饭了吗？”虽然上面的情节中没有提到约翰吃没吃饭的问题，但借助于餐厅剧本，可以回答：他吃了。因为启用了餐厅剧本，情节中的所有事件与剧本中所预测的事件序列相对应，可以推断出整个事件正常进行时所得出的结果。剧本表示法剧本表示法搜索技术 图搜索策略的定义图搜索策略的定义 图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。搜索技术 图搜索算法中的几个重要名词术语图搜索算法中的几个重要名词术语OPEN表与
20、CLOSE表节点深度：根节点深度=0；其它节点深度=父节点深度+1路径：设一节点序列为(n0,n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值：一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。扩展一个节点：生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。搜索技术 图搜索的一般过程图搜索的一般过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点 表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(
21、3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOS
22、ED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GO LOOP。搜索技术 图搜索方法分析：图搜索方法分析：图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败
23、告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。搜索技术 盲目搜索盲目搜索 盲目搜索是按预定的控制策略进行搜索，在搜索过程中获得的中间信 息不用来改进控制策略。本节主要介绍两种盲目搜索方法：宽度优先搜索和 深度优先搜索。宽度优先搜索宽度优先搜索1、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。2、特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。搜索技术 宽度优先搜索算法宽度优先搜索算法(1)把初始节点
24、s放入OPEN表；(2)若OPEN表为空，则问题无解，退出；(3)把OPEN表的第一个节点(记为节点n)取出放入CLOSE表；(4)考察节点n是否为目标节点。若是，则求得了问题的解，退出；(5)若节点n不可扩展，则转第2步；(6)扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点配置指向父节点的指针，然后转第2步。搜索技术例子：例子：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：初始状态：目标状态：2 3 1 2 3 1 8 4 8 4 7 6 5 7 6 5使用的操作有：使用的操作有：空格上移，空格下移，空格左移，空格右移宽度优先搜
25、索法宽度优先搜索法搜索技术宽度优先搜索法宽度优先搜索法搜索技术 深度优先搜索深度优先搜索1 1、定义、定义 在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。2 2、特点、特点 首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。搜索技术 深度优先搜索算法深度优先搜索算法(1)把初始节点s放入OPEN表；(2)若OPEN表为空，则问题无解，退出；(3)把OPEN表的第一个节点(记为节点n)取出放入
26、 CLOSE表；(4)考察节点n是否为目标节点。若是，则求得了问题的解，退出；(5)若节点n不可扩展，则转第2步；(6)扩展节点n，将其子节点放入到OPEN表的首部，并为每个子节点配置指向父节点的指针，然后转第2步。深度界限深度界限 为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。深度优先搜索法深度优先搜索法搜索技术例子：例子：把有界深度优先搜索（深度为4）应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：初始状态：目标状态：2 3 1 2 3
27、1 8 4 8 4 7 6 5 7 6 5使用的操作有：使用的操作有：空格上移，空格下移，空格左移，空格右移深度优先搜索法深度优先搜索法搜索技术深度优先搜索法深度优先搜索法搜索技术 启发式搜索启发式搜索 进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种 信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则 来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿 着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某 些估算节点“希望”的量度，这种量度叫做估价函数(evalution funct
28、ion)。为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 搜索技术 定义定义 用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索(best-first search)，而其算法就叫做有序搜索算法或最佳优先算法。尼尔逊(Nilsson)曾提出一个有序搜索的基本算法。估价函数f是这样确定的：一个节点的希望程度越大，其f值就越小。
29、被选为扩展的节点，是估价函数最小的节点。启发式搜索启发式搜索搜索技术 算法流程算法流程(1)把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。(2)如果OPEN是个空表，则失败退出，无解。(3)从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。(4)把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。(5)如果i是个目标节点，则成功退出，求得一个解。(6)扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：(a)计算f(j)。(b)如果j既不在OPEN表中，又不在CL
30、OSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找 到目标节点时记住一个解答路径。(c)如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则 (i)以此新值取代旧值。(ii)从j指向i，而不是指向它的父辈节点。(iii)如果节点j在CLOSED表中，则把它移回OPEN表。(7)转向(2)，即GO TO(2)。启发式搜索启发式搜索搜索技术例子：八数码难题例子：八数码难题 采用了简单的估价函数 f(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点 n
31、的数据库中错放的棋子个数。比如，起始节点棋局 2 8 3 1 6 4 7 5 的f值等于0+4=4。启发式搜索启发式搜索搜索技术启发式搜索启发式搜索搜索技术 A A*算法算法 A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。在A算法中，如果满足条件：h(n)h*(n),则A算法称为A*算法。几个记号几个记号 令k(ni，nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点，函数k没有定义)。于是，从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n,ti)给出。令h*(n)表示整个目标节点集合ti上所有k(n,ti)中最小的一个，因此
32、，h*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n，函数h*没有定义)。搜索技术 估价函数的定义估价函数的定义定义g*为 g*(n)=k(S,n)定义函数f*，使得在任一节点n上其函数值f*(n)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和，即 f*(n)=g*(n)+h*(n)希望估价函数f是f*的一个估计，此估计可由下式给出：f(n)=g(n)+h(n)其中：g是g*的估计；h是h*的估计。对于g(n)来说，一个明显的选择就是搜
33、索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)g*(n)。h*(n)的估计h(n)依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。把h叫做启发函数。A A*算法算法搜索技术 A A*算法举例算法举例 估价函数 f(n)=d(n)+p(n)其中：d(n)是搜索树中节点n的深度；p(n)用来计算对应于节点n 的数据库中错放的棋子的距离和。比如，起始节点棋局 2 8 3 1 6 4 7 5 的f值等于0+5=5。A A*算法算法搜索技术A A*算法算法
