Launch the AISpace graph searching applet (if the direct link doesn't work, try visiting http://aispace.org/search/ and look for the applet link there). Once the applet is running, you can load sample problems from the "File" menu. Create a lab report with your name and the class info at the beginning, then number the following problems 1.1, 1.2, etc., including your answers and screenshots per the instructions below. Try the following:

  1. Simple Tree Graph
    1. [Depth First] Step through depth-first search. Predict what should happen, and note any places where your prediction is wrong. Take a screen shot of the solved state .
    2. [Breadth First] Reset the graph, then change the algorithm to "Breadth First" (you can change the algorithm in the "Search Options" menu). Predict what should happen, and note any places where your prediction is wrong. Take a screen shot of the solved state .
    3. [(Greedy) Best First] Reset the search, and then use the "View" menu to show the node heuristics. Set the algorithm to "Best First" (which is "Greedy Best First"). Step through the search, again predicting each expansion. Take a screen shot of the solved state.
    4. [Lowest (Uniform) Cost] Hide the node heuristics, and show the edge costs; then set the algorithm to "Lowest Cost First" (aka Uniform Cost or Dijkstra). Step through the search, predicting each expansion. Take a screen shot of the solved state.
    5. [A*] Finally, show both node heuristics and edge costs, and set algorithm to A*. Step through, predicting; and take a screen shot of the solved state.
  2. Misleading Heuristic graph
    1. [(Greedy) Best First] Load the "Misleading Heuristic Demo" and step through the (Greedy) "Best First" algorithm, predicting what the next expansion will be at each step. Step through 10 steps. Take a screen shot and explain what is happening.
    2. [A*] Reset and switch to A*. Predict what the outcome will be. Step through and explain why the misleading heuristic doesn't cause the same problem for A* as as it does for greedy best first. Include a screenshot of the solved state.
  3. "Vancouver Neighborhood" graph. Show both node heuristics and edge costs. For each of the following algorithms, predict (1) whether the goal will be found; (2) how many steps it will take; and (3) whether an optimal path will be found. Then actually test each, noting if there were any places that your predictions were wrong. Include screenshots of final sovled states.
    1. [Depth-first]
    2. [Breadth-first]
    3. [Uniform-cost]
    4. [Best-first]
    5. [A*]
Copyright © 1999-2010| Gene Rohrbaugh | Privacy Statement