AI Week 2

Question 1

Informed/Heuristic Search

Answer 1

A search algorithm that provides an estimate of how far away the current state is from the goal state. This allows us to choose a next state that brings us closest to our goal state.

Question 2

Heuristic Function

Answer 2

A function that uses domain-specific knowledge to estimate how far away a current state is from the goal state.
h: state -> R

Question 3

A* Algorithm

Answer 3

A search algorithm that chooses the next state with the smallest cumulative cost and smallest estimated future cost.

The next state has the cheapest cost f(n) = g(n) + h(n) where
n = a node/current state
g(n) = cumaltive cost from root to current state (backward cost)
h(n) = heuristic cost, estimation of cost from current state to goal state (forward cost)

Question 4

Admissible Heuristic Function

Answer 4

An admissible heuristic function is a function that will never overestimate the true cost of getting from the current state to the goal state. Most admissible heuristics are derived from relaxed problems.

A* is only admissable when we have an admissable heuristic function.

If we have a collection of heuristics, h1, h2, …, hm, then our net heuristic function is h(n) = max{h1(n), h2(n), …, hm(n)}

Question 5

A* Algorithm Properties

Answer 5

A* is:
complete
optimal when we have an admissable heuristic

c* = cheapest possible cost to get from root to goal state, ie cost of optimal solution
E = cheapest possible cost to get from one state to the next state
b = branching factor
O(b^[1+c*/E]) is space and time complexity

Question 6

Hill Climbing

Answer 6

An algorithm to find a min or max

Question 7

Local Search VS Search Problem

Answer 7

Local search and search problems are both deterministic,