블록 형태의 장애물이있는 nxn 격자가 있습니다. 임의의 지점에서 시작하여이 그리드의 어딘가에 플래그를 찾아야합니다. 왼쪽, 오른쪽으로 돌리거나 을 앞뒤로 움직일 수 있습니다.그리드를 탐색하고 플래그를 찾는 가장 빠른 방법
그리드의 각 지점에는 네 개의 블록 (위, 아래, 왼쪽, 오른쪽)에 대한 정보가 있습니다. BFS는 좋은 해결책 인 것 같습니다. 그러나 더 빠르고 더 좋은 탐색 알고리즘이 있는지 궁금하게 생각하니?
모든 아이디어는 크게 감사하겠습니다.
실제로 BFS가 필요한 알고리즘입니다. 추가적인 이점으로 플래그에 교차하는 세포 측면에서 최단 경로를 찾을 수 있습니다. 또한 전체 그래프를 "일반적인 방식으로"저장할 필요가 없음을 유의하십시오. 그리드는이 경우 그래프 자체를 충분히 표현할 수 있습니다. 많은 학생들이 그것을 이해하지 못합니다.
각 지점에서 4 개의 주변 블록에 대한 정보 (위, 아래, 왼쪽, 오른쪽)가 있다면 무엇을 제안 하시겠습니까? – iRiddler
이것은 그리드의 일반적인 탐색 문제로 보입니다. BFS를 사용하면 거리가있는 모든 점을 찾습니다. < = 시작점과 깃발 사이의 거리.
그러나 일부 최적화를 사용하는 것이 좋습니다.
국기의 좌표를 알고 있으면 (질문에서 명확하지 않은) A *를 사용할 수 있습니다.
플래그 좌표가 없으면 블록에서 가져온 정보를 악용 할 수 있습니다. 정사각형 격자에서 BFS는 원형 검색 정면을 만듭니다. 즉, 시작 부분의 원형 모양 영역 내에서 점에 대한 모든 정보를 얻습니다. 즉, 해당 지역의 모든 포인트를 평가하게됩니다. 그래프에 대한 정보를 더 많이주는 점의 우선 순위를 지정하여 탐험을 극대화 할 수 있습니다.이 점은 알 수없는 많은 이웃이있는 지점입니다.
이렇게하면 가능한 빨리 새 포인트를 평가하도록 검색이 리디렉션됩니다. 플래그를 찾으면 거리의 상한선을 가지며 경계를 향상시킬 수있는 알 수없는 부분을 탐색 할 수 있습니다. 우선 순위 기능에서 시작부터의 거리를 고려하여 검색이 너무 멀리되지 않도록 할 수 있습니다. 우선 순위 기능의 균형은 그리드와 장애물의 양에 따라 다릅니다.
"가장 빠른"이라고 말하면 가장 빠른 경로를 찾는 플래그 또는 알고리즘을 찾는 가장 빠른 방법을 찾는 것입니까? – angelatlarge
나는 깃발에 가장 빠른 방법을 의미했다. (가로 지르는 셀의 수) – iRiddler
매번 네 개의 주변 블록에 대한 정보가 있기 때문에 DFS를 사용한다고 말하고 싶습니다. – SidR