Informed search algorithms Chapter 4
Informed search algorithms Chapter 4
Material ·Chapter4 Section1-3 ● 。 Exclude memory-bounded heuristic search
Material • Chapter 4 Section 1 - 3 • • Exclude memory-bounded heuristic search •
Outline ·Best--first search Greedy best-first search ·A search ·Heuristics Local search algorithms ·Hil-climbing search Simulated annealing search ·Local beam search ·Genetic algorithms
Outline • Best-first search • Greedy best-first search • A* search • Heuristics • Local search algorithms • Hill-climbing search • Simulated annealing search • Local beam search • Genetic algorithms
Review:Tree search \input{\filefalgorithmsHtree-search-short- algorithm ● A search strategy is defined by picking the order of node expansion
Review: Tree search • \input{\file{algorithms}{tree-search-shortalgorithm}} • • A search strategy is defined by picking the order of node expansion •
Best-first search Idea:use an evaluation function f(n)for each node estimate of"desirability" >Expand most desirable unexpanded node → ·Implementation: Order the nodes in fringe in decreasing order of desirability ·Special cases: greedy best-first search A search
Best-first search • Idea: use an evaluation function f(n) for each node – estimate of "desirability" – →Expand most desirable unexpanded node → • Implementation: Order the nodes in fringe in decreasing order of desirability • Special cases: – greedy best-first search – A* search –