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