Questions -

The following questions are related with the A* algorithm and, in particular, with heuristic functions and their properties.

Question 1 - Which of the following claims are true?

The DFS algorithm always expands at least as many nodes as A*.

A monotonic heuristic function h is always admissible.

An admissible heuristic function h is always monotonic.

Question 2 - Which of the following claims are true?

If h₁ and h₂ are admissible heuristic functions, then max(h₁, h₂) is admissible.

If two heuristic functions h₁ and h₂ dominate each other, then h₁ = h₂.

If h₁ and h₂ are admissible heuristic functions, then max(h₁, h₂) dominates both h₁ and h₂.

Question 3 - Let D(x, y) denote the straight-line distance between two locations on a planar map (in kilometers). Which of the following heuristic functions are admissible for the A* algorithm?

h₁(x, y) = 0

h₂(x, y) = 50

h₃(x, y) = D(x, y)

h₅(x, y) = D(x, y)/2

h₄ (x, y) = 2 x D(x, y)

Question 4 - Consider maps drawn in a plane: (i) grid-like maps where at least one coordinate of each node is an integer and arcs follow the grid lines and (ii) arbitrary graph-like maps where nodes can be placed freely in the plane and arcs are drawn directly from a node to another. Recall the Manhattan distance M(x₁, y₁, x₂, y₂) defined as |x₁ - x₂-|+|y₁ - y₂| for two points (x₁, y₁) and (x₂, y₂) in plane. Which of the following claims about M and the A* algorithm are true?

The function M is admissible for grid-like maps.

The function M is admissible for graph-like maps.

The function √2 x M is admissible for graph-like maps.

The function M/√2 is admissible for graph-like maps.