주녘공부일지

A* 알고리즘이란?다익스트라 알고리즘에서 동적 계획법(DP)을 적용시켜 확장한 최단 경로 탐색 알고리즘- 탐색이 가능한 모든 노드 중 현재 최적이라고 판단되는 노드를 탐색1.  A* 알고리즘의 개념- 닫힌 목록 : 탐색이 끝난 노드들의 집합 ( 다시 탐색 X )- 열린 목록 : 탐색이 가능한 노드들의 집합 ( 닫힌 목록과 인접한 노드 )g(x) : 시작점을 기준으로 한 비용h(x) : 도착점까지의 예상 비용 // 휴리스틱 함수f(x) = g(x) + h(x) - 휴리스틱 함수 h(x)에 따라 성능이 변함  -> h(x) 이 g(x) or 0 인 경우 다익스트라 알고리즘과 동일 + 휴리스틱 함수란?현재 노드에서 목표 노드까지의 예상 비용을 구하는 함수 -> ex. 맨해튼 거리 함수, 유클리디안 거리 함수2..

1. BFS(Breadth First Search) - 너비 우선 탐색최단 경로, 임의의 경로를 찾고 싶을 때, 등에 사용- 큐(FIFO) 사용 // 큐를 이용 public void BFS(int index) { Node root = nodes[index]; Queue queue = new Queue(); queue.Enqueue(root); root.marked = true; while (queue.Count > 0) { var node = queue.Dequeue(); for (int i = 0; i 2. DFS(Depth First Search) - 깊이 우선 탐색조합류..