MIT Map

In this exercise, we consider searching on a map with which you should be intimately familiar:

The locations are represented as (x,y) positions (in feet) relative to building 10. The edges are labeled with costs that are Euclidean distances in feet (estimated from Google Earth). Dashed lines represent paths that require walking outside.

Here is a list of proposed heuristics:

1. 0
2. Euclidean distance to the goal, in feet
3. 50 feet + the Euclidian distance to the goal
4. The minimum of 200 feet and the Euclidian distance to the goal

For each part, enter your answer as a sequence of letters with no punctuation (e.g. ABCD), or enter None if none of them are admissible.

Part 1

Which of the heuristics listed above are admissible in this particular map?

Part 2

Which of the heuristics listed above are admissible in all maps (that are also measured in feet)?

Part 3

On rainy days, you prefer to walk indoors. We can model this as effectively doubling the cost of outdoor paths (e.g., the cost of the path between node 7 and node 34 becomes 1500).

Under this updated cost model, which of the heuristics listed above are admissible?

Part 4

On sunny days, you prefer to walk outdoors. We can model this as effectively halving the cost of outdoor paths (e.g., the cost of the path between node 7 and node 34 becomes 375).

Under this updated cost model, which of the heuristics listed above are admissible?