General Search
In this problem, you will write the generic search procedure that you used in this week's labs, which implements either depth-first search (DFS) or breadth-first search (BFS) depending on an optional argument.
You can assume that you have available the SearchNode class as described in the readings (the path method is implemented slightly differently).
class SearchNode:
def __init__(self, state, parent, cost = 0.):
self.state = state
self.parent = parent
def path(self):
p = []
node = self
while node:
p.append(node.state)
node = node.parent
p.reverse()
return p
A SearchNode instance has:
- an attribute parent, containing a pointer to this node's parent node. The parent attribute of the root of the tree should be None.
- a method path, which takes no arguments and returns a list of states representing the path from the starting state to this state
Now we will define a general search procedure, which is applicable to any search problem we encounter. Your search procedure should take the following arguments:
- a procedure which takes one argument (a state) and return a list of the successor (neighboring) states.
- a procedure which takes one argument (a state) and returns True if that state is a goal, and False otherwise.
- a boolean argument dfs, which should default to False. If dfs is True, the search should run using the DFS algorithm; otherwise, it should run BFS.
If the search finds a solution, search should return a list of states representing the path from the start state to the goal (inclusive). If the search fails, it should return None.
Your code will be tested by searching for paths a knight can take on an 8x8 chess board. The tests will use the knight_successor function reproduced here:
def knight_successor(state):
moves = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
board_x, board_y = (8,8)
out = []
x,y = state
for dx,dy in moves:
nx,ny = x+dx,y+dy
if (-1<nx<board_x) and (-1<ny<board_y):
out.append((nx,ny))
return out
However, you should make sure your code will work for any arbitrary successor procedure not just for knight_successor.
Your search procedure should prune the search tree using the dynamic programming principle.
You should debug your code in IDLE.
Enter your code for search below:
