예전 자유 게시판

AI Game programming wisdom 에서 A* 알고리즘 문제

안융기 2005-04-08 17:04

안녕하세요.

AI Game programming wisdom을 보고 A* 알고리즘을 실제로 구현해보고 있는데요.
(다 만들고 보려고 첨부한 소스 참고 안 하고 있음.)

191-192 페이지에 걸쳐 설명된 A* 알고리즘에 문제가 있는 것 같습니다.

"닫힌 목록"에 노드를 추가하는 부분이 없군요.

혹시나 해서 GPG 1을 살펴보았는데 342-343 페이지에 의사 코드로 설명된 A* 알고리즘을 바탕으로
wisdom 쪽의 알고리즘을 수정해보면, 아래처럼 수정해야할 것 같습니다.

5.b.i.1. 만일 그렇다면 열린 목록이나 닫힌 목록에서 빼내고, f를 새로운 값으로 설정한 후 열린 목록에 넣는다.
6. B를 닫힌 목록에 추가한 후 4부터 다시 반복한다.


제 생각에는 GPG 쪽이 맞는것 같습니다.
wisdom 쪽의 오류인지 검토 부탁 드립니다.
(제가 다 짜버리면 어느 쪽이 맞는지 알 수 있겠군요.)
그럼..


류광 2005-04-09 00:04

보고 감사합니다.

닫힌 목록에 노드를 추가하는 단계가 없다는 것은 확실히 오류인 것 같습니다...

제시하신 수정 사항이 정확한지는 시간을 내서 검토를 해보겠습니다...만 그 전에 구현을 하셔서 증명을 해주시면 더 고맙겠습니다 :)

안융기 2005-04-11 21:04

GPG 에 있는대로 짰더니 되는군요. Wisdom 쪽에는 위에 언급한 두 개를 추가하셔야겠습니다.
소스는 ... 회사에서 쓸려고 짠거라 아쉽게도 공개할 수 없습니다.