PowerPoint Presentation
CSE 3521: HW1_Programming:
Search Algorithms
General
Please note that this is NOT a programming course. Thus, the TA and I are not to help step-by-step debug your code (e.g., syntax or semantic errors). We may provide suggestions for how to get familiar with Python and help point out which part of your code might go wrong, but it is your job to implement the search algorithms, and the implementation itself involves debugging. It is important that you first go through the lecture slides or suggested reading (on the website) to understand the concepts of the search algorithms and the graph search before implementation.
Introduction
In this homework, you are to implement four search algorithms — DFS, BFS, UCS, and A* — so that a Pac-Man planning agent can complete the search problem. You are to implement the “graph” search rather than the “tree” search version.
Please note the difference between the “search process (nodes that are expanded)” and the “solution (a path from the start state to the goal state)”
What to return is a solution (i.e., a sequence of actions)
There is an autograder that you can run
Introduction
All the search algorithms are the same except for fringe/exploration strategies. Thus, focus on implementing the first algorithm (say DFS) and the others will become easier.
A search problem
Start state
Goal states
Successor functions: with actions, costs, and next states
What you need to return:
A list of actions!
Problem.getStartState()
problem.isGoalState(state)
problem.getSuccessors(state)
Example: [“go north-east”, “go south-east”, “go-south”]
Introduction (in search.py)
You don’t need to implement any of these on the right-hand side or bottom side. Just read through them and understand the input and output of these functions.
Other notes
Please carefully read the pseudo-code of the “graph” search in the slides. It is very important where you:
(a) check the close-set
(b) inset states into the close-set
I have seen some earlier cases where you may do (a) when you add a node into the fringe but not when you expand that node. There is a big difference between them.
If you are not sure what the differences are, create some toy examples yourselves (on the paper), and go through them. This is what I always do to find out some cases that I may miss considering.
An example template (no need to follow this!)
/docProps/thumbnail.jpeg