그리드에서 BFS 큐의 크기

Question

크기 N * N의 정사각형 그리드에서 BFS를 실행하고 싶습니다. 단일 시작 노드가 있습니다. 나는 위/아래/왼쪽/오른쪽 (대각선 아님)으로 만 이동할 수 있습니다. 그리드에 장애물이있을 수 있습니다.

물론 방문해야하는 노드를 저장하기 위해 대기열을 사용하고 싶습니다. 그것은 크기 S (고정 크기)의 원형 배열로 구현됩니다. 배열의 최소 크기는 얼마입니까? 나는 최악의 경우에도 그것이 넘치기를 원하지 않는다.

유사한 문제는 다음과 같습니다. 그리드의 노드가 주어진 경우 시작 노드에서 정확히 거리 K에있는 노드의 최대 수는 얼마입니까 (0 < K < 2 * N)?

나는이 문제에 대한 정확한 답을 찾기가 어려워서 좋은 근사치로 충분할 것이라고 생각한다.

이 그리드 아니라 흰색 장애물을 나타내고 검은 프랙탈은 걷기 노드 어디에 우리가 (같은 패턴으로 격자를 만들 수 :

은 (맨 오른쪽 사진)이 예를 참조하십시오). 정확도 노드에서 동일한 노드까지의 거리 (실제로이 수는 경로가 두 개로 나뉠 때마다 두 배가됩니다)에 많은 노드가 있음을 알 수 있습니다. 그래서이 숫자가 얼마나 큰 지 알고 싶습니다. 같은 상황에서 다른 구성이 나오면 알려주세요.

제 질문은 다음과 같습니다.이 숫자는 2 * N보다 큰 값을 얻을 수 있습니까? N은 N * N 정사각형 그리드의 크기입니다.

Answer 1

대기열의 최대 크기를 알고 싶기 때문에 거리 K에있는 셀의 수를 알고 싶습니까?

그렇다면 단순히 목록을 기반으로하는 순환 버퍼를 사용하는 것이 좋습니다 (또는 버퍼를 가득 채워서 배열을 사용하고 더 큰 버퍼를 다시 할당하는 것).

문제를 건너 뛰고 목록 크기 조정 동작이 문제가되지 않아야합니다. 대부분의 구현은 공간이 부족한 경우 기본 배열의 크기를 두 배로 늘리기 때문에 O 이상 (log n) 어쨌든 재 할당.

. . . * . . . 
. * . * . * . 
. * . * . * . 
. * . * . * . 
. * . . . * . 
. . * * * . . 
. . A * B . . 

내가 A에서 B로, 정확하게 거리를 계산하는 경우 : 내가 제대로 문제를 이해한다면

Answer 2

은 시작 노드에서 노드의 최대 거리 때문에 장애물의 존재>2*N이 될 수 있습니다 30 * 2 * 7 이상입니다.

장애물이 아닌 경우 테두리의 최대 크기 인 K (또는 그 일부가 눈금과 겹치는 부분)의 간단한 다이아몬드가 될 수 있으므로 결과적으로 최대 크기 2*N.

장애물은 두 노드 사이의 최단 경로 길이를 늘릴 수 있습니다. 최대 프린지 크기를 늘릴 수 있습니까? 나는 그들이 할 수있는 예를 빨리 생각해 낼 수 없다. 나는 할 수 없다고 생각한다. 그러나 빠른 증거도 생각할 수 없다.

Answer 3

네,이 숫자는 더 커질 수 있으며 제공된 세 번째 이미지 을 사용하여 시각화하는 것이 매우 쉬워야한다고 생각합니다.

그림의 왼쪽 상단 부분 만 시작한다고 가정 해보십시오. 이는 N을 위 왼쪽 분기의 크기로 정의하고 E를 모두 중앙 셀까지 동일한 거리를 가진 끝점 수로 정의합니다.

이제 전체 그림으로 눈금을 확장한다고 가정 해보십시오. 즉 Nnew가 2N이됩니다 (즉, 길이가 두 배로 넓어짐). 그러나, 도면에서 관찰 할 수있는 바와 같이 종단점 (E)의 수는 이제 4 배로 증가한다 (즉, Enew = 4N). 엔드 포인트의 수는 N보다 훨씬 빠르게 성장 N이 증가함에 따라 즉

, 따라서 은 엔드 포인트의 수는