Assignment 1: Searching

Assignment 1: Searching 
This assignment will give you practice with posing AI problems as search, and with un-informed and informed search algorithms. This is also an opportunity to dust off your coding skills
1. It’s September, which means you have only 6 months to make your Spring Break vacation plans to a dream destination! We’ve prepared a dataset of major highway segments of the United States (and parts of southern Canada and northern Mexico), including highway names, distances, and speed
1
limits; you can visualize this as a graph with nodes as towns and highway segments as edges. We’ve also prepared a dataset of cities and towns with corresponding latitude-longitude positions. These files should be in your GitHub repo from when you cloned in step 0. Your job is to implement algorithms that find good driving directions between pairs of cities given by the user. Your program should be run on the commandline like this:
python route.py [start-city] [end-city] [routing-option] [routing-algorithm] where: • start-city and end-city are the cities we need a route between. • routing-option is one of: – segments finds a route with the fewest number of “turns” (i.e. edges of the graph) – distance finds a route with the shortest total distance – time finds the fastest route, for a car that always travels at the speed limit – scenic finds the route having the least possible distance spent on highways (which we define as roads with speed limits 55 mph or greater) • routing-algorithm is one of: – bfs uses breadth-first search – dfs uses depth-first search – ids uses iterative deepening search – astar uses A* search, with a suitable heuristic function
The output of your program should be a nicely-formatted, human-readable list of directions, including travel times, distances, intermediate cities, and highway names, similar to what Google Maps or another site might produce. In addition, the last line of output should have the following machine-readable output about the route your code found:
[total-distance-in-miles] [total-time-in-hours] [start-city] [city-1] [city-2] ... [end-city] Please be careful to follow these interface requirements so that we can test your code properly. For instance, the last line of output might be:
51 1.0795 Bloomington,_Indiana Martinsville,_Indiana Jct_I-465_&_IN_37_S,_Indiana Indianapolis,_Indiana Like any real-world dataset, our road network has mistakes and inconsistencies; in the example above, for example, the third city visited is a highway intersection instead of the name of a town. Some of these “towns” will not have latitude-longitude coordinates in the cities dataset; you should design your code to still work well in the face of these problems. In the comment section at the top of your code file, please include a brief analysis of the results of your program, answering the questions: (1) Which search algorithm seems to work best for each routing options? (2) Which algorithm is fastest in terms of the amount of computation time required by your program, and by how much, according to your experiments? (To measure time accurately, you may want to temporarily include a loop in your program that runs the routing a few hundred or thousand times.) (3) Which algorithm requires the least memory, and by how much, according to your experiments? (4) Which heuristic function did you use, how good is it, and how might you make it better? (5) Supposing you start in Bloomington, which city should you travel to if you want to take the longest possible drive (in miles) that is still the shortest path to that city? (In other words, which city is furthest from Bloomington?)
2. Consider a variant of the 15-puzzle, but with the following important change: when the empty tile is on the edge of the board, the tile on the opposite side of the board can be slid into the opening. For example, the following are valid moves:
2
1 2 3 4 1 2 3 4 2 3 4 5 6 7 8 5 6 7 8 5 6 7 8 9 10 11 12 → 9 10 11 12 → 9 10 11 12 13 14 15 14 15 13 1 14 15 13
The goal of the puzzle is to find the shortest possible sequence of moves that restores the canonical configuration (on the left above) given an initial board configuration. Write a program called solver15.py that finds a solution to this problem efficiently using A* search. Your program should run on the command line: python solver15.py [input-board-filename] where input-board-filename is a text file containing a board configuration in a format like: 5 7 8 1 10 2 4 3 6 9 11 12 15 13 14 0 where 0 is the position of the empty tile. The program can output whatever you’d like, except that the last line of output should be a machinereadable representation of the solution path you found, in this format: [move-1] [move-2] ... [move-n] where each move is encoded as a letter L, R, U, or D for left, right, up, or down, respectively, indicating which direction a tile is slid in order to fill the missing tile. For instance, the two moves in the picture above would be represented as: L U Try to make your solver as fast as possible. Which heuristic functions did you try, and which works best?
3. Kam and Lars are planning their upcoming wedding. They’d like to make their banquet as awkward as possible by ensuring that at each dinner table, no one knows anyone else at the table. Write a program that computes an assignment of people to tables using as few tables as possible. Your program should run on the command line: python wedding.py [friends-file] [seats-per-table] where friends-file is a text file containing a friendship graph with one line per person, where each line first lists that person’s name and then the list of people that they know (and we assume that friendships are bidirectional, i.e. if A is friends with B then B is automatically friends with A), and seats-per-table is an integer saying the maximum number of people that can be seated at a table. The program can output whatever you’d like, except that the last line of output should be a machinereadable representation of the solution you found, in this format: [table-count] [table1-person1],[table1-person2],... [table2-person1],[table2-person2],... For example, python wedding.py myfriends.txt 3 with input file: davis steven sal joe jinnie zeming emma jayceon jayceon jinnie zeming jinne zeming emma steven jinnie steven sal joe might give the result: 4 davis emma,jayceon jinnie,joe,sal steven,zeming