목록경로찾기 (1)

맛있는감귤

A* 알고리즘 쉬운 개념 설명

개요그래프/트리 탐색 알고리즘. 게임에서 많이 사용되는 최단거리 길찾기 알고리즘이다.다익스트라 확장판. BFS의 가지치기 알고리즘이라 생각하면 된다. 핵심 개념 1. 최소가 되는 지점을 우선 탐색 (우선 순위 큐)2. 휴리스틱 추정값 사용3. Open List / Closed List를 이용하여 노드 관리 다른 알고리즘과 차이점BFS (Breadth First Search) : 완전 탐색 알고리즘. 우선순위없이 모든 노드를 탐색한다. 다익스트라 : 일반적인 최단거리 알고리즘. 한 노드를 기준으로 모든 노드의 최단 경로를 찾기 때문에 시간 비용이 많이 든다.플로이드 : 모든 노드의 최단 경로를 찾는 알고리즘. 일반적인 시간 복잡도 O(N^3). 개념 설명1. 휴리스틱 추정값 f(x) = h(x) + g(x..
알고리즘/알고리즘 정보 2017. 5. 1. 20:23
이전 Prev 1 Next 다음