728x90 반응형 pathfinding3 A* Algorithm A* 알고리즘주어진 출발점에서 목표지점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다.최단 경로를 찾는다는 공통점을 가지지만, A*는 데이크스트라에 휴리스틱(Heuristic)이라는 개념을 추가하여 효율성을 높인 알고리즘이다. 본래 A 알고리즘이라고 불렸지만 적절한 휴리스틱에 따라서 최적의 알고리즘이 되기 때문에 A* 알고리즘이라 불린다. 데이크스트라와 관계A*알고리즘은 데이크스트라 알고리즘의 확장 버전이라고 볼 수 있다. 데이크스트라에서 사용하는 시작점으로부터의 실제 거리 g(n)에 목표점까지의 예상 거리 h(n)라는 휴리스틱을 더한 값을 우선순위 기준으로 사용한다. f(n) = g(n) + h(n) g(n) : 시작점에서 현재 노드 n까지의 실제 비용h(n) : 현재 노드 n에서 목.. 2025. 5. 30. 탐색 알고리즘 - BFS/DFS BFSBreath-First Search, 너비 우선 탐색트리 자료구조의 순회 방법으로 같은 계층의 모든 노드를 먼저 탐색하고 다음 계층을 탐색하는 방식으로 순차적으로 진행하는 방식이다. 아직 탐색하지 않은 자식 노드를 추적하고 모든 노드를 탐색하기 위해서 일반적으로 FIFO 방식인 큐를 사용한다.탐색을 시작할 때 먼저 루트 노드를 큐에 넣는다. 큐에서 가장 앞에 있는 노드를 먼저 탐색하고 그 자식 노드를 모두 큐에 넣는다. 그리고 큐에서 제거를 하면 가장 먼저 넣었던 노드가 빠지게 된다. 그리고 다시 큐의 가장 앞에 있는 노드를 탐색하고 자식을 큐에 넣고 가장 앞의 노드를 제거하는 과정을 큐가 빌 때까지 반복하면 최종적으로 모든 노드를 방문할 수 있게 된다. 이 방법을 확장하면 사이클 유무, 방향성.. 2025. 5. 29. Pathfinding Visualizer - 탐색 알고리즘 시각화 툴 탐색 알고리즘을 시각화하기 위한 웹 페이지 https://bakcoding.github.io/pathfinding-algorithm/index.html Pathfinding Visualizer bakcoding.github.io 2025. 5. 29. 이전 1 다음 728x90 반응형
