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