Task 1 below asks you to implement A* for Pacman. So, you want to have
an openset that’s ordered by a heuristic value. Python has “heaps”
for this purpose. Whenever you “pop” a value from a heap, the lowest
value comes out. Use a tuple to keep the value and other data
together.
from heapq import heappush, heappop
openset = []
heappush(openset, (5, "foo"))
heappush(openset, (7, "bar"))
heappush(openset, (3, "baz"))
heappush(openset, (9, "quux"))
best = heappop(openset)
print bestThis task uses the same Pacman code as Homework 2. Grab the code again, and unzip to a new directory. It’s best not to mix the code for different assignments.
Open the file py/search.py and find the function aStarSearch
(line 104, at the bottom) which reads:
def aStarSearch(problem, heuristic=nullHeuristic):
"Search the node that has the lowest combined cost and heuristic first."
"*** YOUR CODE HERE ***"
util.raiseNotDefined()Add this line of code above that function:
from heapq import heappush, heappop
def aStarSearch(problem, heuristic=nullHeuristic):Take the template and finish the code so that A* search works. (You
probably want to adapt what you wrote for Homework 2.) You can use the
argument heuristic as a function like so:
dist = heuristic(state, problem)You can test it with pacman by running this command:
python py/pacman.py -l mediumScaryMaze -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic
Create a worse search algorithm by modifying aStarSearch in a very
simple way. Describe to me what your modification was, and how it
affected performance (in terms of “search nodes expanded” and “total
cost of path”; look at the output from the pacman program).