$ mkdir ~/cs170/labs/lab23 $ cd ~/cs170/labs/lab23
I've forgotten for a few days, but today is the day we test your emacs prowess! Log onto inquire and take Emacs Quiz #3. No new Emacs commands, because...
Test 3 is next Friday! Wednesday is test review. Come with questions on Wednesday!
A priority queue can be used in many applications. Any time we want to store and process data in a non-time based fashion, we can do so with a priority queue. Cryptography is one application, because we can use frequency analysis to break certain ciphers. The de-facto application, however, is path planning.
Searching using a standard queue is guaranteed to find the end location, given a path exists, in \(O(n^2)\). However, for large mazes that might be extremely slow. Our goal should be to advance to the end location as quickly as possible. Instead of prioritizing expanding of cell locations by time added to the queue, we can prioritize expansion of cell based on their distance from the goal location!
Copy your maze.py file from last Wednesday's lab into today's lab directory:
$ cd ~cs170/labs/lab23 $ cp ../lab20/maze.py .
You are going to make two adjustments to this file. First, you are
going to read in a text file containing a maze.
Write a function read_file(file_name), which takes a
string which refers to a file you have permission to read from. It
should return a 2-dimensional python list of the elements of the
list.
You should read the name of the file using an input statement, and
call the above function to get the 2-d list of the maze.
The input file will be formatted as 50 lines of 50 characters each. A
0 represents an open location, and a 1 represents a wall. You can
assume that all of the mazes you read are 50 × 50, where the
start cell is always (0, 0) and the end cell is always (48, 48).
You will use this read in maze to test the A* algorithm.
A* works almost exactly the same as the search we did on Monday. However, instead of using a normal queue, it unses a priority queue. The priority for a cell is based on its euclidean distance to the end cell.
Edit your can_traverse method of the Maze
class, so that it uses a priority queue instead of the usual queue.
You might want to write a euclidean_distance function
in your file, to compute the appropriate priorities.
The file mazes.tgz contains several mazes you can test your program on. For these mazes, there is always a path to the end cell. You should make sure your program identifies that a path exists for every file.
Reading in a file is something computer scientists have to do all the time. Try to internalize the process very, very soon.
The open function takes two parameters: A file
name as a string, and a string representing the mode we are
operating under. The second parameter should be "r" for
read. The first should be the name of the file you are
working on.
There are many different ways to read a file in Python, but the easiest is probably using a for loop:
for line in opened_file: print(line)
The above code will iterate over ALL of the lines from the file. Remember that line is a string, so you'll need to convert that string of characters into a list of integers.
Your traversal technique will look similar to the traversal done using a queue. However, methods have changed so you need to update them.
Any time you go to add something to the priority queue, you need a priority to go with it. The priority of a cell to explore is its euclidean distance from the end cell. Again, computing distance in 2 dimensions is very important, so try to internalize this equation as well:
\[ distance = \sqrt{(x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2} \]The A* search starts by enqueuing the start cell with its associated priority. Then it should systematically process each cell in the priority queue. Remove the cell from the front of the priority queue, and add the neighbors of that cell to the queue. You can stop when you reach the end cell.
The current implementation for A* is not quite correct. It certainly finds out if there is a path very quickly, but it doesn't find the "fastest path." The priorities are slightly off, because the ACTUAL distance to the cell to be explored should determine what cells get explored next as well.
Modify your above program to account for this. Does it take longer to find the paths? How would you test that?
When you have finished, create a tar file of your lab23 directory. To create a tar file, execute the
following commands:
cd ~/cs170/labs tar czvf lab23.tgz lab23/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
23. Make sure you include a header
listing the authors of the file.