Finders¶
In this particular project, we are required to implement three search algorithms:
- BFS
- DFS
- A*
BFS¶
BFS or breadth-first search traverses the graph by exploring all the neighbors of the root of the graph first, and then proceeds to the next depth of the graph until the end is found.
Implementing this is simple enough - let us keep a queue, add neighbors to it, and iterate on the queue until we find our target. Notice how our implementation accepts arbitrary data structures for the grid/graph by allowing input of a get_neighbor function.
def bfs(grid, get_adjacent, start, end):
queue, visited = [start], set()
while queue:
curr = queue.pop(0)
if curr in visited:
continue
visited.add(curr)
for neighbor in get_adjacent(grid, curr):
if neighbor == end:
# found!
else:
queue.append(neighbor)
Notice that in our breadth first search, we want to know the path traversed by our algorithm to get to the end. There's a couple of methods to achieve this, but to keep the data structures as simple and pure as possible, I opted to implement a backtrace.
def backtrack(grid, parents, start, end):
path = [end]
while path[-1] != start:
path.append(parents[path[-1]])
path.reverse()
return path
def bfs(grid, get_adjacent, start, end):
queue, visited, parents = [start], set(), {}
while queue:
curr = queue.pop(0)
if curr in visited:
continue
visited.add(curr)
for neighbor in get_adjacent(grid, curr):
if neighbor not in visited:
parents[neighbor] = curr
if neighbor == end:
path = backtrack(grid, parents, start, end)
if with_expansion: return path, expansion
else: return path,
else:
queue.append(neighbor)
We can also make our algorithm return the list of expanded nodes. This will help us later if we want to see what 'path' the algorithm took to generate the solution.
def bfs(grid, get_adjacent, start, end, with_expansion=False):
queue, visited, parents = [start], set(), {}
if with_expansion:
expansion = []
while queue:
curr = queue.pop(0)
if curr in visited:
continue
visited.add(curr)
if with_expansion:
expansion.append(curr)
for neighbor in get_adjacent(grid, curr):
if neighbor not in visited:
parents[neighbor] = curr
if neighbor == end:
path = backtrack(grid, parents, start, end)
if with_expansion: return path, expansion
else: return path,
else:
queue.append(neighbor)
DFS¶
DFS or depth-first search traverses the graph by exploring to the end of each branch first.
Implementing this takes even less lines of code - we simply keep a stack, and add neighbors of the node there:
def dfs(grid, get_adjacent, start, end, with_expansion=False):
stack, visited = [(start, [start])], []
while stack:
curr, path = stack.pop()
if curr == end:
if with_expansion: return path, visited
else: return path,
if curr not in visited:
visited.append(curr)
for neighbor in get_adjacent(grid, curr):
if neighbor not in visited:
stack.append((neighbor, path + [neighbor]))
Note that I took the liberty of implementing it with the path and expansion path taken into account.
A*¶
A is perhaps the most interesting search-algorithm here, being the only informed search algorithm. In A, we make use of a heuristic function that will guide the search.
It is a bit longer than the two previous algorithms, but not that much longer.
The first thing that is different is that we need two new arguments, cost and heuristic. cost will return the cost to traverse between two nodes, while heuristic will serve as the heuristic function for our algorithm. This makes our algorithm more general by supporting different problem spaces.
We also add the data structures that we need - in particular, a queue (a priority queue), a set for visited nodes, a map for parents (for backtracking) and a map for G and F.
def astar(grid, get_adjacent, start, end, cost, heuristic, with_expansion=False):
queue, visited, parents = set([start]), set(), {}
g_cost, f_cost = {}, {}
g_cost[start] = 0
f_cost[start] = heuristic(start, end)
We then take the item in the queue with the lowest cost for F
def astar_cut(): # not really a function, we just define it as such so jupyter won't run it
while queue:
curr = None
curr_score = None
# TODO: Turn this into a priority queue?
for coord in queue:
if curr == None or f_cost[coord] < curr_score:
curr_score = f_cost[coord]
curr = coord
After that, we check if it is the goal. If not, we remove it from the queue and iterate over its neighbors, updating the parent map, f_cost, and g_cost in the process:
def astar_cut():
for neighbor in get_adjacent(grid, curr):
if neighbor in visited:
continue
g = g_cost[curr] + manhattan_distance(curr, neighbor)
if neighbor not in queue:
queue.add(neighbor)
elif g >= g_cost[neighbor]:
continue
parents[neighbor] = curr
g_cost[neighbor] = g
f_cost[neighbor] = g + heuristic(neighbor, end)
This is the whole algorithm defined:
def astar(grid, get_adjacent, start, end, cost, heuristic, with_expansion=False):
queue, visited, parents = set([start]), set(), {}
g_cost, f_cost = {}, {}
g_cost[start] = 0
f_cost[start] = heuristic(start, end)
if with_expansion:
expansion = []
while queue:
curr = None
curr_score = None
# TODO: Turn this into a priority queue?
for coord in queue:
if curr == None or f_cost[coord] < curr_score:
curr_score = f_cost[coord]
curr = coord
if curr == end:
path = backtrack(grid, parents, start, end)
if with_expansion: return path, expansion
else: return path,
queue.remove(curr)
if curr in visited:
continue
visited.add(curr)
if with_expansion:
expansion.append(curr)
for neighbor in get_adjacent(grid, curr):
if neighbor in visited:
continue
g = g_cost[curr] + manhattan_distance(curr, neighbor)
if neighbor not in queue:
queue.add(neighbor)
elif g >= g_cost[neighbor]:
continue
parents[neighbor] = curr
g_cost[neighbor] = g
f_cost[neighbor] = g + heuristic(neighbor, end)
With our generic algorithms defined, we can move on to see how we can use it to search in our grid.
This is a post in the CS 180 Pathfinding series.
Other posts in this series:
- Mar 17, 2019 - CS 180 Pathfinding
- Mar 17, 2019 - Grid
- Mar 17, 2019 - Finders
- Mar 17, 2019 - Grid Search
- Mar 17, 2019 - Test Cases
- Mar 17, 2019 - Running Test Cases
- Mar 17, 2019 - Timing
- Mar 17, 2019 - Viz