4 - informed search

Question 1

Informed search

Answer 1

give the algorithm “hints” about the desirability of different states - choose the most promising expansion

Question 2

Greedy best-first search

Answer 2

Expand the node that has the lowest value of the heuristic function h(n)
(isnt optimal, as it may get stuck in loops)

Question 3

A*search

Answer 3

f(n)= g(n)+ h(n)
f(n) = total estimated cost of path through node n
g(n) = cost so far to reach node n
h(n) = estimated cost from n to goal

avoid expanding paths that are already expensive

Question 4

Weighted A* search

Answer 4

take an admissable heuristic, inflate it by α, adn then perform the search as usual
- Fewer nodes tend to get expanded, but the resulting solution may be suboptimal ( its cost will be at most α times the cost of the optimal solution)

Question 5

Admissible heuristics

Answer 5

Admissible heuristics are used to estimate the cost of reaching the goal state in a search algorithm. Admissible heuristics never overestimate the cost of reaching the goal state. The use of admissible heuristics also results in optimal solutions as they always find the cheapest path solution.

Question 6

Designing heuristic functions

Answer 6

The standard way to construct a heuristic function is to find a solution to a simpler problem, which is one with fewer constraints. A problem with fewer constraints is often easier to solve

Question 7

Dominance

Answer 7

One heuristic, ha, is said to dominate another heuristic, hb, if the estimated goal distance for ha is greater than the estimated goal distance for hb for every node in the state space graph