6.01
Staff/Schedule Grading Policies Collaboration Policy Archived Announcements
Progress
Course Notes Python and lib601 Circuit Part Specifications
Help Queue Piazza
Log In☰
Home / Week 13 Exercises / Trail Blazing

Trail Blazing

You are not logged in.

If you are a current student, please Log In for full access to this page.
Music for this Problem

You are trying to plan a path for a vehicle moving through an environment without obstacles. The environment has several cities, some of which are connected by straight roads. The vehicle starts at a city A and has to move to another city D. It can travel on-road or off-road. If it goes on a road of length d, then the cost is d. If it goes off-road for a distance d, then the cost is 2d.

Here is an example world, with lines indicating roads, and a matrix of Euclidean ("airline") distances between each pair of cities (this figure is drawn to scale):

 

  A B C D E F G H A 0.0 4.0 8.1 7.0 1.0 7.1 2.2 5.1 B 4.0 0.0 7.0 8.1 5.0 8.6 5.4 7.1 C 8.1 7.0 0.0 4.0 8.6 5.0 7.1 5.4 D 7.0 8.1 4.0 0.0 7.1 1.0 5.1 2.2 E 1.0 5.0 8.6 7.1 0.0 7.0 2.0 5.0 F 7.1 8.6 5.0 1.0 7.0 0.0 5.0 2.0 G 2.2 5.4 7.1 5.1 2.0 5.0 0.0 3.0 H 5.1 7.1 5.4 2.2 5.0 2.0 3.0 0.0

We assume that when moving between one city and another, the vehicle uses the road if it is available on its direct path. So, for example:

  • The cost from E to A is $1$
  • The cost from E to F is $10 = \hbox{dist}(EG) + 2\cdot\hbox{dist}(GH) + \hbox{dist}(HF)$
  • The cost from E to D is $14.2 = 2\cdot\hbox{dist}(ED)$
!!!! Note that the goal is city D !!!!

Cost

What is the cost of the path ABD?

Depth-First with DP

Some assumptions for this part:

  • The AD off-road path is not allowed; all other paths on and off road are allowed.
  • The successors (children) of a state are pushed onto the agenda in REVERSE ALPHABETICAL order.

What is the path found from A to D by Depth First search with DP? Enter a series of letters:

What is its cost?

What states are expanded by the search? Enter a series of letters:

Breadth First with DP

Some assumptions for this part:

  • The AD off-road path is not allowed; all other paths on and off road are allowed.
  • The successors (children) of a state are pushed onto the agenda in ALPHABETICAL order.

What is the path found from A to D by Breadth First search with DP? Enter a series of letters:

What is its cost?

What states are expanded by the search? Enter a series of letters:

Uniform Cost with DP

Some assumptions for this part:

  • All paths on and off road are allowed.
  • The successors (children) of a state are pushed into the agenda in ALPHABETICAL order.

What is the path found from A to D by Uniform Cost search with DP? Enter a series of letters:

What is its cost?

What states are expanded by the search? Enter a series of letters: