Practice Exercise 3.A
Thinking in Discrete States

Back to practice exercises.

1: Background Reading

2: Route Planning

  • Navigate to the following webpage: As you'll gather, this is a site for cyclists to find possible routes from point A to point B.

  • Enter a "From Address" and a "To Address." Experiment with various locations. Ignore the other options on the page for now.

3: Possible Representations

  • Think about how such a route-planner might represent the problem of finding routes from point A to point B. For now, don't worry about how it's actually finding the best route. Just think about how the problem itself could be represented. Think visually, and sketch some ideas that come to mind.

4: Thinking in Terms of States

  • Open the graph searching tool. Go to the File menu and select "Load Sample Problem" and select "Vancouver neighbourhood graph."

  • Take a look at the graph. You might be able to guess that DT=downtown, JB=Jericho Beach, and so on. Does this look anything like your sketch above? It's a crude representation of the city, but it's steering us in the right direction.

  • An obvious difference is that the AIspace graph has clearly defined nodes compared with the cycling map. If we were to place nodes in the cycling map, what would they represent in the real world?

  • The goal for now is simply to get you to think in terms of graphs with discrete states for representing problems such as the cycling route planner. Feel free to explore the graph search tool in more detail if you like.

Valid HTML 4.0 Transitional