$ mkdir ~/cs170/labs/lab27 $ cd ~/cs170/labs/lab27
Earlier this week, we discussed Queues. Queues are FIFO data structures: the next item removed from the queue is the oldest item in the queue. Queues are incredibly useful data structures, but sometimes we don't necessarily want to access data based on the original order we added them to the Queue. Sometimes we want to retrieve the data out of the queue based on their . That's what a priority queue gives us.
A Priority Queue is generalized form of a Queue. A queue simply removes items from the queue based on time. In a priority queue, we can specify a priority value, so that items are removed in the correct order.
In a file called priority_queue.py, create a class
called PriorityQueue. This class must implement the
four main methods of a Priority Queue:
insert(self, data, priority) - This function
takes as a parameter some data, and an integer priority. It
should insert a tuple
representing the data and its priority into the queue.
dequeue_max(self) - This function simply removes
(and returns!) the data of the smallest priority
in the priority queue.
peek(self) - This function returns the data from
the maximum element of the priority queue, without removing it.
update_priority(self, data, new_priority) - This
function takes some data type, and an
integer new_priority. It should remove the old tuple
for data, and insert the new tuple.
You might also want a function for size of your queue
as well. You should implement the above functions using
a LinkedList, as opposed to an actual python list.
>>> pq = PriorityQueue()
>>> pq.insert(1, 1)
>>> pq.insert(0, 0)
>>> pq.insert(3, 3)
>>> pq.insert(2, 2)
>>> print(pq)
head -> (0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> None
>>> print(pq.dequeue_max())
0
>>> print(pq.dequeue_max())
1
>>> print(pq.dequeue_max())
2
>>> print(pq.dequeue_max())
3
>>> pq.insert("Hello", 5)
>>> pq.insert("World", 6)
>>> pq.insert("!", 2)
>>> print(pq)
head -> ("!", 2) -> ("Hello", 5) -> ("World", 6) -> None
>>> pq.update_priority("!", 7)
>>> print(pq)
head -> ("Hello", 5) -> ("World", 6) -> ("!", 7) -> None
You can create a tuple by separating the values using a comma:
>>> my_tuple = (2, 3)
>>> print(my_tuple)
(2, 3)
Your insert method is going to look a lot like the insert procedure for insertion sort. This time, however, you are inserting into a linked list.
update_priority could just resort the list.
However, we are just going to delete the current node, and
re-insert it into the correct place.
As of right now, insert is a O(n) operation, while dequeue is a O(1) operation. However, sometimes you are going to have a queue where you perform a lot of insertions, but only a few dequeues. Create a copy of the above class so that the insert operation is O(1), at the expense of a O(n) dequeue.
How would you describe the difference between how these classes operate? Do they now behave like two well known algorithms we've discussed in class?
Searching using a standard queue is guaranteed to find the end location, given a path exists, in O(n). 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 Monday's lab into today's lab directory:
$ cd ~cs170/labs/lab27 $ cp ../lab25/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 uses 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.
This exercise should be very straight forward, assuming you have written your priority queue correctly. You will still just be pulling the item from the front of the queue to expand. The only difference is that when you insert an item into the queue, you need the priority of that queue to be the euclidean distance to that node.
Determining if there exists a path is very straight forward.
However, solving a maze that we know there is a path is not terribly
interesting. What we really would like is the actual path that
would get us to the end location. Create a copy of the
can_traverse method that returns a list of tuples, the
cells that must be traversed in order to get to the end cell of the maze.
When you have finished, create a tar file of your lab27
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab27.tgz lab27/
To submit your activity, go to cseval.roanoke.edu. You should
see an available assignment called Lab Assignment 27.
Make sure you include a header listing the authors of the file.