A*2 A* 알고리즘을 이용한 하노이 타워 풀기 A* 알고리즘을 이용해서 일반적으로는 길찾기를 많이 합니다. A* 알고리즘은 적절한 에너지 함수만 제공해준다면, 최적의 해를 적은 노드 탐방으로 찾을 수 있는 장점이 있습니다. 그러나 적절한 에너지 함수를 제공할 수 없는 경우에는, A* 알고리즘은 상당히 많은 시간을 소모할 수 있고, 또한 최적의 해를 찾을 수 없을 수도 있습니다. 1) 에너지 함수가 실제 소요되는 것보다 상대적으로 너무 적을 때에는 많은 노드를 탐방하게 됩니다. 2) 에너지 함수가 실제 소요되는 것보다 더 많을 가능성이 아주 조금이라도 있다면, 최적의 해를 찾는다는 보장을 할 수 없습니다. 제가 A* 알고리즘을 조금 더 관심있게 보고 있는 것은 바로 2)항 때문입니다. 게임 AI 로직에서 최적의 해를 꼭 찾아야한다고 볼 수 없습니다. .. 2014. 12. 11. A* 알고리즘을 위한 우선순위 큐 구현 알고리즘 그래프 이론을 들어가면, 가장 끝판왕은 역시나 A* 알고리즘이라고 생각합니다. A* 알고리즘은 게임 프로그래밍에서도 많이 쓰이는 기법이니, 알아두는 것이 좋지 않을까 하네요. A* 알고리즘을 적용할 때, 방문해야할 노드 수가 많을 때, 속도에 영향을 미치는 부분은 두가지가 있습니다. 첫번째는 가장 작은 에너지 함수값을 갖는 노드를 찾는 것입니다. 두번째는 방문한 셋에 포함되어 있는지 찾는 것입니다. 제 경우에는 작은 에너지 함수값을 갖는 노드를 찾는 것은 힙을 이용한 우선순위 큐를 사용합니다. 힙을 이용하게 되면, 삽입과 삭제의 경우 O(logn)의 점근적 시간이 필요합니다. 선형으로 찾는 것보다 훨씬 빠르게 삽입 삭제를 할 수 있습니다. 방문한 셋에 포함되어있는지 검사하는 방법은 해.. 2014. 12. 8. 이전 1 다음 728x90
