티스토리 뷰

[A* algorithm]

여기서는 실제 거리를 고려한 탐색과 최적 우선 탐색 방법을 결합하면 보 다 우수한 탐색 알고리즘을 만들 수 있습니다. 만일 출발 노드 로 부터 각 노드까지의 정확한 거리를 계산할 수 있고 목표 노 드까지의 거리를 예측할 수 있는 경험적(heuristic)정보가 이용 가능하다면 A* 알고리즘을 적용할 수가 있습니다. A* 알고리즘은 출발 노드에서 목표 노드까지 최단 거리를 갖 는 노드를 선택한다. 이를 위한 평가 함수는 F = g + h로 결정 합시다. g는 출발 노드에서 현재 노드까지 최소 비용이며, h는 현재 노드에서 목표 노드까지 예측된 최소 비용이다. 만일 h는 현재 노드에서 목표 노드까지의 실제 거리를 초과하지 않는다면 A* 알고리즘은 항상 최단 거리의 경로를 찾아내며, 이것을 적절 성(ad- missionability)이라 합니다. 여기서 평가 함수와 최적 우선 탐색을 돌아보면, 목적지가 어 디 있는지 알지 못하고 무의미한 탐색을 계속하는 것을 방지하 기 위해서는 탐색 경로를 안내할 수 있는 정보가 필요합니다. 평가 함수 f는 각각의 노드를 숫자로 평가하여 그 노드를 선택 할 때의 상대적인 유리함 또는 상대적 비용을 나타냅니다. 일반 적으로 f(n)은 노드 n과 목표 노드 사이의 거리를 나타내는 것 이 보통입니다. 이와 같은 평가 함수는 탐색하고자 하는 노드들 의 탐색 순서를 정하기 위하여 사용됩니다. 목표와 가까운 거리 에 있는 것으로 평가된 노드를 선택하고, 다시 선택된 노드의 다음 단계의 노드들을 평가하여 목표와 가까운 노드를 선택하는 탐색 방법에 따르면 보다 빨리 목표에 도달하게 됩니다. 그리고 최적 우선 탐색은 항상 평가함수 f(n)의 값이 최소인 노드를 다 음 탐색 노드로 선정합니다. 출발 노드 S에서 목표 노드 G까지 의 평가 함수 f를 사용하여 탐색하는 것이 문제이다. 먼저 S를 OPEN에 넣는다. OPEN에 있는 노드가 G이면 출력하고, 아니면 그 노드를 CLOSED에 넣고, 그 successor 노드를 OPEN에 넣 는다. OPEN에 있는 노드는 f(n)이 가장 작은 것이 우선 순위를 갖도록 넣습니다.

A* Algorithm

begin
input the start node S and the set GOALS of goal nodes:
OPEN ← {S};
CLOSED ← ?;
G[S] ← 0;
PRED[S] ← NULL;
found ← false;
while OPEN is not empty and found is false do
begin
L ← the set of nodes on OPEN for which F is the least;
if L is a singleton then let X be its sole element
else if there are any goal nodes in L 
then let X be one of them else let X be any element of L;
remove X from OPEN and put X into CLOSED;
if X is a goal node then found ← true
else begin
generate the set SUCCESSORS of successors of X;
for each Y in SUCCESSORS do
if Y is not already on OPEN or on CLOSED then
begin
G[Y] ← G[X] + distance(X,Y);
F[Y] ← G[Y] + h(Y); PRED[Y] ← X;
enter Y on OPEN;
end
else /* Y is on OPEN or on CLOSED */
begin
Z ← PRED[Y];
temp ← F[Y] - G[Z] - distance(Z,Y) + G[X] + distance(X,Y);
if temp < F[Y] then
begin
G[Y] ← G[Y] - F[Y] + temp;
F[Y] ← temp; PRED[Y] ← X;
if Y is on CLOSED then
insert Y on OPEN and remove Y from CLOSED;
end;
end;
end;
end;

if found is false then output "Failure"
else trace the pointers in the PRED fields from X back to S. "CONSing"
each node onto the growing list of nodes to get the path from S to X;
end

'기억하자정보 > 알고리즘' 카테고리의 다른 글

A* 의사코드  (0) 2006.12.27
A star algorithm code  (0) 2006.12.27
길찾기(A*) 알고리즘 테스트  (0) 2006.12.26
A* 알고리즘 요약  (0) 2006.12.26
A* 알고리즘  (0) 2006.12.26
댓글
안내
궁금한 점을 댓글로 남겨주시면 답변해 드립니다.