A*
-
A* 알고리즘Algorithm with C/ETC 2021. 3. 19. 22:11
내용은 책 1권, 5권, 7권에서 발췌. A* 알고리즘의 역사는 너비 우선 탐색에서 시작한다. 너비 우선 탐색은 트리에서 한 노드의 모든 자식 노드를 점검한 후에 트리의 다음 수준으로 내력가는 방식이다. 현재 수준의 자식 노드들에서 목표를 발견하지 못하면 자식 노드들을 한 수준 더 전개해서 검색을 진행한다. 구현 환경은 Microsoft Visual Studio 2008 A*의 이론에 대해서는 다른 블로그에 자세히 설명되었으므로 여기서는 구현의 목적에 초점을 두도륵 한다. 필요한 자료구조 힙(최소힙), 연결 리스트이며, 기존의 힙은 최대 힙으로 구현을 하였는데, 최소 힙을 만드려면 부등호의 방향만 변경하면 된다. designatedroom87.tistory.com/27?category=871993 최대 ..