A* 알고리즘이란
- 넓이 우선 탐색에 깊이 우선 탐색을 조합하여 휴리스틱한 기법을 사용한 알고리즘입니다..
흠!! 처음에 이 말을 보는 순간 우리나라 말이 아닌줄 알았음..!!
하나하나 쪼개서 살펴 보자..
넓이 우선 탐색(BFS) : 위의 이미지에서 시작 지점이 1이라고 정하자 그럼 탐색 순위가
넓이 우선 탐색은 시작지점과 갈려고 하는 지점이 같은것부터 탐색을 시작 한다
즉 출발 지점 1에서 한칸만 가서 갈수 있는 곳이 2,4,5 이다 여기서 가장 숫자가 적은 2 부터 검색을
하게 된다. 다 검색을 한 후에 이제 두칸을 이동 하여 갈수 잇는 3을 검색 하게 된다.
즉 1 , 2 , 4 , 5 , 3 이 순서대로 탐색을 하는 방법을 BFS라고 할수있다.
깊이 우선 탐색(DFS) : 역시 출발 지점이 1이라고 정하자 거기서 가장 가깝고 가작 적은 노드 부터 검색을 시작 한다.
그럼 한칸 이동한 2가 될것이도 2에서 검색 할수있는 노드 중에서는 3, 그다음 4, 이제 모든 검사를
다 한 상태여서 마지막에 5를 검색 할것이다.
자연스럽게 1,2,3,4,5 순서대로 탐색을 하게 된다. 이 방법을 DFS라고 할수 있다.