컴공돌이의 취미 블로그

균일 비용 탐색(Uniform Cost Search : UCS) 균일 비용 탐색 이란? * 사전적 정의 : 균일 비용 탐색은 그래프에서 노드 간의 최단 경로를 찾아주는 Dijkstra Algorithm(다익스트라 알고리즘)을 이용해서 탐색하는 방식을 의미한다. * 간단한 정의 : 현재 우선순위 큐에 들어있는 노드들의 인접한 노드들을 탐색하는데 소요되는 총 비용을 비교하여 가장 작은 비용이 드는 노드를 탐색하는 방식으로 시작 state와 골 state가 정해진 다익스트라 알고리즘이라고 생각하면 된다. 균일 비용 탐색 의 데이터 저장 구조 균일 비용 탐색은 자식노드로 가는데 드는 총 비용들을 검사해서 비교한 후 가장 작은 비용이 드는 노드를 저장소에 추가하면서 데이터를 확장한다. 이때 자식노드로 움직이는데 ..

너비 우선 탐색 (Breadth First Search : BFS) 너비 우선 탐색 이란? * 사전적 정의 : 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. * 간단한 정의 : 원하는 해를 찾기 위해서 자식노드들을 전부 검사해 나가면서 전진하는 방식 너비 우선 탐색은 말 그대로 너비를 우선적으로 하여 탐색하는 방법을 말한다. 비슷한 탐색 방법으로는 깊이 우선 탐색(Depth First Search : DFS) 가 있는데 이것 역시 말 그래로 깊이를 우선적으로 하여 탐색을 하는 방법을 말한다. 데이터가 같은 트리 구조로 ..

깊이 우선 탐색 (Depth First Search : DFS) 깊이 우선 탐색 이란? * 사전적 정의 : 깊이 우선 탐색은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한개의 자식 노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해가는 방식이다. * 간단한 정의 : 원하는 해를 찾기 위해서 전진할 수 있을 때 까지 전진하고, 만약 전진하다가 나아갈 길이 보이지 않는다면 바로 전에 선택한 갈림길에서 다른길을 선택하여 또 전진하는 방식이다. 깊이 우선 탐색은 말 그대로 깊이를 우선적으로 하여 탐색하는 방법을 말한다. 비슷한 탐색 방법으로는 너비 우선 탐색(Breadth Fi..