Heuristic (Informed) Search Flashcards
(28 cards)
What is Combinatorial Explosion
As we go deeper in the search tree the number of nodes increases exponentially
What is different from Heuristic Search Algorithms and Blind Search Algorithms
Heuristic Search Algorithms exploit knowledge about the problem to guide search
How do Heuristic algorithms work?
They have some information about the domain so that they can distinguish the candidate states to expands into “promising” and “non-promising”
What is a Heuristic?
A strategy based on the nature of the problem.
How is a Heuristic expressed?
It is expressed as a function that return an estimate of how far a state is from the final state
What is the drawback of heuristics?
They can be fallible
- Estimates can be underestimates, overestimates or simply wrong!
What is the Heuristic Function: Euclidean Distance?
d(S, F) = sqrt((Xs - Xf)^2 + (Ys - Yf)^2)
What is the Heuristic Function: Manhattan Distance?
Md(S, F) = |Xs - Xf| + |Ys - Yf|
What parts is a Heuristic algorithm consisted of?
- The heuristic function
- Some algorithm that exploits information produced by the function
How does Best First Search (BestFS) work?
Generate the search space by expanding the “best” state
What are the advantages of BestFS?
- The algogrithm tries to find a solution fast
- It is complete
What are the disadvantages of BestFS?
- The open list grows fast
- It is not admissible
- Its efficiency largely depends on the heuristic
What is the “A” Algorithm
An improvement of BestFS that keeps track of the cost of computation
What is the heuristic of A* Algorithm?
HV(S) = g(S) + h(S)
where:
- h(S) is the value of the state S given by the heuristic function
- g(S) is the distance of the state S from the initial state
What is Motivation?
It is the preference of the shortest path when two states have the same heuristic value
When is the A* admissible?
When the h(S) in the heuristic function HV(S)=g(S)+h(S) is an underestimate of the actual cost of reaching the final state
What are the advantages of A*?
- It is admissible
- It is complete
What are the disadvantages of A*?
- Its efficiency largely depends on the heuristic
What is Admissibility in Heuristic Algorithms?
The property of returning the shortest solutions
What is Monotonicity in Heuristic Algorithms?
It is a collection of the following properties:
∀si,sj : j>i, h(si)-h(sj) ≤ cost(si,sj).
- h(goal)=0
- It is admissible
What is Informedness in Heuristic Algorithms?
Given two A* heuristics h1 and h2, h1 is said to be more informed if
∀S∈D: h2(S) ≤ h1(S)
If a heuristic is more informed then it examines less states to find a solution
What is the Hill-Climbing Search (HC)?
It is an Heuristic search algorithm that doesn’t keep track of the choices made along the problem solving process nor has an open list or closed set. It just expands to the best child
What are the advantages of HC?
- It is space efficient
- It is time efficient
What are the disadvantages of HC?
- It is incomplete → Random Restart Hill Climbing
- Foothills: The solution found is not necessarily the best (local maxima)
- Plateau: Every child has the same heuristic value
- Ridges: Although the best child is picked and initial progress is done fast, no overall progress is made after that
