Search algorithm with avoiding repeated states -

with reference section 3.5 of russel , norvig : on grid, each state has 4 successors, search tree including repeated states has 4^d leaves; there 2d^2 distinct states within d steps of given state.

what meaning of distinct states here. can explain me considering various values of d, 1,2,3,4.

what meaning of distinct states here.

the meaning of distinct state unique cell, count each cell in grid once.

crude upper bound number of distinct states:

first, @ subgrid of size 2d+1 x 2d+1, , start node @ middle. easy see there no cells outside of subgrid reachable (from center) within d steps. in addition, number of cells in subgrid (2d+1)*(2d+1) ~= 4d^2, found simple upper bound better naive 4^d.

but there many cells still unreachable (for example, cannot within d steps (0,0) middle (which index (d,d)), can tighter bound.

approach 1: combinatorics:

if can move "up , right", number of reachable cells can traverse through sum { cc(i,2) | i=0,1,...,d }. in here, cc stands stars , bars solution, , defined as:

cc(n,k) = choose(n+k-1,k-1) = (n+k-1)!/(n!*(k-1)!) 

when assigning formula, get:

sum{ (i+1)!/(i)!1! | i=1,...,d} = sum { (i+1) | i=1,...,d} 

the above sum of arithmetic progression sums (d)(d+1)/2

however, note allowing "up , right" moves, allowed reaching upper-right quarter of grid, , want allow other quarters well. symmetry, each quarter number of attainable cells identical above, , in addition - add origin cell (one started from) @ total get:

#reachable_cells(d) = 4* (d)(d+1)/2 = 2d(d+1) + 1 ~= 2d^2 

approach 2 geometrical:

have on following example matrix of size 7 x 7:

6 5 4 3 4 5 6 5 4 3 2 3 4 5 4 3 2 1 2 3 4 3 2 1 0 1 2 3 4 3 2 1 2 3 4 5 4 3 2 3 4 5 6 5 4 3 4 5 6 

this matrix contains nodes of distance @ 3 center.
if carefully, can see each distance forming square around center, edge of length d. (so d=1, there square around 0 edges of length 1, d=2, there square edged of length 2, , on)

in square, perimeter 4a - a length of edge.
so, number of unique cells reachable center @ d steps, number of cells on such rectangle.

number of cells on rectangle edge length of i 4i, , need sum each possible rectangle i<d, , get:

#reachable_cells(d) = sum { 4i | i=1,....,d } = 4 sum{ | i=1,...,d} 

this sum of arithmetic progression again (and add origin again), , get:

#reachable_cells(d) = 4 * d(d+1)/2 + 1 = 2d(d+1) + 1 ~= 2d^2 

examples:

6 5 4 3 4 5 6 5 4 3 2 3 4 5 4 3 2 1 2 3 4 3 2 1 0 1 2 3 2 3 2 1 2 3 4 5 4 3 2 3 4 5 6 5 4 3 4 5 6 

in above, have 7x7 matrix, contains cells of of distance 3 center, can see - number of reachable states counting them , see fits forumla:

#reachable_cells(0) = 2*0*1 + 1 = 1 #reachable_cells(1) = 2*1*2 + 1 = 5 #reachable_cells(2) = 2*2*3 + 1 = 13 #reachable_cells(3) = 2*3*4 + 1 = 25