설모의 기록

탐색 알고리즘에는 여러가지가 있습니다. 가장 기본적인 알고리즘이 BFS 와 DFS 인데요. 각각 아래에서 살펴보겠습니다. BFS(Breath First Search) BFS 는 너비우선탐색 알고리즘입니다. 위의 트리는 깊이(depth)가 2인 이진트리입니다. BFS는 루트부터 시작해서 깊이별로 가로방향을 먼저 탐색해나가는 방식입니다. 따라서 1단계에 있는 a를 먼저 탐색하고, 2단계에 있는 b,c 를 탐색하고, 마지막으로 3단계에 있는 d,e,f,g 를 탐색하는 방식입니다. 장점너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장합니다.최단경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단경로를 반드시 찾을 수 있습니다.노드의 수가 적고 깊이가 얕은 해가 존재..

최단 경로 탐색 알고리즘 최단 경로를 탐색하는 알고리즘의 종류는 여러가지가 존재합니다. 그 종류 중 하나인 a* 알고리즘에 대해 알아보겠습니다. a* 알고리즘은 bfs 알고리즘의 한 예로, 휴리스틱(h) 값을 이용해 최단 경로를 추정해나가는 방식입니다. 아래의 설명을 보시면 아시겠지만 휴리스틱 값이 0이라고 생각하면 결국 최단 경로가 되는데요. 휴리스틱 값이 0 이라면 bfs 와 똑같은 알고리즘이 됩니다. 따라서, 이 알고리즘은 결국 bfs 알고리즘이 최단 경로를 발견한다는 것을 다시 입증해주는 예시입니다. 개념과 예시는 아래에서 설명하도록 하겠습니다. A* 알고리즘? 한 지점에서 목표 지점으로 가는 방법 중 가장 짧은 길을 찾는 것을 최단 경로 탐색이라 하며, 지점을 노드라고 표현합니다. a* 알고리즘..