반응형 Hanoi2 A* 알고리즘을 이용한 하노이 타워 풀기 A* 알고리즘을 이용해서 일반적으로는 길찾기를 많이 합니다. A* 알고리즘은 적절한 에너지 함수만 제공해준다면, 최적의 해를 적은 노드 탐방으로 찾을 수 있는 장점이 있습니다. 그러나 적절한 에너지 함수를 제공할 수 없는 경우에는, A* 알고리즘은 상당히 많은 시간을 소모할 수 있고, 또한 최적의 해를 찾을 수 없을 수도 있습니다. 1) 에너지 함수가 실제 소요되는 것보다 상대적으로 너무 적을 때에는 많은 노드를 탐방하게 됩니다. 2) 에너지 함수가 실제 소요되는 것보다 더 많을 가능성이 아주 조금이라도 있다면, 최적의 해를 찾는다는 보장을 할 수 없습니다. 제가 A* 알고리즘을 조금 더 관심있게 보고 있는 것은 바로 2)항 때문입니다. 게임 AI 로직에서 최적의 해를 꼭 찾아야한다고 볼 수 없습니다. .. 2014. 12. 11. 하노이 타워 알고리즘을 하다보면, 자기호출함수 부분을 배울 때, 하노이 타워에 관련되어서는 한번쯤 이야기가 됩니다. 하노이 타워는 대표적인 재귀적 관점이 들어가 있습니다. (사진출처 : 위키피디아) 하노이 타워가 재귀적 관점이 들어가는 가장 큰 이유는, 작은 디스크 위에 큰 디스크가 올라갈 수 없다는 이유때문입니다. 위 그림에서 첫번째 기둥에 있는 8개의 디스크를 가운데 기둥으로 모두 옮겨야 한다고 하면, 가장 큰 디스크는, 위에 있는 7개의 디스크를 맨 오른쪽 기둥으로 옮기고 나서야 옮길 수 있습니다. 가장 큰 디스크를 가운데 기둥으로 옮긴다음, 맨 오른쪽에 있는 7개의 디스크를 가운데 기둥으로 옮기면 됩니다. 그래서 n개의 디스크를 옮긴다면, 다음과 같이 재귀적 알고리즘을 적용할 수 있습니다. 1) n-1개의 디.. 2014. 12. 5. 이전 1 다음 728x90
