• Learn more about using Lisp for AI Search

Finding our Way Around in Romania

We have seen the map of Romania from our AI text in which the author is trying to find a way go from Arad to Bucharest:

And we know that we can find a route from one city to another via search like we did in the square puzzle assignment. However, the recursive structure of the depth-first search that we used to solve the square puzzle problem is not the only way to write a depth-first serarch function. Using recursion forces the visited nodes to be automatically stored via the function call mechanism. When we want access to these, so we can make sure we never visit the same node twice, then the advantage of the recursive structure is largely lost. Thus, it is typical to see iterative search functions that require substancially more memory. In this assignment, iteration rather than recursion, is used to use depth-first-search to find a path from the initial state to the goal state.

1. Download the Lisp code in DFS.txt and run it using the command (TEST) to find a route from Arad to Bucharest. In your text document, give the path found and explain why this algorithm has not found a "shortest" path (that visits the minimum number of cities in between).

2. Run this code to and from different cites in Romania, documenting the problems you select and the results of the serach in your text document.

3. Given that a recursive algorithm never takes the same path in the search tree twice, explain why it is important in this application to know which nodes have already been visited.

4. Make the appropriate changes to the ordering given in the lists of the neighboring cities so that the route from Arad to Bucharest WILL be completed by visiting the fewest number of cities. Paste your new code into your text document.

5. Explain why reordering alone cannot generally work with depth-first-search to find routes (from/to cities other than Arad and Bucharest) that visit the minimum number of cities in this map.

6. Explain why a breadth-first-search algorithm COULD ALWAYS be used in a general way to find routes (from/to cities other than Arad and Bucharest) that visit the minimum number of cities in this map each time.

7. Make the modificatons necessary to convert the Lisp code to using a breadth-first-search approach. Hint: You might consider changing the way the list L is merged with the list OPEN. When you have made the change and are convinced the code is now doing a breadth-first search, copy the altered code into your text document, making sure to also use comments to document.

8. Finally, run your new code several times with different cities, placing the problems and the soultions in your text document, being sure that you test all classes of "boundary value" cases. Explain what is meant by a "boundary value" in this application, and show that you test all classes of them.