Informed Search Flashcards
What is a heuristic?
A rule or principle used to guide a search algorithm
What does a heuristic search provide?
A workable solution in a reasonable time.
Where do heuristics usually come from?
Human experience
What are the basic requirements for heuristic evaluation
- Computation must not take long
- Accurate
- Close to perfect
- Optimistic (think it is closer to a solution than it actually is)
How does a hill climbing algorithm consider the states?
As if they are all laid on the surface of a landscape
How does a hill climbing algorithm work?
Starts with current state = initial state
Until current state = goal state or no change to current state:
- Get successors of current state and apply eval. func. to all
- If one of the successors has a better score, set current state to that successor.
Does a hill climb algorithm retain the paths?
No - Little memory used
What is a hill climbing algorithm useful for?
Useful for more practical problems where the state description holds all the information needed for a solution.
Can a hill climbing algorithm find reasonable solutions in a large or infinite state space?
Yes.
What are some issues with hill climbing algorithms?
- It may find a local minimum over a global one.
- There may be a plateau
- There may be ridges
What is a plateau?
An area of state space where evaluation function is essentially flat
Means algorithms will go on a random walk
What is a ridge?
They have steeply sloping sides
Cause problems where states along ridge are not directly connected
What is the general formula for a best - first search?
f(n) = g(n) + h(n)
where g(n) is the cost function
and h(n) is the heuristic function
What does a best first algorithm use to search the tree?
It uses the frontier, meaning it tries all paths
What data structure does a best first search use?
A priority queue to order states on basis of how promising they are
