<PERSON> First Search Path Finding - Store Paths in Queue or Track Predecessors?
In studying various solutions for finding a path in a 2d maze using BFS, I've come across two different approaches. One is to store the whole path to a given position in the search queue. The other is to keep track of predecessors and build the path at the end by back-tracking.
I'm curious to hear which of these approaches is considered better in which situations. It looks to me like the time and memory requirements for the "store the path in the queue" method would grow much faster than the "predecessors" approach as the maze grows in size. Is that correct?
Below are two implementations in Python showing the different approaches.
```python """ BFS maze solver. 923
The queue contains paths. """
import collections
offsets = { "R": (0, 1), "L": (0, -1), "U": (-1, 0), "D": (1, 0) }
def bfs(grid, start): queue = collections.deque([[start]]) seen = set([start]) while queue: print("queue:", queue) path = queue.popleft() print("path", path) i, j = path[-1] if grid[i][j] == goal: return path for direction in ["U", "D", "R", "L"]: row_offset, col_offset = offsets[direction] i2, j2 = i + row_offset, j + col_offset if 0 <= i2 < num_rows and 0 <= j2 < num_cols and grid[i2][j2] != wall and (i2, j2) not in seen: queue.append(path + [(i2, j2)]) seen.add((i2, j2))
wall, clear, goal = "#", ".", "" num_rows, num_cols = 2, 4 grid = ["S...", "#.."] path = bfs(grid, (0, 0)) ```
```python """ BFS maze solver. The queue contains only positions. Predecessors are kept in dictionary. """
import collections
offsets = { "R": (0, 1), "L": (0, -1), "U": (-1, 0), "D": (1, 0) }
def bfs(grid, start): queue = collections.deque([start]) #!! seen = set([start]) while queue: print("queue:", queue) i, j = queue.popleft() print("i, j:", i, j) if grid[i][j] == goal: return (i, j) for direction in ["U", "D", "R", "L"]: row_offset, col_offset = offsets[direction] i2, j2 = i + row_offset, j + col_offset if 0 <= i2 < num_rows and 0 <= j2 < num_cols and grid[i2][j2] != wall and (i2, j2) not in seen: queue.append((i2, j2)) seen.add((i2, j2)) previous[(i2, j2)] = (i, j)
wall, clear, goal = "#", ".", "" num_rows, num_cols = 2, 4 grid = ["S...", "#.."] start_pos = (0, 0) previous = {} previous[start_pos] = (-1, -1) goal = bfs(grid, start_pos)
if goal: path = [] i, j = goal while i != -1: path.append((i, j)) i, j = previous[(i, j)] path.reverse() print("----Node history---") for item in previous.items(): print(item) print("----Path----") print(path) ``` 923