Solving Problems by Searching

Question 1

What is a heuristic?

Answer 1

A function that estimates how close a state is to a goal; designed for a particular search problem

Question 2

What is a Greedy Search?

Answer 2

Expand the code that seems closest
Heuristic: estimate of distance to nearest goal for each state

Question 3

What is A* Search?

Answer 3

Combination of uniform cost search (backward cost) and greedy search (forward cost) [Estimates the forward cost]
- Best-first search
- Relies on an open and closed list to find a path that is both optimal and complete

Question 4

What is an admissible heuristic?

Answer 4

Used to estimate the cost of reaching the goal state in an informed search algorithm.

Question 5

Difference between UCS and A*

Answer 5

UCS expands equally in all directions

A* expands mainly towards the goal, but does hedge its bets to ensure optimality

Question 6

What is Manhattan distance?

Answer 6

Distance between two points measured along axes at right angles
| |
| |_____ X
|
|_______________>

Question 7

Heuristics form a semi-lattice which is _______.

Answer 7

max of admissible heuristics is admissible.

Question 8

What is the idea of a graph search?

Answer 8

Never expand a state twice

*Think of it as a binary tree

Question 9

T or F: Estimated heuristic costs <= actual costs

Answer 9

True.

Question 10

When is A* optimal on a tree search?

Answer 10

When its heuristic is admissible.

Question 11

When is A* optimal on a graph search

Answer 11

When its heuristic is consistent.

• Consistency implies admissibility