当前位置：文档之家 › D-启发式搜索-人工智能(AI)

D-启发式搜索-人工智能(AI)

  • 格式：ppt
  • 大小：1006.50 KB
  • 文档页数：72

下载文档原格式

  / 72

合集下载

浅谈人工智能中的启发式搜索策略

浅谈人工智能中的启发式搜索策略

浅谈人工智能中的启发式搜索策略
一、启发式策略
启发式策略是指在解决复杂问题时，根据人的经验和技巧来寻求最优解的方法。

它是人工智能领域中的一种和规划技术，可以解决形式化的各种问题。

启发式策略广泛应用于机器学习、图形图计算、机器人控制和计算机图形学等多种领域。

启发式策略包括：A*算法、B*树算法、启发式和动态规划等。

A*算法是一种非常有效的启发式方法，它采用了一个启发函数来估计待访问节点的最优价值，从而可以根据最小价值节点而进行，的效果比较好。

B*树算法是一种静态的启发式方法，该算法在每一步都可以通过比较不同节点价值来确定最优路径，从而更有效地出最优路径。

启发式和动态规划都是一种在状态空间中采取其中一种方法或策略以获得最优解的技术，两者最大的不同点在于，启发式依赖于当前状态，动态规划则更倾向于最终目标。

二、应用
启发式策略广泛应用于人工智能领域，它可以用来解决各种形式化问题，如游戏、自然语言处理问题等。

《人工智能基础》名词术语

《人工智能基础》名词术语

1，AI:AI是人工智能英文单词Artificial Intelligence的缩写。

2，人工智能:人工智能是研究如何制造出人造的智能机器或智能系统，来模拟人类智能活动的能力，以延伸人们智能的科学。

3，产生式系统:产生式系统是Post于1943年提出的一种计算形式体系里所使用的术语，主要是使用类似于文法的规则，对符号串作替换运算。

到了60年代产生式系统成为认知心理学研究人类心理活动中信息加工过程的基础，并用它来建立人类认识的模型。

到现在产生式系统已发展成为人工智能系统中最典型最普遍的一种结构，例如目前大多数的专家系统都采用产生式系统的结构来建造。

产生式系统由综合数据库、一组产生式规则（规则集）和一个控制系统（控制策略）三部分组成，称为产生式系统的三要素。

4，产生式系统的三要素:产生式系统的三要素是综合数据库、一组产生式规则（规则集）和一个控制系统（控制策略）。

5，产生式规则:产生式规则是知识表示的一种形式，其形式如下： IF <前件> THEN <后件> 其中规则的<前件>表达的是该条规则所要满足的条件，规则的<后件>表示的是该规则所得出的结论，或者动作。

规则表达的可以是与待求解的问题有关的客观规律方面的知识，也可以是对求解问题有帮助的策略方面的知识。

6，八数码游戏（八数码问题）:八数码游戏（八数码问题）描述为：在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。

棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。

这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。

7，传教士和野人问题（M-C问题）:传教士和野人问题描述为：有N个传教士和N个野人来到河边准备渡河，河岸有一条船，每次至多可供k人乘渡。

浅谈人工智能中的启发式搜索策略

浅谈人工智能中的启发式搜索策略

蚁群算法
总结词
模拟蚂蚁觅食过程的群体智能优化算法
详细描述
蚁群算法是一种模拟蚂蚁觅食过程的群体智能优化算法，通过模拟蚂蚁的信息素传递过程，逐渐建立起最优路 径。其优点在于能够在复杂环境中寻找到最优解，适用于解决组合优化问题，如旅行商问题、图的着色问题等 。
粒子群优化算法
总结词
模拟鸟群、鱼群行为的全局优化算法
人工智能的未来趋势
未来人工智能的发展将更加注重跨学科融合，包括计算机科 学、心理学和哲学等多个领域，同时人工智能的应用也将更 加广泛和深入，涉及的领域也将更加广泛和多样化。
03
启发式搜索策略简介
启发式搜索的定义与特点
定义
启发式搜索是一种基于人类认知和解决问题的启发式方 法的搜索策略，它通过利用一些特定的提示或启发式信 息来指导搜索方向，从而减少搜索的盲目性和无序性， 提高搜索效率。
展望未来-启发式搜索策略在人工智 能中的发展前景
基于启发式搜索的混合优化算法
总结词
结合了启发式搜索策略和混合算法的优化方 法，能够处理复杂的多变量优化问题，提高 搜索效率。
详细描述
混合优化算法是一种结合了不同优化技术的 算法，旨在解决单一方法无法有效处理的复 杂问题。启发式搜索策略为混合算法提供了 重要的启示，通过混合启发式搜索策略和传 统优化算法，可以更好地处理多变量优化问
题，提高搜索效率。
基于启发式搜索的多目标优化算法
总结词
利用启发式搜索策略处理多目标优化问题 ，能够同时满足多个优化目标，提高整体 优化效果。
VSBiblioteka 详细描述多目标优化问题是一种需要同时满足多个 优化目标的复杂问题。传统的优化算法往 往难以同时满足所有目标，而启发式搜索 策略可以提供一种有效的解决方案。通过 结合启发式搜索策略和多目标优化算法， 可以更好地解决这类问题，提高整体优化 效果。

浅谈人工智能中的启发式搜索策略

浅谈人工智能中的启发式搜索策略

在自然语言处理中的应用
文本分类
在自然语言处理中，文本分类是一个重要的任务。启发式搜索策略可以帮助 算法对文本进行分词，提取特征，并选择最能代表文本类别的特征，从而提 高文本分类的准确性。
信息检索
在信息检索中，用户输入查询关键词后，系统需要从大量的文档中检索出与 查询相关的信息。启发式搜索策略可以帮助系统根据关键词语义信息，快速 定位到相关文档，并返回最相关的结果，提高用户体验。
在机器学习中的应用
特征选择
机器学习算法通常需要对输入数据进行特征选择，以降低维 度并提高算法性能。启发式搜索策略可以帮助算法选择更有 效的特征，从而提高分类和回归的准确性。
模型优化
机器学习算法中的模型优化是关键，启发式搜索策略可以通 过试错的方式来寻找最优的超参数配置，提高模型的性能和 泛化能力。
利用多智能体的协同作用，提高搜索效率。多个智能体可以分工合作，共同解决问题。
启发式搜索策略的未来发展趋势
01
可解释性
研究如何提高启发式搜索策略的可解释性，以便开发人员能够更好地
理解搜索算法的内部工作原理。
02
多任务学习
将多个任务集成到一个统一的框架中，使搜索策略能够适应不同任务
的要求。
03
强化学习
研究展望
1
未来将继续深入研究该启发式搜索策略的性能 和适用范围，希望能够进一步拓展其应用领域 。
2
将探索将该启发式搜索策略与其他人工智能技 术相结合，以进一步提高其性能和鲁棒性。
3
将致力于推广该启发式搜索策略在实际应用领 域的应用，希望能够为解决实际问题提供更多 帮实际问题中的应用案例
分析
在路径规划中的应用案例
总结词
高效、实用

人工智能应用考试题及答案

人工智能应用考试题及答案

人工智能应用考试题及答案一、单选题（共40题，每题1分，共40分）1、计算智能和感知智能的关键技术已经取得较大突破，弱人工智能应用条件基本成熟。

但（）的算法尚未突破，前景仍不明朗。

A、认知智能B、视频智能C、语音智能D、触觉智能正确答案：A2、下列哪些网用到了残差连接A、ResNetB、BERTC、FastTextD、GoogLeNet正确答案：A3、例如在生产与采购环节，典型的AI应用场景包括智能质检，利用（）等AI技术可代替人力或者协助人力完成对缺陷商品进行识别。

A、机器推理B、语音识别C、机器视觉D、机器学习正确答案：C4、用Tensorflow处理图像识别任务时，若输入数据的形状为[64,224,224,3]，下面说法正确的是（）A、以上选项均不正确B、每一张图片都是三通道图片C、模型一次处理224张图片（batchsize为224）D、每一张图片都是二值图片正确答案：B5、关于线性回归的描述,以下说法正确的有:A、多重共线性会使得参数估计值方差减小B、基本假设包括不服从正态分布的随机干扰项C、基本假设包括随机干扰项是均值为0的同方差正态分布D、基本假设包括随机干扰项是均值为0,方差为1的标准正态分布正确答案：C6、以下哪种神经网络技术可以用于语音识别的处理？A、深层神经网络B、循环神经网络C、卷积神经网络D、浅层神经网络正确答案：B7、自然语言处理机制涉及两个流程，其中，( )是指计算机能够理解自然语言文本的意义。

A、自然语言输入B、自然语言生成C、自然语言理解D、自然语言处理正确答案：C8、下列哪项网络不属于常用的深度神经网络：()A、AlexNetB、VGGC、HopField网络D、ResNet正确答案：C9、如果问题存在最优解，则下面几种搜索算法中（）必然可以得到最优解A、深度优先搜索B、广度优先搜索C、有界深度优先搜索D、启发式搜索正确答案：B10、下列选项中，属于图像识别技术应用的是（）A、制作pptB、人脸识别支付C、编写word文档D、制作多媒体正确答案：B11、生物特征识别技术不包括（）。

（人工智能）人工智能复习题及答案

（人工智能）人工智能复习题及答案

（⼈⼯智能）⼈⼯智能复习题及答案（⼈⼯智能）⼈⼯智能复习题及答案填空：1.⼈⼯智能的研究途径有⼼理模拟、⽣理模拟和⾏为模拟。

2.任意列举⼈⼯智能的四个应⽤性领域智能控制、智能管理、智能决策、智能仿真。

3.⼈⼯智能的基本技术包括表⽰、运算、搜索归纳技术、联想技术。

4.谓词逻辑是壹种表达能⼒很强的形式语⾔，其真值的特点和命题逻辑的区别是（10）。

5.谓词逻辑中，重⾔式（tautlogy）的值是（11）。

6.设P是谓词公式，对于P的任何论域，存于P为真的情况，则称P为（12）。

7.于著名的医疗专家系统MYCIN中规定，若证据A的可信度CF（A）=0，则意味着13 ，CF（A）=-1，则意味着（14），CF（A）=1，则意味着（15）。

8.谓词公式G是不可满⾜的，当且仅当对所有的解释（16）。

9.谓词公式和其⼦句集的关系是（17）。

10.利⽤归结原理证明定理时，若得到的归结式为（18），则结论成⽴。

11.若C1=┐P∨Q，C2=P∨┐Q，则C1和C2的归结式R（C1，C2）= （19）。

12.若C1=P(x)∨Q(x)，C2=┐P(a)∨R(y)，则C1和C2的归结式R（C1，C2）= （20）。

13.有谓词公式G，置换δ，则G·ε= （21），δ·ε= （22）。

14.有⼦句集S=｛P(x),P(y)｝，其MGU= （23）。

15.于归结原理中，⼏种常见的归结策略且且具有完备性的是（24），（25），（26）。

16.状态图启发式搜索算法的特点是（27）。

17.⼴度优先搜索算法中，OPEN表的数据结构实际是壹个（28），深度优先搜索算法中，OPEN表的数据结构实际是壹个（29）。

18.产⽣式系统有三部分组成（30），（31）和推理机。

其中推理可分为（32）和（33）。

19.专家系统的结构包含⼈机界⾯、（34），（35），（36），（37）和解释模块。

20.于MYCIN推理中，对证据的可信度CF（A）、CF（A1）、CF（A2）之间，规定如下关系：CF（~A）= （38），CF（A1∧A2）= （39），CF（A1∨A2）= （40）。

人工智能原理MOOC习题集及答案北京大学王文敏

人工智能原理MOOC习题集及答案北京大学王文敏Quizzes for Chapter 1 1 单选(1 分)图灵测试旨在给予哪一种令人满意的操作定义得分/ 总分A.人类思考B.人工智能C.机器智能D.机器动作正确答案：C 你选对了 2 多选(1 分)选择以下关于人工智能概念的正确表述得分/总分A.人工智能旨在创造智能机器该题无法得分/B.人工智能是研究和构建在给定环境下表现良好的智能体程序该题无法得分/}得分/C.人工智能将其定义为人类智能体的研究该题无法D.人工智能是为了开发一类计算机使之能够完成通常由人类所能做的事该题无法得分/ 正确答案：A、B、D 你错选为A、B、C、D 3 多选(1 分)如下学科哪些是人工智能的基础得分/总分A.经济学B.哲学C.心理学D.数学正确答案：A、B、C、D 你选对了4 多选(1 分)下列陈述中哪些是描述强 AI(通用 AI)的正确答案得分/ 总分；能力A.指的是一种机器，具有将智能应用于任何问题的B.是经过适当编程的具有正确输入和输出的计算机，因此有与人类同样判断力的头脑C.指的是一种机器，仅针对一个具体问题D.其定义为无知觉的计算机智能，或专注于一个狭窄任务的 AI 正确答案：A、B 你选对了 5 多选(1 分)选择下列计算机系统中属于人工智能的实例得分/总分搜索引擎B.超市条形码扫描器C.声控电话菜单该题无法得分/D.智能个人助理该题无法得分/（正确答案：A、D 你错选为 C、D 6 多选(1 分)选择下列哪些是人工智能的研究领域得分/总分A.人脸识别B.专家系统C.图像理解D.分布式计算正确答案：A、B、C 你错选为 A、B 7 多选(1 分)考察人工智能(AI)的一些应用，去发现目前下列哪些任务可以通过 AI 来解决得分/总分A.以竞技水平玩德州扑克游戏!B.打一场像样的乒乓球比赛C.在 Web 上购买一周的食品杂货D.在市场上购买一周的食品杂货正确答案：A、B、C 你错选为 A、C 8 填空(1 分)理性指的是一个系统的属性，即在_________的环境下做正确的事。

浅谈人工智能中的启发式搜索策略


启发式搜索策略的常见算法
Dijkstra算法
Dijkstra算法也是一种常见的启发式搜索算法，它主要用于解决带权图的最短路径问题。该算法通过不断扩展当前节点，并使用启发式函数来更新每个节点的距离。
Bellman-Ford算法
Bellman-Ford算法是一种解决动态规划问题的启发式搜索算法，它通过迭代更新每个节点的距离来找到最短路径。与Dijkstra算法不同的是，Bellman-Ford算法可以处理带有负权边的图。
02
它将问题分解为若干个状态，并从初始状态开始搜索，通过不断迭代，寻找目标状态。
03
在每个迭代过程中，启发式搜索策略会评估当前状态到目标状态的代价，并选择最小代价的状态进行扩展，直到找到目标状态或确定无法找到目标状态。
A*算法
A*算法是一种广泛使用的启发式搜索算法，它通过使用启发式函数来评估每个状态的代价，并选择最小代价的状态进行扩展。
xx年xx月xx日
浅谈人工智能中的启发式搜索策略
引言启发式搜索策略的基本概念与原理启发式搜索策略在人工智能中的应用启发式搜索策略的优缺点分析未来展望与研究方向结论
contents
目录
引言
01
人工智能（Artificial Intelligence，简称 AI）是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。
鼓励探索该算法在实际应用场景中的应用价值和可能性
THANKS
谢谢您的观看
定义
AI 技术正在改变人类的生活方式和社会结构，应用在各个领域如医疗、金融、交通、制造等，帮助人们解决复杂的问题和提高效率。
重要性
人工智能的定义与重要性
VS
启发式搜索策略是一种基于问题特定的信息搜索策略，它利用问题特定的知识来指导搜索方向，从而减少搜索范围，提高搜索效率。

人工智能导论-第3章 搜索求解1 - 启发式搜索

个标号为A的结点所对应状态相同，但是这三个
节点在搜索树中却是不同结点，因为它们分别代
表了从初始状态出发到达城市 A 的三条不同路径。
这三个结点表示的路径分别为：A → B → A、
A → D → A和A → E → A。因此需要注意的是，在
搜索树中，同一个标号一定表示相同的状态，其
含义为智能体当前所在的城市，但是一个标号可
达每个状态（城市）的最短路径。在处理通向相同状态的不同路径时，算法会更新当前的
前驱状态。
图3.7 修改后图搜索A*算法扩展A→E→G结点，红色实线表示
当前搜索树中的边，虚线表示不在搜索树中的边
搜索算法：A*算法性能分析
图搜索A*算法满足最优性（方法二）：
要求启发函数满足一致性
引理3.1：启发函数满足一致性条件时，给定一个从搜索树中得到的结点序列，每个结
ถ

=

+
评价函数 起始结点到结点代价
(当前最小代价)
B
5
5
3
D
4
I
C
A
5
7
6
4
E
4
H
G
J
3
3
3
F
7
K
5
6
L
()
ถ
结点到目标结点代价
(后续估计最小代价)
状态
A
h(n)
13 10 6 12 7 8 5 3 6 3 0 6
B C D
E F G H I J K L
A*算法
搜索算法：A*算法
搜索算法：启发函数与评价函数
贪婪最佳优先搜索
所求解问题之外、与所求解
问题相关的特定信息或知识。

启发式搜索

搜索状态空间的算法。
例：一字棋游戏
选择“最好优先”算法 每种状态都标记了启发值 简化了搜索过程
启发式搜索和估价函数
在智能活动中使用最多的不是具有完备性的算法，而 是不一定完备的启发式方法。 对问题空间进行搜索时，提高搜索效率需要有和解有 关的大量控制性知识作为搜索的辅助性策略。 控制信息反映在估价函数中。 估价函数的任务就是估计待搜索结点的重要程度。
状态空间
爬山法的变形
随机爬山法 首选爬山法 随机重新开始爬山法
5.2.2 最好优先搜索法
❖ 定义：
Best-first Search (Ordered Search) 在AI图解搜索中，结点扩展的顺序是根据待扩展结点
的评价函数值 f(x)来决定，即将评价函数值最佳的结 点最先扩展，搜索方法是靠 f 值指导搜索顺序的。
启发式搜索
❖ “启发” (heuristic) 是关于发现和发明规则及方法的 研究。在状态空间搜索中,启发式被定义成一系列规 则,它从状态空间中选择最有希望到达问题解的路径。
❖ 有信息的搜索策略——是一种在问题本身的定义之外 还利用问题的特定知识的策略。
启发性信息
❖ 启发性信息的种类 有效地帮助确定扩展节点的信息； 有效的帮助决定哪些后继节点应被生成的信息； 能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。
❖ 如果h(n)=0，g(n)=d(n) 时，就是广度优先搜索法。一般讲在 f(n) 中，g(n)的比重越大，越倾向于广度优先搜索；h(n)的比 重越大，越倾向于深度优先搜索。
❖ 有了f(n)，就可以对各个待扩展结点的价值进行估计，从 OPEN表中选择出最有希望的结点扩展。
5.2.2 最好优先搜索法
f (n) g(n) h(n)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

13
怎样构造一个可纳的 h ？
一个可纳的启发函数通常可看作是一个松弛 问题（通过去除一些约束限制得到）的最优 解的耗散 在机器人导航中:
• 曼哈顿距离对应于去除障碍物的限制 • 欧几里得距离对应于去除障碍物的限制及机器人 只能在格子内移动的约束
详情在本课稍后叙述
14
(AI中被最广泛应用的算法)
10
8-Puzzle Heuristics
5
4 7 2 3
8
1 6
1
4 7
2
5 8
3
6
STATE(N)
Goal state
h1(N) = 不在位数码牌的个数 = 6 是可纳的 h2(N) =每个数码牌与其目标位置的 (Manhattan) 距离和
h3(N) = sum of permutation inversions = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16 is not admissible
1 100 1 2 90 100 0 102 104
2 1 1+100 2+90 4+90 2+1
相反的，如果不因为状态的重复访问而丢弃 新节点，那么搜索算法将会找到最优解，并 停止
28
但是 ...
如果不丢弃那些重复访问状态的节点，搜索树 可能会达到指数级的访问状态数量
1 1
1 1+1 1 1 2+1 2+1 2+1 2+1 2 4 4 4 4 4 4 4 4 1+1
5
4 7 2 3
8
1 6
1
4 7
2
5 8
3
6
STATE(N)
Goal state
h1(N) = 不在位数码牌的个数 = 6 是可纳的 h2(N) =每个数码牌与其目标位置的 (Manhattan) 距离和 = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13 是 可纳的 h3(N) = sum of permutation inversions = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16 is not admissible
STATE(N)
Goal state
h1(N) =不在位的牌数 = 6
h2(N) = 每个数码牌与其目标位置的
(Manhattan) 距离和 = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13 h3(N) = sum of permutation inversions = n 5 + n8 + n4 + n2 + n1 + n7 + n3 + n6 =4 +6 +3 +1 +0 +2 +0 +0 = 16
2+4
5
f(N) = h(N) =
S 数码牌与其目标位置的距离
8-Puzzle
6
5
2 5 4 3 4 6
2
1
0
5
6
Best-First Efficiency
Local-minimum problem
最佳优先效率
f(N) = h(N) = 与目标的直线距离
7
什么是我们能证明的？
如果状态空间是无限的，通常搜索是不完 备的 如果状态空间是有限的，但不丢弃那些重 复访问的状态的话，通常搜索也是不完备 的
G 为目标节点 h(G) = 0
9
8-Puzzle Heuristics
5
4 7 2 3
8
1 6
1
4 7
2
5 8
3
6
STATE(N)
Goal state
h1(N) = 不在位数码牌的个数 = 6 是 ??? h2(N) = sum of the (Manhattan) distances of every tile to its goal position = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13 is admissible h3(N) = sum of permutation inversions = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16 is not admissible
15
结论 1
A*
完备
最优
[即使不丢弃重复访问的节点，以上结论也 是成立的]
16
时间限制问题
当一个问题无解时，如果该问题的状态空间是无限的或者 不限制重复访问的次数，那么A*将不停的永远运行下去。 其他的一些情况，也可能使A*花费大量的时间才会停止。 因此，实际应用中，对A*将会给定一个时间的限制。如果 在时间限制内没有找到解，则停止运行。这样的话，将没 有办法知道该问题是否无解，或者是否需要更多的时间就 能找到解 当AI系统“小”且一次只是解决一个搜索问题时，以上 的问题不会成为太大的问题，不必过虑. 但是当AI系统变得很大，需要同时解决许多个搜索问题， 其中一些是无解问题的时候，该如何定义相应的时间限制 呢？有兴趣的同学可以进一步阅读相关文献…… （如 Motion Planning ...）
f(N) = g(N)+h(N), 式中 h(N) = 与目标的Manhattan距离 (A*) 8+3 6+5 8 7+4 7 6+3 6 5+6 5 4+7 4 3+8 3 2+9 2 3+10 3 4 7+2 7 6+1 6 7+0 7 6+1 6 8+1 8 7+2 7 6+3 6 5+4 5 4+5 4 3+6 3 2+7 2 3+8 3 4 5 5+6 5 4+7 4 3+8 3 3 2+9 2 1+10 1 0+11 0 1 2 5 6 5 4 5 6
2 1
此处的启发函数h无 疑是可纳的
26
如何处理可重复访问状态?
c=1 h = 100 1 2 90 100 0
2 1 f = 1+100 4+90 2+1
?
104
如果因为该新节点的状态是重复访问的， 就将它丢弃的话，那么搜索算法下一个 就将扩展目标节点，因此返回一个非最 优解
27
如何处理可重复访问状态?
30
一个启发函数 h 是一致 (或单调)的，若 1) 对于每个节点N及其每一个子节点N’ : N h(N) c(N,N’) + h(N’) c(N,N’) 2) 对于每个目标节点G: h(N) N’ h(G) = 0 h(N’) 一致启发函数也是可纳的
(三角形不等式)
Consistent Heuristic
1
2
29
如果新路径耗散 之前的路径耗散，那么丢弃该 重复访问状态的节点对 A* 不会产生负面影响
[因此，实际上如果一个节点的重复访问状态是已经被其 祖先节点访问过的话，可以将其丢弃] [搜索树可能会变得庞大，达到访问状态的指数级]
A* 仍然是最优的，但状态仍可能会被多次访问 幸运的是，对于许多可纳函数，是所谓一致可纳 的，这使得算法在处理重复访问状态上变得非常 高效
一致启发函数
直觉: 一致启发函数将会随着搜索树的深入变得越 来越精确 31
Admissibility and Consistency
一致启发函数也是可纳的
可纳启发函数不一定是一致的，但许多的可 纳启发函数是一致的
一致性和可纳性
32
8-Puzzle
5 8 1 2 3
4
7
2
3
1
6
4
7
5
8 goal
6
STATE(N)
h1(N) = 不在位的数码牌个数 h2(N) = 与目标位置的Manhattan距离的和 都是一致的吗? (为什么呢？)
33
结论 #2
若启发函数h是一致的，则只要A*扩展 一个节点，那一定是找到了到达该节点 状态的最优路径
34
证明 (1/2)
1) 考虑节点N及其子节点N’ 由于h是一致的: h(N) c(N,N’)+h(N’) = g(N)+h(N) g(N)+c(N,N’)+h(N’) = 因此，其它任何一条路径都不可能使f更低
1) f(N) = g(N) + h(N), 其中:
• • g(N) = 从起始节点到节点N的路径耗散 h(N) = 可纳启发函数
A* 搜索
2) 对于所有的弧: c(N,N’) > 0
3) 采用 SEARCH#2 搜索算法（节点扩展时目标测
试）
最佳优先（Best-first）搜索于是被称为 A* search
N
N’
f(N)
f(N’)
35
一致启发函数下的状态重复访问
当一个节点被扩展时，保存其状态到CLOSED 表中 当一个新的节点N生成时: • 如果STATE(N)已在CLOSED中，则丢弃N • 如果在边缘里存在节点N’有STATE(N’) = STATE(N) ，则丢弃其中f最大的一个（ N 或 N’ ）