Informed Search

Question 1

Describe the difference between informed and uninformed search.

Answer 1

Informed search strategies can find solutions more efficiently using domain-specific hints about the location of goals using a heuristic function h(n).

h(n) gives the estimated cost of the cheapest path from n.state to a goal state. It is problem-specific with only constraints being it is nonnegative and h(n) = 0 where n is a goal node.

Question 2

Discuss the influence of a heuristic on the search results

Question 3

Determine whether a heuristic dominates another one

Question 4

Methods to systematically obtain heuristics for search problems

Question 5

Create simple heuristics to improve performance of search problems

Question 6

Properties/Performance of Greedy Best First search
(Completeness, Time complexity, Space complexity, Optimality)

b: branching factor
m: maximum length of any path

Answer 6

Not complete unless graph search is used

Time and Space complexity O(b^m). A good heuristic can provide dramatic improvement.

Not optimal.

Question 7

Idea of A* search algorithm: avoid expanding paths that…

Evaluation function f(n) = h(n) + g(n)

f(n) :
h(n):
g(n):

h(n) has to be admissible. What does that mean?

Answer 7

are already expensive

estimated total cost of path through n to the goal
=estimated cost from n to goal + cost so far to reach n

An admissible heuristic is an underestimation, i.e. it has to be less than or equal to the actual cost.