[알고리즘] 『A*알고리즘』에 대하여

소개글

[알고리즘] 『A*알고리즘』에 대하여에 대한 보고서 자료입니다.

목차

1. 들어가는 말

2. 용어정리

3. A*알고리즘 관련이론

4. A*알고리즘

5. A*알고리즘의 간단한 예

6. A*알고리즘 코드

7. 맺음말

본문내용

>numchildren++] = check;
if(g < check->g){
check->parent = node;
check->g = g;
check->f = g + check->h;
}
} else if (check = CheckLIst(m_pClosed, num)){
node->children[node->numchilderen++] = check;
if(g < check->g){
check->parent = node;
check->g = g;
check->f = g + check->h;
UpdateParents(check);
}
}
LinkChild는 _asNode형의 포인터 두 개를 받는다. 하나는 부모노드를 다른 하나는 임시 노드를 의미한다. 일단 이 함수는 temp로부터 좌표정보를 얻어
g값을 계산한다. 그리고 난 후 현재 노드가 OPEN LIST에 있는지 CLOSED LIST에 있는지 판단한다. 그리고 OPEN LIST에서 노드를 찾은 경우 이 노드를 자식 배열에 추가한다. 아울러 g값을 비교판단한다.
else {
_asNode *newnode = new _asNode(x, y);
newnode->parent = node;
newnode->g = g;
newnode->h = abs(x-m_iDX) + abs(y-m_iDY);
newnode->f = newnode->g + newnode->h;
newnode->number = Coord2Num(x, y)
AddToOpen(newnode)
node->children[node->numchildren++] = newnode;
}
}
그리고 OPEN LIST와 CLOSED LISt 모두에서 찾을 수 없다면 새 노드를 만들고 f, g, h값들을 배정한다. 그런 다음에는 그것을 OPEN LIST에 추가하고 부모의 자식 배열에도 추가한다.
void CAStar::UpdateParents(_asNode *node);
{
int g = node->g, c= node->numchilderen;
_asNode *kid = NULL;
for(int k=0;k kid = node->children[k];
if(g+1 < kid->g){
kid->g = g+1;
kid->f = kid->g + kid->h;
kid->parent = node;
Push(kid);
}
}
여기서 중요한 것은 node의 g값이 UpdateParents를 호출하기전에 갱신되었음을 기억해야 한다. 그런 이유로 주어진 노드의 모든 자식들을 점검해서 자식들의 g값을 갱신할 것이지 판단하는 과정이 필요한 것이다.
_asNode *parent;
while(m_pStack) {
parent = Pop();
c = parent->numchildren;
for(int k=0; k kid->g=parent->g + udFunc(udCost, parent, kid, 0, m_pCBData)
kid->f = kid->g + kid->h;
kid->parent = parnet;
Push(kid);
}
}
}
}
기본적으로 처음의 반과 동일하지만 node의 값ㄷ르을 사용하는 대신 Stack으로부터 노드들을 뽑는다.
7. 맺음말
A*알고리즘은 기본적으로 확장성이 좋고 문제의 해결에 있어서 우회적인 해법을 제시해주는 좋은 알고리즘 중 하나이다. A*알고리즘이 보다 효율적으로 응용되기 위해 가장 중요한 것은 휴리스틱 함수가 어떻게 조직되는가와 밀접한 관련을 맺는다. 게다가 A*알고리즘은 응용과 확장이라는 측면에서 잠재력이 높은 편이다. 좀 어렵긴 하지만 적극적인 이해를 바탕으로 새로운 분야에 적용해 본다면 의외의 좋은 결과가 나올 수 있다.

키워드

A알고리즘,   A*알고리즘,   알고리즘,   노드,   휴리스틱,   A알고리즘 코드,   A*,   에이알고리즘