В отношении раздела 3.5 Рассела и Норвига: В сетке каждое состояние имеет четыре преемника, поэтому дерево поиска, включая повторяющиеся состояния, имеет 4^d листьев; но существует только около 2d^2 различных состояний в пределах d шагов любого данного состояния.Алгоритм поиска с предотвращением повторяющихся состояний
В чем смысл различных состояний здесь. Может кто-нибудь объяснить мне, рассматривая различные значения d, скажем 1,2,3,4.
В чем смысл различных состояний здесь.
Значение отдельного состояния - это уникальная ячейка, вы подсчитываете каждую ячейку в сетке только один раз.
Сырая верхняя граница числа различных состояний:
Во-первых, посмотрите на Подсеточное размера 2d+1 X 2d+1, и вы начинаете с узла в середине. Легко видеть, что нет ячеек вне этой подкритики, которые достижимы (из центра) в пределах d шагов. Кроме того, количество ячеек в этой подсети составляет (2d+1)*(2d+1) ~= 4d^2, поэтому мы нашли простую верхнюю границу, которая значительно лучше наивной 4^d.
Но есть много клеток, которые все еще недостижимы (например, вы не можете получить в d шагов к (0,0) от середины (что индекс (d,d)), так что мы можем получить более жесткие границы.
подход 1 : Комбинаторика:
Если мы говорим, что мы можем двигаться только «вверх и вправо», число достижимых клеток, мы можем пройти через это sum { CC(i,2) | i=0,1,...,d } здесь, CC стендов для stars and bars раствора, и определяются как:.
CC(n,k) = Choose(n+k-1,k-1) = (n+k-1)!/(n!*(k-1)!)
При назначении формулу, получим:
sum{ (i+1)!/(i)!1! | i=1,...,d} = sum { (i+1) | i=1,...,d}
Выше сумма арифметической прогрессии, что подводит к (d)(d+1)/2
Однако, отметим, что, позволяя только «вверх и вправо» ходов, мы позволили добраться до верхней правой четверти сетки, и мы хотим разрешить ее и для других кварталов. Из симметрии, за каждый квартал число достижимых клеток идентичен описанному выше, и в дополнение - добавить происхождения клетки (один мы начали с), так что в целом мы получаем:
#reachable_cells(d) = 4* (d)(d+1)/2 = 2d(d+1) + 1 ~= 2d^2
подход 2 Геометрическая:
Посмотрите на следующий примере матрице размера 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
этой матрица содержит все узлы на расстоянии не более 3 от центра.
Если вы внимательно посмотрите, вы увидите, что каждое расстояние фактически образует квадрат вокруг центра с краем длины d.(Так что для d=1, есть квадрат вокруг 0 с ребрами длины 1, для d=2, есть квадрат с краями длиной 2, и так далее)
В квадрате, периметр 4a - где a находится длина края.
Таким образом, количество уникальных ячеек, которые достижимы из центра с максимальным числом d, - это количество ячеек на любом таком прямоугольнике.
Количество ячеек на прямоугольник с длиной ребра i является 4i, и мы должны суммировать, что для каждого возможного прямоугольника, где i<d, и мы получаем:
#reachable_cells(d) = sum { 4i | i=1,....,d } = 4 sum{ i | i=1,...,d}
Это сумма арифметической прогрессии снова (и добавить происхождение снова), и мы получаем:
#reachable_cells(d) = 4 * d(d+1)/2 + 1 = 2d(d+1) + 1 ~= 2d^2
Примеры:
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
В приведенном выше, вы 7х7 матрице, она содержит все ячейки расстояния до 3 от центра, как вы можете видеть - количество достижимых состояний путем подсчета их и видеть, что это соответствует 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