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 h1 and h2 are admissible heuristic functions, then max(h1, h2) is admissible.
If two heuristic functions h1 and h2 dominate each other, then h1 = h2.
If h1 and h2 are admissible heuristic functions, then max(h1, h2) dominates both h1 and h2.
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?
h1(x, y) = 0
h2(x, y) = 50
h3(x, y) = D(x, y)
h5(x, y) = D(x, y)/2
h4 (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(x1, y1, x2, y2) defined as |x1 - x2-|+|y1 - y2| for two points (x1, y1) and (x2, y2) 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.