"Visited" vs "Seen" Positions in Breadth-First Search
I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid.
In the Python program below, uncommenting the indicated lines switches between versions.
As well as help with understanding the difference, I would like to know if there is a "canonical" version which is considered best practice. Clearly here the second version performs best, but it is a also different to most of the statements of the algorithm I have found, which add the current node to a "visited" list straight after dequeuing.
BFS Algorithm
These versions store the whole path at each stage in the queue.
Version 1
Enqueue a list containing the start position, as the initial path.
while the queue has elements in it:
dequeue the next path
name the last element frontier
add the frontier to a set of visited positions
check if the frontier is the goal position
if so, return the path
otherwise, check neighbouring cells:
if the cell is legal and is not in the set of visited positions,
enqueue a new path consisting of the current path + this new cell
if no successful path was found, return None
Version 2
Enqueue a list containing the start position, as the initial path.
while the queue has elements in it:
dequeue the next path
name the last element frontier
check if the frontier is the goal position
if so, return the path
otherwise, check neighbouring cells:
if the cell is legal and is not in the set of previously seen cells,
enqueue a new path consisting of the current path + this new cell
add the current cell to a set of previously seen cells.
if no successful path was found, return None
``` import collections
offsets = { "up": (-1, 0), "right": (0, 1), "down": (1, 0), "left": (0, -1) }
def is_legal_position(maze, pos): i, j = pos num_rows = len(maze) num_cols = len(maze[0]) return 0 <= i < num_rows and 0 <= j < num_cols
def bfs(grid, start, end): """ Bread-First Search in a 2d list. Stores whole paths in queue. """ queue = collections.deque([[start]]) seen_or_visited = set()
while queue:
print("####### While queue is not empty #########")
path = queue.popleft()
print("Path", path)
frontier = path[-1]
print("Frontier:", frontier)
seen_or_visited.add(frontier) # Uncomment for version (1)
if frontier == end:
return path
enqueued_this_round = []
for direction in ["up", "right", "down", "left"]:
print("### Direction: ", direction)
row_offset, col_offset = offsets[direction]
next_pos = (frontier[0] + row_offset, frontier[1] + col_offset)
if is_legal_position(grid, next_pos) and next_pos not in seen_or_visited:
print("Enqueueing", next_pos)
queue.append(path + [next_pos])
# seen_or_visited.add(next_pos) # Uncomment for version (2)
enqueued_this_round.append(next_pos)
print("seen_or_visited:", seen_or_visited, "\n")
print("Enqueued this round", enqueued_this_round, "\n")
maze = [[0] * 5 for row in range(5)] start_pos = (4, 4) end_pos = (0, 0) print(bfs(maze, start_pos, end_pos)) ``` 923