第三章知识的状态空间表示法.pdf

《第三章知识的状态空间表示法.pdf》由会员分享，可在线阅读，更多相关《第三章知识的状态空间表示法.pdf（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 知识的状态空间表示法 1 课前思考：人类的思维过程，可以看作是一个搜索的过程。某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。2 学习目标：掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和 A 搜索算法，对典型问题，掌握启发式函数的定义方法。3 学习指南：了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下，程序实现每一个算法，求解一些典型的问题。4 难重点：回溯搜索算法、算法及其性质、改进的算法。5 知识点：本章所要的讨论的问题如下：有哪些常用的

2、搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。3.1 状态空间表示知识 一、状态空间表示知识要点 1状态 状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成：Q=q1，q2，qn 当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。2操作（规则或算符）操作（Operator）是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某个可用操作时，它将引起该状态中某一些

3、分量发生变化，从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。通常可表示为：F=f1,f2,fm 3状态空间 状态空间（State Space）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间。用三元组表示为：（Qs，F，Qg）Qs：初始状态，Qg：目标状态，F：操作（或规则）。4状态空间（转换）图 状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作。二、状态图搜索 1.搜索方

4、式 用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。2.搜索策略 大体可分为盲目搜索和启发式（heuristic）搜索两大类。搜索空间示意图 例 3.1 钱币翻转问题 设有三枚硬币，其初始状态为（反，正，反），允许每次翻转一个硬币（只翻一个硬币，必须翻一个硬币）。必须连翻三次。问是否可以达到目标状态（正，正，正）或（反，反，反）。问题求解过程如下：用数组表示的话，显然每一硬币需占一维空间，则用三维数组状态变量表示这个知识：Q=（q1,q2,q3）取 q=0 表示钱币的正面 q=1 表示钱币的反面 构成的问题状态空间显然为：Q0=（0，0，0），Q1=（0，0，1），Q2=（

5、0，1，0），Q3=（0，1，1）Q4=（1，0，0），Q5=（1，0，1），Q6=（1，1，0），Q7=（1，1，1）引入操作：f1：把 q1 翻一面。f2：把 q2 翻一面。f3：把 q3 翻一面。显然：F=f1，f2，f3 目标状态：（找到的答案）Qg=（0，0，0）或（1，1，1）例 3.2 分油问题。有两只空油瓶，容量分别为 8 斤和 6 斤，另有一个大油桶，里面有足够的油。我们可以任意从油桶中取出油灌满某一油瓶，也可以把某瓶中的油全部倒回油桶，两个油瓶之间可以互相灌。问如何在 8 斤油瓶中精确的得到 4 斤油。问题的求解显然用 2 维数组或状态空间描述比较合适，第一位表示 8 斤油

6、瓶油量，第二位表示 6 斤油瓶油量，构成整数序列偶（E，S）E：=0，1，2，3，4，5，6，7，8。表示 8 斤油瓶中含有的油量。S：=0，1，2，3，4，5，6。表示 6 斤油瓶中含有的油量。总结出如下分油操作规则：f1：8 斤油瓶不满时装满（E，S）且 E 8（8，S）f2：6 斤油瓶不满时装满（E，S）且 S 0（0，S）f4：6 斤油瓶不空时倒空（E，S）且 S 0（E，0）f5：8 斤油瓶内油全部装入 6 斤油瓶内（E，S）E 0 且 E+S 6（0，E+S）f6：6 斤油瓶内油全部装入 8 斤油瓶内（E，S）S 0 且 E+S 8（E+S，0）f7：用 6 斤油瓶内油去灌满 8

7、斤油瓶 （E，S）且 E 8 且 E+S 8（8，E+S-8）f8：用 8 斤油瓶内油去灌满 6 斤油瓶 （E，S）且 S Dm GO LOOP;7、EXPAND(n)mi,G:=ADDmi,G;8、IF 目标在mi中 THEN EXIT(SUCCESS);9、ADD(mi,OPEN),并标记 mj 到 n 指针;10、将 mi 重排序到 open 表头部。11、GO LOOP;深度优先搜索性质 一般不能保证找到最优解 当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制 最坏情况时,搜索空间等于穷举 与回溯法的差别:图搜索 是一个通用的与问题无关的方法 3.4 回溯策略 所谓回溯策略

8、，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探用过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。一个递归的例子 Int abc(int n)abc(m);八数码游戏回溯控制方式 新生成的状态在通向初始状态的路径上已出现过；从初始状态开始，应用的

9、规则数目达到所规定的数目之后还未找到目标状态（这一组规则的数目实际上就是搜索 对当前状态，再没有可应用的规则。回溯搜索算法 BACKTRACK（DATA）功能：如果从当前状态 DATA 到目标状态有路径存在，则返回以规则序列表示的从 DATA 到目标状态的路径（以规则表的形式表示）；如果从当前状态 DATA 到目标状态没有路径存在，则返回 FAIL。递归过程 BACKTRACK（DATA）IF TERM（DATA），RETURN NIL；TERM 取真即找到目标，则过程返回空表 NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND 取真，即该状态不合法，则过程返回

10、FAIL，必须回溯。RULES：APPRULES（DATA）；APPRULES 计算 DATA 的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给 RULES。LOOP：IF NULL（RULES），RETURN FAIL；NULL 取真，即规则用完未找到目标，过程返回FAIL，必须回溯。R：FIRST（RULES）；取头条可应用规则。RULES：TAIL（RULES）；删去头条规则，减少可应用规则表的长度。RDATA：GEN（R，DATA）；调用规则 R 作用于当前状态，生成新状态。PATH：BACKTRACK（RDATA）；对新状态递归调用本过程。IF PATHFAIL，GO

11、LOOP；当 PATHFAIL 时，递归调用失败，则转移调用另一规则进行测试。RETURN CONS（R，PATH）；过程返回解路径规则表（或局部解路径子表）。回溯搜索算法（）BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：同前面的算法一样，是以规则序列表示的路径表（当求解成功时），或者是 FAIL（当求解失败时）。回溯搜索算法（续）DATA：FIRST（DATALIST）；设置 DATA 为当前状态 IF MEMBER（DATA，TAIL（DATALIST)，RETURN FAIL；TAIL 是取尾操作，表示取表 DATALIST中除了第一个元素

12、以外的所有元素。如果 DATA 在 TAIL（DATALIST）中存在，则表示有环路出现，过程返回 FAIL，必须回溯。IF TERM（DATA），RETURN NIL；TERM 取真即找到目标，则过程返回空表 NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND 取真，即该状态不合法，则过程返回 FAIL，必须回溯。IF LENGTH（DATALIST）BOUND，RETURN FAIL；LENGTH 计算 DATALIST 的长度，即搜索的深度，当搜索深度大于给定值 BOUND 时，则过程返回 FAIL，必须回溯。RULES：APPRULES（DATA）；APP

13、RULES 计算 DATA 的可应用规则集，依某种原则（任意排列或按启发式准则排列）排列后赋给 RULES。LOOP：IF NULL（RULES），RETURN FAIL；NULL 取真，即规则用完未找到目标，过程返回FAIL，必须回溯。R：FIRST（RULES）；取头条可应用规则。RULES：TAIL（RULES）；删去头条规则，减少可应用规则表的长度。RDATA：GEN（R，DATA）；调用规则 R 作用于当前状态，生成新状态。RDATALIST:CONS(RDATA，DATALIST)；将新状态加入到表 DATALIST 中。PATH：BACKTRACK1（RDATALIST）；递归调

14、用本过程。IF PATHFAIL，GO LO0P；当 PATHFAIL 时，递归调用失败，则转移调用另一规则进行测试。RETURN CONS（R，PATH）；过程返回解路径规则表（或局部解路径子表）。2.1 回溯策略（Backtracking Strategies）例：四皇后问题 Q Q Q Q 存在问题及解决办法：问题：深度问题 死循环问题 解决办法：对搜索深度加以限制 记录从初始状态到当前状态的路径 一些深入的问题 失败原因分析、多步回溯 Q Q 一些深入的问题（续）回溯搜索中知识的利用 基本思想（以皇后问题为例）：尽可能选取划去对角线上位置数最少的 Q Q 3.5 状态空间的与/或树表示

15、法 1、分解（与树）把一个复杂的问题变成简单的子问题，各子问题又可以化成更为简单的子问题，重复此过程，直到不能分解为止。然后对各子问题求解，最后把各子问题复合起来就是问题的解。2、等价变换（或树）通过同结构的等价变换或同态的等价变换把问题分解成比较容易解的子问题，P1，P2，P3任何一个子问题有解，则问题 P 就可解，称 P1，P2，P3 之间存在“或”的关系，节点 P 成为“或”节点，由 P1，P2，P3，P 之间构成的树为“或”树。几个概念（1）父问题、子问题：问题空间是由一个个问题组成的空间，在问题求解中，用一个节点代表一个问题，若节点 A 有一边通向 B，则表示 A 的解决有赖于 B

16、的解决。A 称为父问题，B 称为子问题。（2）本原问题：不能再分解或变换，而且直接可解的子问题。（3）端节点与终止节点：没有子节点的节点，本原问题对应的节点是终止节点。注意，终止节点一定是端节点，但端节点不一定是终止节点。与或图的搜索:基本概念：Q Q 与或图是一个超图，节点间通过连接符连接。K-连接符：可解节点：终节点是可解节点；若非终节点有“或”子节点时，当且仅当其子节点至少有一能解，该非终节点才可解；若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节点才可解。不可解节点 没有后裔的非终节点是不可解节点；若非终节点有“或”子节点时，当且仅当所有子节点均不能解时，该非终节点才不可解

17、；若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不可解。“与/或”树的搜索过程 1.把初始节点 S0 放入 OPEN 表；2.移出 OPEN 表的第一个节点 N 放入 CLOSED 表，并冠以序号 n；3.若节点 N 可扩展，则做下列工作：(1)扩展 N,将其子节点配上指向父节点的指针后放入 OPEN 表；(2)考察这些子节点中是否有终止节点。(3)删去 OPEN 表中那些具有可解先辈的节点（因为其先辈节点已经可解，故已无再考察该节点的必要），转步骤 2；4.若 N 不可扩展，则做下列工作：(1)标记 N 为不可解节点，然后由它的不可解返回推断其先辈节点的可解性，并对其中的

18、不可解节点进行标记。如果初始节点 S0 也被标记为不可解节点，则搜索失败，退出。(2)删去 OPEN 表中那些具有不可解先辈的节点（因为其先辈节点已不可解，故已无再考察这些节点的必要），转步骤 2；与状态图搜索一样，搜索成功后，解树已经记录在 CLOSED 表中。这时需按指向父节点的指针找出整个解树。例 3.9 三阶梵塔问题 设有 A，B，C 三个金片（盘）以及三个钢针，盘按自上而下从小到大的顺序穿在 1 号钢针上，要求将它们全部移到 3 号钢针上。规则：一次只能搬移一个金片，任何时刻都不能把大的金片压在小的金片上，2 号钢针作为过渡使用。解法 1：用状态转换图法。用三维状态空间来表示知识或过

19、程。（i，j，k）i 表示 C 片所钢针号，j 表示 B 片所在钢针号，k 表示 A 中所在钢针号。显然，组成的状态空间有 27 个（3*3*3）S0=（1，1，1）S1=（1，1，2）S2=（1，1，3）S3=（1，2，1）S4=（1，2，2）S5=（1，2，3）S6=（1，3，1）S7=（1，3，2）S8=（1，3，3）S9=（2，1，1）S10=（2，1，2）S11=（2，1，3）S12=（2，2，1）S13=（2，2，2）S14=（2，2，3）S15=（2，3，1）S16=（2，3，2）S17=（2，3，3）S18=（3，1，1）S19=（3，1，2）S20=（3，1，3）S21=（3

20、，2，1）S22=（3，2，2）S23=（3，2，3）S24=（3，3，1）S25=（3，3，2）S26=（3，3，3）依题意规则可用 18 个状态空间表示算子，A（），B（），C（）A（1，2）表示从 1 号针移到 2 号针，以下类推：A 盘共有 6 种搬移规则。A（1，3）A（2，1）.A（3，1）A（3，2）B（1，2）B（1，3）B（3，1）B（3，2）C（1，2）C（1，3）C（3，1）C（3，2）解法 2：用“与/或”树解题 为把 3 个金片移到 3 号针可分解成如下步骤：1）把 A，B 金片移到 2 号针问题，双片移动问题。2）把 C 片移到 3 号针问题，终止节点，单片移动。3

21、）把 A，B 金片移到 3 号针问题，双片移动问题。用“=”表示状态变换，则由 博弈树的搜索 博弈问题:双人 一人一步 双方信息完备 零和 分钱币问题:中国象棋问题:每个势态有 40 种不同的走法，如果一盘棋双方平均走 50 步，则搜索的位置有(402)50=10160，即深度达 100 层，总节点数约为 10161 个。假设一毫微秒走一步,约需 10145 年。结论：不可能穷举。极小极大过程：一字棋 在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。设程序方 MAX 的棋子用（）表示，对手 MIN 的棋子用（）表示，MAX 先走。静态估计函数 f（p

22、）规定如下：若 p 对任何一方来说都不是获胜的格局，则 f（p）（所有空格都放上 MAX 的棋子之后，MAX 的三子成线（行、列、对角）的总（所有空格都放上 MIN 的棋子之后，MIN 的三子成线（行、列、对角）的总数）若 p 是 MAX 获胜的格局，则 f（p）；若 p 是 MIN 获胜的格局，则 f（p）。-搜索过程 极大节点的下界为 极小节点的上界为 剪枝的条件：（后继层）（先辈层），剪枝；（后继层）（先辈层），剪枝。简记为：极小极大，剪枝；极大极小，剪枝；一字棋第一阶段-剪枝方法 -搜索过程的博弈树 3.7 启发式搜索 启发式图搜索 利用知识来引导搜索,以达到减少搜索范围,降低问题复杂

23、度的目的 启发信息的强度 强：降低搜索工作量,但可能导致找不到最优解 弱：一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解 希望：引入启发知识,在保证找到最佳解的情况下,尽可能减少搜索范围,提高搜索效率 基本思想：定义一个评价函数 f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展 启发式搜索算法 A(A 算法)评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数 h(n)：启发函数 符号的意义 g*(n):从 s 到 n 的最短路径的耗散值 h*(n):从 n 到 g 的最短路径的耗散值 f*(n)=g*(n)+h*(n):从 s 经过 n 到 g 的最短路

24、径的耗散值 g(n)、h(n)、f(n)分别是 g*(n)、h*(n)f*(n)的估计值 A 算 法 1.OPEN:=(s),f(s)=g(s)+h(s);2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n,CLOSED);6.EXPAND(n)mi,计算 f(n,mi):=g(n,mi)+h(mi)ADD(mi,OPEN),标记 mi 到 n 的指针 若 mi 在 open 表或 closed 表中有重复，根据耗散值确定取舍。7.OPEN

25、 中的节点按 f 值从小到大排序 8.GO LOOP 一个 A 算法的例子 h 计算举例 21 82 33 18 60 44 77 6 55 h(n)=4 2.最佳图搜索算法 A*(A*算法)在 A 算法中如果满足条件 h(n)h*(n)则 A 算法称为 A*算法 89 A*条件举例 8 数码问题 h1(n)=“不在位”的将牌数 h2(n)=将牌“不在位”的距离和 21 82 33 18 60 44 77 6 55 h1(n)=4 h2(n)=5 A*算法的性质 A*算法的假设 设 ni,nj 是任意两个节点,有:C(ni,nj)其中为大于 0 的常数 几个等式 f*(s)=f*(t)=h*(

26、s)=g*(t)=f*(n)其中 s 是初始节点,t 是目标节点,n 是 s 到 t 的最佳路径上的节点 定理 1：对有限图，如果从初始节点 s 到目标节点 t 有路径存在，则算法 A 一定成功结束。引理 2.1 对无限图,若有从初始节点 S 到目标节点 t 的路径,则 A*不结束时,在 OPEN 表中即使最小的一个 f 值也将增到任意大,或有 f(n)f*(s)引理 2.2 A*结束前,OPEN 表中必存在一个节点 n,n 在最佳路径上且满足 f(n)f*(s)f(n)=g(n)+h(n)=g*(n)+h(n)g*(n)+h*(n)=f*(n)=f*(s)定理 2 对无限图,若从初始节点 s

27、 到目标节点 t 有路径存在,则 A*一定成功结束 证明：引理 2.1:A*如果不结束,则 OPEN 中所有的 n 有 f(n)f*(s)引理 2.2:在 A 结束前,必存在节点 n,使得 f(n)f*(s)所以,如果 A*不结束,将导致矛盾 推论 2.1:OPEN 表上任意一具有 f(n)f*(s)由引理 2.2 知结束前 OPEN 中存在 f(n)f*(s)的节点 n,所以 f(n)f*(s)h1(n),则在一条从 s 到 t 的路径的隐含图上,搜索结束时,由 A2 所扩展的每一个节点,也必定由 A1 所扩展,即 A1 所扩展的节点数至少和 A2 一样多.简写:如果 h2(n)h1(n)(

28、目标节点除外),则 A1 扩展的节点数 A2 扩展的节点数.注意:在定理 4 中,评价指标是”扩展的节点数”也就是说,同一个节点无论被扩展多少次,都只计算一次.定理 4 的证明 使用数学归纳法,对节点的深度进行归纳.(1)当 d(n)=0 时,即只有一个节点,显然定理成立.(2)设 d(n)k 时,定理成立.(归纳假设)(3)当 d(n)=k+1 时,用反证法.设存在一个深度为 k+1 的节点 n,被 A2 扩展,但没有被 A1 扩展.而由假设,A1 扩展了 n 的父节点，即 n 已经被生成了。因此当 A1 结束时，n 将被保留在 OPEN 中。n 没有被 A1 选择扩展，有 f1(n)f*(

29、s)，即 g1(n)+h1(n)f*(s)所以 h1(n)f*(s)g1(n)（1）另一方面 A2 扩展了 n，有 f2(n)f*(s)，即 g2(n)+h2(n)f*(s)所以 h2(n)f*(s)g2(n)（2）由于 d=k 时，A2 扩展的节点，A1 也一定扩展，故有 g1(n)g2(n)（因 A1 扩展的节点数可能较多）所以 h1(n)f*(s)g1(n)f*(s)g2(n)（3）比较式（2）、（3）可得：至少在节点 n 上有 h1(n)h2(n)，这与定理的前提条件矛盾，因此存在节点 n 的假设不成立。证毕 102 对 h 的评价方法：平均分叉数：设共扩展了 d 层节点，共搜索了 N

30、 个节点，则：其中 b*称为平均分叉数 b*越好，说明 h 效果越好 实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化 对 h 的评价举例：例：数码问题，随机产生若干初始状态 使用 h1：d=14,N=539,b*=1.44 d=20,N=7276,b*=1.47 使用 h2：d=14,N=113,b*=1.23 d=20,N=676,b*=1.27 A*的复杂性：一般说来，*的算法复杂性是指数型的,可以证明当且仅当以下条件成立时：abs(h(n)-h*(n)O(log(h*(n)*的算法复杂性才是非指数型的，但是通常情况下，h 和 h*的差别至少是和离目标的距离成正比的 A*

31、算法的改进 在 A 算法的第六步，对于 ml 类节点，存在重新放回到 OPEN 表的可能，因此一个节点有可能被反复扩展多次。因此单纯用扩展的节点数并不能客观地来评判搜索算法的好坏。因为即便是扩展的节点数比较少，但如果很多节点被多次重复扩展的话，搜索效率同样是很低的。出现多次扩展节点的原因 主要就是因为在扩展一个节点时，A*并不能保证此时就已经找到了从初始节点 s 到当前节点n 的最短路径，使得算法在第六步，有可能将其重新放回到 OPEN 表中，而放入 OPEN 表以后，该节点就有可能被再次扩展。解决的途径：对启发函数 h 进一步加上限制 使得 A*算法在扩展一个节点 n 时，就已经找到了从初始

32、节点 s 到当前节点 n 的最短路径 对算法加以改进 能否对算法加以改进，避免或减少节点的多次扩展 改进的条件：可采纳性不变 不多扩展节点 不增加算法的复杂度 对 h 加以限制 定义：一个启发函数 h，如果对所有节点 ni 和 nj（nj 是 ni 的子节点），都有 h(ni)-h(nj)C(ni，nj)或 h(ni)C(ni，nj)h(nj)且 h(t)0，则称该 h 函数满足单调限制条件。h 单调的性质：定理 5：若 h(n)满足单调限制条件，则 A*扩展了节点 n 之后，就已经找到了到达节点 n 的最佳路径。即若 A*选 n 来扩展，在单调限制条件下有 g(n)=g*(n)。定理 5 的

33、证明：由单调限制条件，对 P 中任意结点 ni 有 h(ni)C(ni，ni+1)+h(ni+1)g*(ni)+h(ni)g*(ni)+C(ni，ni+1)+h(ni+1)g*(ni+1)+h(ni+1)g*(n)+h(n)而在于 f(n)=g(n)+h(n)f(ni+1)所以：g(n)g*(n)（最小）只能是：g(n)=g*(n)h 单调的性质（续）：定理 6：若h(n)满足单调限制，则由A*所扩展的节点序列，其f值是非递减的，即f(ni)f(nj)。证明：由单调限制条件：h(ni)-h(nj)C(ni,nj)即 f(ni)-g(ni)-f(nj)+g(nj)C(ni,nj)f(ni)-g(ni)-f(nj)+g(ni)C(ni,nj)C(ni,nj)f(ni)-f(nj)0。证毕 h 单调的例子：8 数码：h 为“不在位的将牌数”101)()(jinhnh h(t)=0;C(ni,nj)=1 满足单调条件。对算法加以改进：一些结论：OPEN 表中任意满足 f(n)f*(s)的节点都会被扩展。A*选作扩展的任意节点都满足 f(n)f*(s)。其它的一些搜索算法：爬山法（局部搜索算法）随机搜索算法 动态规划算法