"Visited" vs "Seen" Positions in Breadth-First Search

Question

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))
```

Answer 1

I recommend you to take the same approach as I did to draw my conclusions: take a graphical approach to see the differences and drawbacks.

For that, do the following:

1. Comment out all print lines except print("Frontier:", frontier)
2. Then do python program.py > version1.txt, modify your program such that it represents verison 2, and then do python program.py > version2.txt.
3. Get pen & paper and draw a 4 × 4 table.

Here is a comparison of the first lines of both log files:

    Version 1           Version 2

Frontier: (4, 4)     Frontier: (4, 4)
Frontier: (3, 4)     Frontier: (3, 4)
Frontier: (4, 3)     Frontier: (3, 4)
Frontier: (2, 4)     Frontier: (4, 3)
Frontier: (3, 3)     Frontier: (2, 4)
Frontier: (3, 3)     Frontier: (4, 4)
Frontier: (4, 2)     Frontier: (3, 3)

I leave it as an exercise for you to draw this with pen & paper. Can you take it from here?

Note that the duplicate (3, 4) is version 2 is suspicious. Can you guess where it comes from?

I would like to know if there is a "canonical" version which is considered best practice.

You typically want the invariant that everything in the queue is already put in the seen queue. As a formula, this amounts to saying $$\text{work queue}\ \subseteq\ \text{seen queue}.$$

Otherwise, you could pick the tip of the work queue, say item $i_1$, go through its neighbors to then add its neighbor $i_2$ to the work queue. However, $i_2$ was already part of the work queue before (perhaps just after $i_1$!), but you couldn't know since you didn't keep the seen queue synchronized.

Hence, implementing this invariant amounts in your code to

• putting start onto the seen queue

  queue = collections.deque([[start]])
  seen_or_visited = set([start])
  

• choosing version 2, i.e.

  seen_or_visited.add(next_pos) # Uncomment for version (2)
  

You may also want to comment out version 1, i.e.

#seen_or_visited.add(frontier) # Uncomment for version (1)

since the invariant, fulfilled by the two points above, guarantees that whatever you pick from the queue (here, frontier) has already been added to the seen queue.

By the way, your function is missing a return None in case it doesn't find the target position.