안녕하세요. 에이스타와 bfs 관련 문의드립니다.

Question

안녕하세요. 에이스타 까지의 강의를 공부하고 궁금한게 있어서 문의드립니다.  에이스타와 bfs는 어쨋든 하나의 정점에서 상하좌우 or 상하좌우-우상-우하-좌상-좌하  로 탐색을 하면서 가장 좋은 길을 선택하는 거잖아요.  근데 제가 저의 포폴에서 확인을 해보니 동일한 타겟 지점으로 에이스타와 bfs 이동을 해보면, 에이스타의 효율이 훨씬 좋더라고요. 오픈리스트 추가되는 갯수가 적습니다.  왜 이런 현상이 발생하는지 알 수 잇을까요?

Rookiss · Answer

A*는 [시작지점]-[목표지점]을 각기 정해두고
휴리스틱이라는 느낌적인 느낌으로 좋을 것 같은 방향으로 먼저 서칭을 합니다.
BFS는 [시작지점]에서 가까운 순서대로 서칭을 하기 때문에,
설령 목표지점이 오른쪽에 있더라도 반대 방향을 먼저 서칭하는 경우가 생길 수 있습니다.
그래서 엄청 장애물이 많거나 하는 특수 상황이 아니면 A* 가 훨 좋은 것이죠.
BFS는 [목표지점]이라는 존재에 대해 아예 모른다는 것을 유의깊게 살펴보세요!

leomessi · Answer

BFS는 '순회' 알고리즘이므로, 기본적으로 그래프 내의 연결된 모든 정점을 방문하려고 시도하는 알고리즘입니다. 따라서 그래프의 간선들의 가중치가 모두 같은 상황이 아닐 땐 최단거리를 구할 수 없다는 단점도 있습니다. 반면 A*는 분명한 목적지를 정해두고 시작지점과 도착지점간의 최단거리에만 관심이 있는 알고리즘이기 때문에 BFS와 다르게 동작합니다.