中国科学技术大学：《人工智能基础》课程教学资源（课件讲稿）Lecture 04 Informed Search

Informed Search 吉建民 USTC jianminOustc.edu.cn 2022年3月14日 4口◆4⊙t1三1=，￥9QC

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Informed Search 吉建民 USTC jianmin@ustc.edu.cn 2022 年 3 月 14 日

Used Materials Disclaimer:本课件采用了S.Russell and P.Norvig's Artificial Intelligence-A modern approach slides,.徐林莉老师课件和其他网 络课程课件，也采用了GitHub中开源代码，以及部分网络博客 内容 口卡4三4色进分QC

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Used Materials Disclaimer: 本课件采用了 S. Russell and P. Norvig’s Artificial Intelligence –A modern approach slides, 徐林莉老师课件和其他网 络课程课件，也采用了 GitHub 中开源代码，以及部分网络博客 内容

Table of Contents 课程回顾 Best-first Search(最佳优先搜索 Greedy search A search Local Search Algorithms Hill-climbing search Simulated annealing search Local beam search Genetic algorithms 口◆4日1三1=，是90C

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents 课程回顾 Best-first Search (最佳优先搜索) Greedy search A* search Local Search Algorithms Hill-climbing search Simulated annealing search Local beam search Genetic algorithms

课程回顾 function TREE-SEARCH(problem,fringe)returns a solution,or failure fringe -INSERT(MAKE-NODE(INTIAL-STATE[problem]),fringe) loop do if fringe is empty then return failure node--REMOVE-FRONT (fringe) if GOAL-TEST[problem]applied to STATE(node)succeeds return node fringe INSERTALL(EXPAND(node,problem),fringe) A strategy is defined by picking the order of node expansion Variety of uninformed search strategies Iterative deepening search uses only linear space and not much more time than other uninformed algorithms 口卡回·三4色，是分Q0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 课程回顾 ▶ A strategy is defined by picking the order of node expansion ▶ Variety of uninformed search strategies ▶ Iterative deepening search uses only linear space and not much more time than other uninformed algorithms

Uninformed search strategies Uninformed search strategies use only the information available in the problem definition ·Breadth-first search(广度优先搜索) ,Uniform-cost search(代价一致搜索) ·Depth-first search(深度优先搜索) ~Depth-limited search(深度有限搜索) ,Iterative deepening search(迭代深入深度优先搜索) Bidirectional search(双向搜索) 口◆4日1三1，是90C

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Uninformed search strategies Uninformed search strategies use only the information available in the problem definition ▶ Breadth-first search (广度优先搜索) ▶ Uniform-cost search (代价一致搜索) ▶ Depth-first search (深度优先搜索) ▶ Depth-limited search (深度有限搜索) ▶ Iterative deepening search (迭代深入深度优先搜索) ▶ Bidirectional search (双向搜索)

Summary of algorithms Breadth- Uniform- Depth- Depth- Iterative Bidirectional Criterion First Cost First Limited Deepening (if applicable) Complete? Yes Yesa.b No No Yes“ Yesa,d Time O6) O(b1+LC/e) O(6m) 06 O(6) 0(64/2) Space O(6) O6+c/j】 O(bm) O(be) O(bd) O(b/2 Optimal? Yes Yes No No Yese Yese.d Figure 3.21 Evaluation of tree-search strategies.b is the branching factor,d is the depth of the shallowest solution;m is the maximum depth of the search tree;I is the depth limit. Superscript caveats are as follows:complete if b is finite;complete if step costs>efor positiveoptimal if step costs are all identical;if both directions use breadth-first search. b:Branching factor d:Solution Depth m:maximum Depth 口卡回t·三4色，是分Q0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary of algorithms ▶ b: Branching factor ▶ d: Solution Depth ▶ m: maximum Depth

Repeated states Failure to detect repeated states can turn a linear problem into an exponential one! 4口◆4⊙t4三1=，￥9QC

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Repeated states ▶ Failure to detect repeated states can turn a linear problem into an exponential one!

Graph search function GRAPH-SEARCH(problem,fringe)returns a solution, or failure closed an empty set fringe-INSERT(MAKE-NODE(INITIAL- STATE problem),fringe) loop do if fringe is empty then return failure node REMOVE-FRONT(fringe) if GOAL-TEST(problem,STATE[nodel)then return node if STATE[node is not in closed then add STATE[node to closed fringe -INSERTALL(EXPAND(node,problem),fringe) end 口卡回t·三4色，是分Q0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graph search

Informed search ,~Uninformed search无信息的搜索：除了问题中 提供的定义之外没有任何关于状态的附加信 息。 ~Informed search有信息的搜索：在问题本身的 定义之外还可利用问题的特定知识。 4口◆4⊙t1三1=，￥9QC

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Informed search ▶ Uninformed search 无信息的搜索：除了问题中 提供的定义之外没有任何关于状态的附加信 息。 ▶ Informed search 有信息的搜索：在问题本身的 定义之外还可利用问题的特定知识

Table of Contents 课程回顾 Best-first Search(最佳优先搜索) Greedy search A search Local Search Algorithms Hill-climbing search Simulated annealing search Local beam search Genetic algorithms 口卡回t·三4色，是分Q0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents 课程回顾 Best-first Search (最佳优先搜索) Greedy search A* search Local Search Algorithms Hill-climbing search Simulated annealing search Local beam search Genetic algorithms