an agent aims to find a path on a hexagonal map with initial state s0 in the center and goal state s⋆ at the bottom as depicted below. The map is parametrized by the distance n ≥ 1 from s0 to any of the border cells (n = 3 in the depicted example). The agent can move from its current cell to any of the 6 adjacent cells,
How can we find the number of node expansions performed by bfs without duplicate detection, and with duplicated detection as a function of n.
I know that the branching factor for the map would be 6 because the agent can move in 6 directions, and for a depth of k, we get O(b^k) = 6^n without duplicate detection, but what is the number of node expansion with duplicate detection with bfs.