A* 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

A* 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 사용되는 그래프 탐색 알고리즘이다. 1968년 피터 E. 하트, 닐스 J. 닐슨, 버트럼 라파엘에 의해 처음 소개되었으며, 셰이 프로젝트의 일환으로 개발되었다. A*는 노드 n에서 목표 노드까지의 예상 거리인 휴리스틱 함수 h(n)과 시작 노드에서 n까지의 거리 g(n)의 합 f(n) = g(n) + h(n)을 최소화하는 경로를 찾는다. A*는 허용 가능한 휴리스틱을 사용할 경우 최적의 경로를 보장하며, 다양한 문제에 적용될 수 있다.

2. 역사

A*는 자신의 행동을 계획할 수 있는 이동 로봇을 구축하는 것을 목표로 한 셰이 프로젝트의 일환으로 만들어졌다. 닐스 닐슨은 원래 셰이의 경로 계획에 그래프 탐색기 알고리즘^[5]을 사용할 것을 제안했다.^[6] 그래프 탐색기는 휴리스틱 함수/heuristic function^영어 에 의해 안내되며, 이는 노드 에서 목표 노드까지의 예상 거리이다. 이 알고리즘은 시작 노드에서 까지의 거리인 을 완전히 무시한다. 버트람 라파엘은 의 합을 사용할 것을 제안했다.^[7] 피터 하트는 현재 허용성과 일관성이라고 부르는 휴리스틱 함수의 개념을 발명했다. A*는 원래 경로의 비용이 해당 비용의 합일 때 최소 비용 경로를 찾기 위해 설계되었지만, A*가 비용 대수 조건을 만족하는 모든 문제에 대해 최적의 경로를 찾는 데 사용될 수 있음이 밝혀졌다.^[8]

1968년의 원본 A* 논문^[4]에는 A*와 유사한 알고리즘이 휴리스틱 함수가 일관성이고 A*의 동점자 처리 규칙이 적절하게 선택된 경우 A*보다 적은 노드를 확장할 수 없다는 정리가 포함되어 있었다. 몇 년 후 일관성이 필요하지 않다고 주장하는 "수정"이 발표되었지만^[9], 이는 1985년 Dechter와 Pearl의 A*의 최적성에 대한 결정적인 연구(현재 최적 효율성이라고 함)에서 잘못된 것으로 밝혀졌으며, 이 연구에서는 허용 가능하지만 일관성이지 않은 휴리스틱을 가진 A*가 A*와 유사한 대체 알고리즘보다 임의로 더 많은 노드를 확장하는 예시를 제시했다.^[13]

A* 알고리즘은 1968년에 피터 E. 하트, 닐스 J. 닐슨, 버트럼 라파엘의 세 사람이 발표한 논문^[39]에서 처음 기술되었다. A*라는 특이한 이름은 이 논문에서 시작점에서 목표점까지의 최단 경로를 확실하게 찾는 알고리즘을 '''허용적/admissible^en-short'''이라고 부르고, 논문의 수식 중에 허용적인 알고리즘의 집합을 '''A'''로 표기했으며, 그 '''A''' 중에서도 평가 횟수가 최적이 되는 것을 '''A^*'''로 표기했기 때문이다^[45]。

2. 1. A* 알고리즘의 명칭

A*는 이동 로봇 구축을 목표로 한 셰이 프로젝트의 일환으로 만들어졌다.^[5]^[6] 초기에는 닐스 닐슨이 그래프 탐색기 알고리즘을 제안했으나, 버트람 라파엘이 ''g''(''n'') + ''h''(''n'') (노드 n에서 목표 노드까지의 예상 거리 ''h''(''n'')와 시작 노드에서 n까지의 거리 ''g''(''n'')의 합)을 사용할 것을 제안했다.^[7] 피터 하트는 허용성과 일관성 개념을 발명했다.^[8]

1968년 논문^[4]에서 A*와 유사한 알고리즘이 특정한 조건에서 A*보다 적은 노드를 확장할 수 없다는 정리가 포함되었으나, 이후 일관성이 필요하지 않다는 주장은 잘못된 것으로 밝혀졌다.^[9]^[13]

3. 알고리즘

시작 노드에서 특정 노드 ''n''을 거쳐 목표 노드에 도달하는 최단 경로의 비용을 ''f* (n)''이라고 하면, ''f* (n)= g* (n) + h* (n)''으로 둘 수 있다. 여기서 ''g* (n)''은 시작 노드에서 ''n''까지의 최소 비용, ''h* (n)''은 ''n''에서 목표 노드까지의 최소 비용이다. 그러나 실제로는 ''g* (n)''과 ''h* (n)''을 미리 제공할 수 없다. 그래서 ''f* (n)''을 다음과 같은 추정치 ''f (n)''으로 바꾸는 것을 생각한다.

: $f(n) = g(n) + h(n)$

여기서 ''g(n)''은 시작 노드에서 ''n''까지의 최소 비용의 추정치, ''h(n)''은 ''n''에서 목표 노드까지의 최소 비용의 추정치이다. 이 경우 ''g''에 관해서는 탐색 과정에서 업데이트를 함으로써 ''g*''에 접근해 갈 수 있지만, ''h*''는 실제로 목표에 도달하기 전까지는 아무도 알 수 없다. 그래서, ''h(n)''에는 사람이 (어느 정도 타당성을 갖도록) 설계한 추정치를 부여하기로 한다. 이 알고리즘을 '''A* 탐색 알고리즘'''이라고 하며, ''h (n)''을 휴리스틱 함수라고 한다.

A* 알고리즘의 구현은 다음과 같다. (이 OPEN 리스트 구현은 나중에 설명하겠지만 느리다는 것을 미리 언급해 둔다.)

# 시작 노드( $S$ )를 생성한다. 또한 계산 중인 노드를 저장하기 위한 우선순위 큐 '''OPEN 리스트'''와 계산이 완료된 노드를 저장하기 위한 '''CLOSE 리스트'''를 준비한다. (이름은 "리스트"지만, 이들의 실제 데이터 구조는 반드시 연결 리스트일 필요는 없다.)

# 골은 반드시 하나일 필요는 없으므로, 골 조건을 만족하는 노드 집합을 $G$ 라고 부르기로 한다.

# 시작 노드를 Open 리스트에 추가한다. 이때 $g(S)$ = $0$ 이며 $f(S)$ = $h(S)$ 가 된다. 또한 Close 리스트는 빈 상태로 한다.

# Open 리스트가 비어있으면 탐색은 실패로 한다 (시작점에서 골에 도달하는 경로가 존재하지 않았다는 의미).

# Open 리스트에 저장된 노드 중 최소 $f(n)$ 값을 가진 노드 $n$ 을 하나 꺼낸다. 같은 $f(n)$ 값을 가진 노드가 여러 개인 경우, 타이 브레이크 기법으로 노드 중 하나를 선택한다.

# $n \in G$ 인 경우 탐색을 종료한다. 그 외의 경우에는 $n$ 을 Close 리스트로 옮긴다.

# $n$ 에 인접한 모든 노드(여기에서는 인접 노드를 $m$ 이라고 한다)에 대해 다음의 연산을 수행한다.

## $f'(m) = g(n) + COST(n,m) + h(m)$ 을 계산한다. 여기서 $COST(n,m)$ 는 노드 n에서 m으로 이동할 때의 비용이다. 또한 $g(n)$ 은 $g(n) = f(n) - h(n)$ 으로 구할 수 있다.

## m의 상태에 따라 다음의 연산을 수행한다.

##* m이 Open 리스트에도 Close 리스트에도 포함되지 않은 경우 $f(m) \leftarrow f'(m)$ 으로 하고 m을 Open 리스트에 추가한다. 이때 m의 부모를 n으로 기록한다.

##* m이 Open 리스트에 있는 경우, $f'(m) < f(m)$ 인 경우 m을 Open에서 삭제하고 $f(m) \leftarrow f'(m)$ 으로 교체한 후, 다시 Open에 삽입한다 (Open이 올바르게 정렬되도록 보장하기 위해). 또한 기록되어 있는 m의 부모를 n으로 교체한다.

##* m이 Close 리스트에 있는 경우, $f'(m) < f(m)$ 인 경우 $f(m) \leftarrow f'(m)$ 으로 하여 m을 Open 리스트로 이동한다. 또한 기록되어 있는 m의 부모를 n으로 교체한다.

# 3 이후를 반복한다.

# 탐색 종료 후, 발견된 골 $n_G$ 에서 부모를 차례로 따라가면 S에서 골 $n_G$ 까지의 최단 경로를 얻을 수 있다.

이상의 흐름을 보면, 알고리즘이 절차적이고 병렬화가 매우 어렵다는 것을 알 수 있다. 그러나, 최근에는 HDA*^[40], PBFS 등과 같은 병렬 기법이 개발되었으며, 특히 HDA*는 768코어 이상의 대규모 병렬 계산 환경에서도 확장될 수 있음이 실증되었다.

3. 1. 작동 원리

시작 노드에서 특정 노드 ''n''을 거쳐 목표 노드에 도달하는 최단 경로의 비용을 ''f* (n)''이라고 하면, ''f* (n)= g* (n) + h* (n)''으로 둘 수 있다. 여기서 ''g* (n)''은 시작 노드에서 ''n''까지의 최소 비용, ''h* (n)''은 ''n''에서 목표 노드까지의 최소 비용이다. 그러나 실제로는 ''g* (n)''과 ''h* (n)''을 미리 알 수 없으므로, ''f* (n)''을 추정치 ''f (n) = g(n) + h(n)''으로 사용한다. ''g(n)''은 시작 노드에서 ''n''까지의 최소 비용의 추정치, ''h(n)''은 ''n''에서 목표 노드까지의 최소 비용의 추정치이다. ''g''는 탐색 과정에서 업데이트를 통해 ''g*''에 접근하지만, ''h*''는 목표에 도달하기 전까지 알 수 없다. 따라서 ''h(n)''에는 사람이 설계한 추정치를 사용하며, 이를 휴리스틱 함수라고 한다.

A* 알고리즘은 다음과 같이 작동한다.

1. 시작 노드를 생성하고, 계산 중인 노드를 저장하기 위한 우선순위 큐 '''OPEN 리스트'''와 계산이 완료된 노드를 저장하기 위한 '''CLOSE 리스트'''를 준비한다.

2. 목표 노드 집합을

G

라고 한다.

3. 시작 노드를 Open 리스트에 추가한다. 이때

g(S)

=

0

이며

f(S)

=

h(S)

가 된다. Close 리스트는 빈 상태로 둔다.

4. Open 리스트가 비어있으면 탐색은 실패이다.

5. Open 리스트에서 최소

f(n)

값을 가진 노드

n

을 꺼낸다. 같은

f(n)

값을 가진 노드가 여러 개면, 타이 브레이크 기법으로 하나를 선택한다.

6.

n \in G

이면 탐색을 종료한다. 아니면

n

을 Close 리스트로 옮긴다.

7.

n

에 인접한 모든 노드(여기에서는 인접 노드를

m

이라고 한다)에 대해 다음 연산을 수행한다.

$f'(m) = g(n) + COST(n,m) + h(m)$ 을 계산한다. 여기서 $COST(n,m)$ 는 노드 n에서 m으로 이동할 때의 비용이다. $g(n)$ 은 $g(n) = f(n) - h(n)$ 으로 구할 수 있다.
m의 상태에 따라 다음 연산을 수행한다.
m이 Open 리스트와 Close 리스트에 모두 없으면, $f(m) \leftarrow f'(m)$ 으로 하고 m을 Open 리스트에 추가한다. m의 부모를 n으로 기록한다.
m이 Open 리스트에 있으면, $f'(m) < f(m)$ 인 경우 m을 Open에서 삭제하고 $f(m) \leftarrow f'(m)$ 으로 교체한 후, 다시 Open에 삽입한다. m의 부모를 n으로 교체한다.
m이 Close 리스트에 있으면, $f'(m) < f(m)$ 인 경우 $f(m) \leftarrow f'(m)$ 으로 하여 m을 Open 리스트로 이동한다. m의 부모를 n으로 교체한다.

8. 3 이후를 반복한다.

9. 탐색 종료 후, 발견된 골

n_G

에서 부모를 차례로 따라가면 시작 노드에서 골

n_G

까지의 최단 경로를 얻을 수 있다.

A* 알고리즘은 절차적이고 병렬화가 어렵지만, HDA*^[40], PBFS 등과 같은 병렬 기법이 개발되었다. 특히 HDA*는 768코어 이상의 대규모 병렬 계산 환경에서도 확장될 수 있음이 실증되었다.^[40]

3. 2. 구현

다음은 이 알고리즘을 설명하는 의사 코드이다.

function reconstruct_path(cameFrom, current)

total_path := {current}

while current in cameFrom.Keys:

current := cameFrom[current]

total_path.prepend(current)

return total_path

// A*는 시작점에서 목표점까지의 경로를 찾습니다.

// h는 휴리스틱 함수입니다. h(n)은 노드 n에서 목표점에 도달하는 데 드는 비용을 추정합니다.

function A_Star(start, goal, h)

// (재)확장해야 할 수 있는 발견된 노드 집합입니다.

// 처음에 시작 노드만 알려져 있습니다.

// 이것은 일반적으로 해시 집합이 아닌 최소 힙 또는 우선 순위 큐로 구현됩니다.

openSet := {start}

// 노드 n에 대해 cameFrom[n]은 시작점에서 n까지 현재 알려진 가장 저렴한 경로 바로 앞에 있는 노드입니다.

cameFrom := 빈 맵

// 노드 n에 대해 gScore[n]은 시작점에서 n까지의 가장 저렴한 경로의 현재 알려진 비용입니다.

gScore := 기본값 Infinity인 맵

gScore[start] := 0

// 노드 n에 대해 fScore[n] := gScore[n] + h(n). fScore[n]은 시작점을 거쳐 종료점까지 가는 경로가 얼마나 저렴할 수 있는지에 대한 현재 최상의 추정치를 나타냅니다.

fScore := 기본값 Infinity인 맵

fScore[start] := h(start)

while openSet is not empty

// 이 작업은 openSet이 최소 힙 또는 우선 순위 큐인 경우 O(Log(N)) 시간에 발생할 수 있습니다.

current := openSet에서 가장 낮은 fScore[] 값을 가진 노드

if current = goal

return reconstruct_path(cameFrom, current)

openSet.Remove(current)

current의 각 이웃에 대해

// d(current,neighbor)는 current에서 neighbor까지의 에지의 가중치입니다.

// tentative_gScore는 시작점에서 current를 통해 neighbor까지의 거리입니다.

tentative_gScore := gScore[current] + d(current, neighbor)

if tentative_gScore < gScore[neighbor]

// neighbor로 가는 이 경로는 이전 경로보다 더 좋습니다. 기록해 둡니다!

cameFrom[neighbor] := current

gScore[neighbor] := tentative_gScore

fScore[neighbor] := tentative_gScore + h(neighbor)

if neighbor not in openSet

openSet.add(neighbor)

// 열린 집합이 비어 있지만 목표점에 도달하지 못함

return failure

'''비고:''' 이 의사 코드에서 노드가 한 경로로 도달하여 openSet에서 제거된 다음 더 저렴한 경로로 도달하는 경우, 허용 가능한 휴리스틱이지만 일관된 휴리스틱이 아닌 경우 반환되는 경로가 최적임을 보장하기 위해 openSet에 다시 추가된다. 휴리스틱이 일관되면 노드가 openSet에서 제거될 때 해당 노드로 가는 경로는 최적임이 보장되므로 노드에 다시 도달하면 ‘tentative_gScore < gScore[neighbor]’ 테스트는 항상 실패한다.

3. 2. 1. 의사 코드

wikitext

다음은 이 알고리즘을 설명하는 의사 코드이다.

function reconstruct_path(cameFrom, current)

total_path := {current}

while current in cameFrom.Keys:

current := cameFrom[current]

total_path.prepend(current)

return total_path

// A*는 시작점에서 목표점까지의 경로를 찾습니다.

// h는 휴리스틱 함수입니다. h(n)은 노드 n에서 목표점에 도달하는 데 드는 비용을 추정합니다.

function A_Star(start, goal, h)

// (재)확장해야 할 수 있는 발견된 노드 집합입니다.

// 처음에 시작 노드만 알려져 있습니다.

// 이것은 일반적으로 해시 집합이 아닌 최소 힙 또는 우선 순위 큐로 구현됩니다.

openSet := {start}

// 노드 n에 대해 cameFrom[n]은 시작점에서 n까지 현재 알려진 가장 저렴한 경로 바로 앞에 있는 노드입니다.

cameFrom := 빈 맵

// 노드 n에 대해 gScore[n]은 시작점에서 n까지의 가장 저렴한 경로의 현재 알려진 비용입니다.

gScore := 기본값 Infinity인 맵

gScore[start] := 0

// 노드 n에 대해 fScore[n] := gScore[n] + h(n). fScore[n]은 시작점을 거쳐 종료점까지 가는 경로가 얼마나 저렴할 수 있는지에 대한 현재 최상의 추정치를 나타냅니다.

fScore := 기본값 Infinity인 맵

fScore[start] := h(start)

while openSet is not empty

// 이 작업은 openSet이 최소 힙 또는 우선 순위 큐인 경우 O(Log(N)) 시간에 발생할 수 있습니다.

current := openSet에서 가장 낮은 fScore[] 값을 가진 노드

if current = goal

return reconstruct_path(cameFrom, current)

openSet.Remove(current)

current의 각 이웃에 대해

// d(current,neighbor)는 current에서 neighbor까지의 에지의 가중치입니다.

// tentative_gScore는 시작점에서 current를 통해 neighbor까지의 거리입니다.

tentative_gScore := gScore[current] + d(current, neighbor)

if tentative_gScore < gScore[neighbor]

// neighbor로 가는 이 경로는 이전 경로보다 더 좋습니다. 기록해 둡니다!

cameFrom[neighbor] := current

gScore[neighbor] := tentative_gScore

fScore[neighbor] := tentative_gScore + h(neighbor)

if neighbor not in openSet

openSet.add(neighbor)

// 열린 집합이 비어 있지만 목표점에 도달하지 못함

return failure

'''비고:''' 이 의사 코드에서 노드가 한 경로로 도달하여 openSet에서 제거된 다음 더 저렴한 경로로 도달하는 경우, 허용 가능한 휴리스틱이지만 일관된 휴리스틱이 아닌 경우 반환되는 경로가 최적임을 보장하기 위해 openSet에 다시 추가된다. 휴리스틱이 일관되면 노드가 openSet에서 제거될 때 해당 노드로 가는 경로는 최적임이 보장되므로 노드에 다시 도달하면 ‘tentative_gScore < gScore[neighbor]’ 테스트는 항상 실패한다.

A* 알고리즘의 구현을 다음에 나타낸다. 이 OPEN 리스트 구현은 나중에 설명하겠지만 느리다는 것을 미리 언급해 둔다.

# 시작 노드(

S

)를 생성한다. 또한 계산 중인 노드를 저장하기 위한 우선순위 큐 '''OPEN 리스트'''와 계산이 완료된 노드를 저장하기 위한 '''CLOSE 리스트'''를 준비한다. (이름은 "리스트"지만, 이들의 실제 데이터 구조는 반드시 연결 리스트일 필요는 없다.)

# 골은 반드시 하나일 필요는 없으므로, 골 조건을 만족하는 노드 집합을

G

라고 부르기로 한다.

# 시작 노드를 Open 리스트에 추가한다. 이때

g(S)

=

0

이며

f(S)

=

h(S)

가 된다. 또한 Close 리스트는 빈 상태로 한다.

# Open 리스트가 비어있으면 탐색은 실패로 한다 (시작점에서 골에 도달하는 경로가 존재하지 않았다는 의미).

# Open 리스트에 저장된 노드 중 최소

f(n)

값을 가진 노드

n

을 하나 꺼낸다. 같은

f(n)

값을 가진 노드가 여러 개인 경우, 타이 브레이크 기법으로 노드 중 하나를 선택한다.

#

n \in G

인 경우 탐색을 종료한다. 그 외의 경우에는

n

을 Close 리스트로 옮긴다.

#

n

에 인접한 모든 노드(여기에서는 인접 노드를

m

이라고 한다)에 대해 다음의 연산을 수행한다.

##

f'(m) = g(n) + COST(n,m) + h(m)

을 계산한다. 여기서

COST(n,m)

는 노드 n에서 m으로 이동할 때의 비용이다. 또한

g(n)

은

g(n) = f(n) - h(n)

으로 구할 수 있다.

## m의 상태에 따라 다음의 연산을 수행한다.

##* m이 Open 리스트에도 Close 리스트에도 포함되지 않은 경우

f(m) \leftarrow f'(m)

으로 하고 m을 Open 리스트에 추가한다. 이때 m의 부모를 n으로 기록한다.

##* m이 Open 리스트에 있는 경우,

f'(m) < f(m)

인 경우 m을 Open에서 삭제하고

f(m) \leftarrow f'(m)

으로 교체한 후, 다시 Open에 삽입한다 (Open이 올바르게 정렬되도록 보장하기 위해). 또한 기록되어 있는 m의 부모를 n으로 교체한다.

##* m이 Close 리스트에 있는 경우,

f'(m) < f(m)

인 경우

f(m) \leftarrow f'(m)

으로 하여 m을 Open 리스트로 이동한다. 또한 기록되어 있는 m의 부모를 n으로 교체한다.

# 3 이후를 반복한다.

# 탐색 종료 후, 발견된 골

n_G

에서 부모를 차례로 따라가면 S에서 골

n_G

까지의 최단 경로를 얻을 수 있다.

3. 2. 2. C++

cpp

// 이 소스 코드의 그래프는 인접 리스트 방식으로 그래프를 표현하였다.

using ii = pair;

priority_queue, greater > pq;

/// N_VER은 그래프의 정점의 개수를 의미한다.

int dist[N_VER], cost[N_VER][N_VER]; /// dist[i]는 i번째 정점까지 가는 최단 거리를 의미한다.

vector edges[N_VER]; /// edges[i]는 i와 연결된 정점과 가중치를 묶어 저장하는 벡터이다.

int minDist(int src, int dst) {

pq.emplace(0, src);

bool success = false;

while (!pq.empty()) {

int v = pq.top(); pq.pop();

if (v == dst) {

success = true;

break;

}

for (ii& adj : edges[v]) {

if (dist[adj.first] < g(v) + adj.second + h(adj.first)) {

dist[adj.first] = g(v) + adj.second + h(adj.first); // 이완 (relaxation)

pq.emplace(dist[adj], adj); // 다음 정점 후보에 탐색하고 있는 정점을 넣는다.

}

}

}

if (!success) return -1;

else return dist[dst];

}

3. 3. 효율적인 OPEN/CLOSE 리스트 구현

A* 알고리즘의 성능을 최적화하는 방법 중 하나는 OPEN/CLOSE 리스트를 효율적으로 구현하는 것이다. 노드 수가 많을 때, 노드를 전개할 때마다 자식 노드를 OPEN 리스트에서 CLOSE 리스트로 옮기거나 그 반대로 옮기는 것은 매우 비효율적이다.^[41]

개선된 구현 방법에서는 노드를 OPEN/CLOSE 리스트 간에 직접 이동시키지 않는다.^[41] 대신, 각 노드에 OPEN 또는 CLOSE 상태를 나타내는 태그를 부여하고, 각 노드에 고유한 정수 ID를 할당한다.^[41] 또한, ID를 통해 노드를

O(1)

시간 안에 참조할 수 있는 해시 테이블을 사용한다.^[41]

OPEN 리스트에는 노드의 ID만 중복을 허용하여 추가한다. 이렇게 하면 중복으로 인한 오버헤드를 최소화할 수 있다.^[41] OPEN 리스트에서 노드를 꺼낼(pop) 때는, 해당 노드의 상태가 OPEN이면 전개를 수행하고, CLOSE이면 그냥 건너뛴다.^[41] 이를 통해 중복된 노드를 여러 번 전개하는 낭비를 방지할 수 있다.^[41]

이러한 방식으로, OPEN 리스트는 f값에 따른 우선순위 큐 아래에 선입선출(FILO) 큐를 둠으로써 구현할 수 있다.^[41] 노드 검색이 이루어지지 않고, 삭제가 맨 앞 또는 맨 뒤에서만 일어나므로 효율적인 구현이 가능하다.^[41] CLOSE 리스트는 사용하지 않는다.^[41]

f값에 의한 우선순위 큐는, 간선(변)의 비용이 1인 경우에는 단순히 f값별 가변 배열로 구현하는 것이 더 빠를 수 있다.^[41] 간선 비용에 큰 편차가 있는 경우에는 힙으로 구현하는 것이 좋다.^[41]

4. 성질

A*의 성질은 h의 성질에 따라 크게 좌우된다.

A*는 다익스트라의 일반화이며, 다익스트라와 마찬가지로 그래프에 음의 가중치 간선이 있으면 완전성을 잃는다. 이 경우에는 벨만-포드 알고리즘을 사용한다.
h(n)은 항상 비 음수여야 한다.
어떤 휴리스틱 h(n)이 모든 노드 n에 대해 실제 목표까지의 거리 h*(n)을 넘지 않는 경우, h는 허용 가능(Admissible)하다고 한다.

:

\forall n,0 \le h(n) \le h^*(n)

이때, A*가 반환하는 경로는 최적, 즉 최단 경로이다.

어떤 휴리스틱 h(n)에 대해, 모든 노드 n과, 이에 인접한 노드 m에 대해 $h(n) \le cost(n,m) + h(m)$ 인 경우, 그 h는 일관적(consistent)이라고 한다.
일관적인 h는 항상 허용 가능하다^[42]。
어떤 두 휴리스틱 함수 h1, h2에 대해 $\forall n,h_1(n) \le h_2(n)$ 가 성립할 때, h2는 h1을 지배(dominate)한다고 부른다. 이때, 특히 양쪽이 허용 가능한 경우, h2를 사용한 탐색이 더 효율적일 것으로 생각된다. 그러나 몇몇 코너 케이스에서는 이 사실이 성립하지 않는다^[43]。

이 알고리즘은 CPU 사용률, 메모리 사용률 등 계산 부하가 높지만, 문제에 맞는 적절한 휴리스틱 함수를 사용함으로써 문제에 대한 최적화가 가능하다.

4. 1. 완전성

유한 그래프에서 음이 아닌 가중치를 갖는 A* 알고리즘은 종료가 보장되며, 해(시작 노드에서 목표 노드까지의 경로)가 존재할 경우 항상 해를 찾을 수 있다는 점에서 완전하다.^[1] A*는 다익스트라의 일반화이며, 다익스트라와 마찬가지로 그래프에 음의 가중치 간선이 있으면 완전성을 잃는다. 이 경우에는 벨만-포드 알고리즘을 사용한다. 유한 분기 계수를 가지는 무한 그래프에서, A* 알고리즘은 해가 존재하는 경우에만 종료가 보장된다.^[1]

4. 2. 허용성

탐색 알고리즘은 최적의 해를 반환하는 것이 보장될 때 '허용 가능'하다고 말한다. A\*에 사용된 휴리스틱 함수가 허용 가능하다면, A\*는 허용 가능하다.^[42] 어떤 휴리스틱 h(n)이 모든 노드 n에 대해 실제 목표까지의 거리 h\*(n)을 넘지 않으면, h는 허용 가능(Admissible)하다고 한다.

:

\forall n,0 \le h(n) \le h^*(n)

이때, A\*가 반환하는 경로는 최적 , 즉 최단 경로이다.

A\*가 탐색을 종료하면, 시작 노드에서 목표 노드까지의 실제 비용이 열린 노드를 통과하는 시작 노드에서 목표 노드까지의 예상 비용보다 낮은 경로를 찾은 것이다. 휴리스틱이 허용 가능하면, 이러한 예상치는 낙관적이다. 따라서 A\*는 이미 가지고 있는 솔루션보다 더 저렴한 솔루션으로 이어질 수 없기 때문에 이러한 노드를 안전하게 무시할 수 있다. 즉, A\*는 시작 노드에서 목표 노드까지 더 저렴한 경로가 있을 가능성을 결코 간과하지 않으므로, 그러한 가능성이 존재하지 않을 때까지 계속 탐색한다.^[42]

4. 3. 일관성

어떤 휴리스틱 h(n)에 대해, 모든 노드 n과, 이에 인접한 노드 m에 대해 $ h(n) \le cost(n,m) + h(m) $인 경우, 그 h는 일관적(consistent)이라고 한다. 일관적인 h는 항상 허용 가능하다.^[42]

A* 알고리즘의 휴리스틱이 일관성을 갖는 경우, A*는 모든 "비병리적" 탐색 문제에 대해 모든 허용 A*-유사 탐색 알고리즘에 관하여 최적 효율성을 가진다. 여기서 비병리적 문제란 "동률 처리까지"를 의미한다. 그러나 휴리스틱이 허용되지만 일관적이지 않은 경우에는 A*보다 임의로 적은 수의 노드를 확장할 수 있는 허용 A*-유사 알고리즘이 존재할 수 있다.

4. 4. 휴리스틱의 지배

어떤 두 휴리스틱 함수 h1, h2에 대해 \forall n,h_1(n) \le h_2(n) 가 성립할 때, h2는 h1을 지배(dominate)한다고 부른다.^[43] 이때, 특히 양쪽이 허용 가능한 경우, h2를 사용한 탐색이 더 효율적일 것으로 생각된다. 그러나 몇몇 코너 케이스에서는 이 사실이 성립하지 않는다.^[43]

5. 복잡도

A* 알고리즘의 시간 복잡도는 휴리스틱에 따라 달라진다. 무제한 검색 공간의 최악의 경우, 확장된 노드의 수는 솔루션의 깊이 에 대해 지수적으로 증가한다.^[25] 이는 목표 상태가 존재하고 시작 상태에서 도달 가능하다고 가정한다. 그렇지 않고 상태 공간이 무한하면 알고리즘은 종료되지 않는다.

휴리스틱 함수는 A* 검색의 실질적인 성능에 큰 영향을 미친다.^[23] 좋은 휴리스틱은 A*가 정보가 없는 검색이 확장할 노드 중 많은 부분을 제거할 수 있게 하기 때문이다.

검색 공간이 트리이고, 단일 목표 상태가 있으며, 휴리스틱 함수 ''h''가 다음 조건을 충족하는 경우 시간 복잡도는 다항식이다.

: $|h(x) - h^*(x)| = O(\log h^*(x))$

여기서 는 최적의 휴리스틱이며, 에서 목표까지 도달하는 정확한 비용이다. 즉, 의 오차는 에서 목표까지의 실제 거리를 반환하는 "완벽한 휴리스틱" 의 로그보다 더 빠르게 증가하지 않는다.^[24]^[25]

A*의 공간 복잡도는 생성된 모든 노드를 메모리에 유지하므로 다른 모든 그래프 검색 알고리즘과 거의 같다.^[1]

6. 응용

A* 알고리즘은 비디오 게임과 같은 애플리케이션에서 일반적인 경로 탐색 문제에 자주 사용되지만, 원래는 일반적인 그래프 순회 알고리즘으로 설계되었다.^[4]

자연어 처리 (NLP)에서 확률적 문법을 사용한 파싱 문제를 포함하여 다양한 문제에 적용된다.^[26]

다른 사례로는 온라인 학습을 통한 정보 검색이 있다.^[27]

6. 1. 경로 탐색

A* 알고리즘은 비디오 게임과 같은 애플리케이션에서 경로 탐색 문제에 자주 사용되지만, 원래는 일반적인 그래프 순회 알고리즘으로 설계되었다.^[4] 자연어 처리(NLP)에서 확률적 문법을 사용한 파싱 문제를 포함하여 다양한 문제에 적용된다.^[26] 다른 사례로는 온라인 학습을 통한 정보 검색이 있다.^[27]

6. 2. 자연어 처리

A* 알고리즘은 원래 일반적인 그래프 순회 알고리즘으로 설계되었지만,^[4] 자연어 처리에서 확률적 문법을 사용한 파싱 문제 등 다양한 문제에 적용된다.^[26] 온라인 학습을 통한 정보 검색에도 활용된다.^[27]

6. 3. 기타

A* 알고리즘은 비디오 게임과 같은 애플리케이션에서 경로 탐색 문제에 자주 사용되지만, 원래는 일반적인 그래프 순회 알고리즘으로 설계되었다.^[4] 자연어 처리(NLP)에서 확률적 문법을 사용한 파싱 문제를 포함하여 다양한 문제에 적용된다.^[26] 온라인 학습을 통한 정보 검색에도 활용된다.^[27]

7. 변형 알고리즘

언제나 A*^[31]
블록 A*
D*
필드 D*
가장자리
가장자리 절약 A* (FSA*)
일반화된 적응형 A* (GAA*)
점증적 휴리스틱 탐색
축소된 A*^[32]
반복 심화 A* (IDA*)
점프 포인트 검색
평생 계획 A* (LPA*)
새로운 양방향 A* (NBA*)^[33]
단순화된 메모리 제한 A* (SMA*)
세타*

A*는 양방향 탐색 알고리즘에도 적용될 수 있지만, 중단 조건에 특별한 주의가 필요하다.^[34]

7. 1. 제한된 탐색

A*는 양방향 탐색 알고리즘에도 적용될 수 있지만, 중단 조건에 특별한 주의가 필요하다.^[34] 빔 서치(Beam Search)는 탐색하는 경로의 수를 제한하여 메모리 사용량을 줄인다.

7. 2. 반복 심화 A* (IDA*)

A*는 반복적 깊이 심화 탐색을 적용하여 메모리 사용량을 줄일 수 있다.^[31] 이를 반복 심화 A* (IDA*)라고 부른다. A*는 양방향 탐색 알고리즘에도 적용될 수 있지만, 중단 조건에 특별한 주의가 필요하다.^[34]

7. 3. 양방향 탐색

A\*는 양방향 탐색 알고리즘에도 적용될 수 있지만, 중단 조건에 특별한 주의가 필요하다.^[34]

8. 다른 알고리즘과의 관계

A* 알고리즘이 탐욕 최우선 탐색 알고리즘과 구별되는 점은 이미 이동한 비용/거리를 고려한다는 것이다.

다익스트라 알고리즘의 일부 일반적인 변형은 모든 노드에 대해 휴리스틱 h(n) = 0인 A*의 특수한 경우로 볼 수 있다.^[11]^[12] 반면에 다익스트라 알고리즘과 A*는 모두 동적 계획법의 특수한 경우이다.^[28] A* 자체는 분기 한정법의 일반화된 형태의 특수한 경우이다.^[29]

A*는 빔 서치와 유사하지만, 빔 서치는 탐색해야 하는 경로의 수에 제한을 둔다는 점에서 차이가 있다.^[30]

8. 1. 다익스트라 알고리즘

다익스트라 알고리즘은 모든 노드에 대해 h(n) = 0인 A* 알고리즘의 특수한 경우로 볼 수 있다.^[11]^[12] 다익스트라 알고리즘과 A* 알고리즘은 동적 계획법의 특수한 경우이다.^[28] A* 알고리즘은 이미 이동한 비용/거리 를 고려한다는 점에서 탐욕 최우선 탐색 알고리즘과 구별된다.

8. 2. 분기 한정법

A* 자체는 분기 한정법의 일반화된 형태의 특수한 경우이다.^[29]

9. 예제: 8-퍼즐 문제

3 x 3 숫자판에 1부터 8까지의 숫자와 빈칸이 주어져 있을 때, 인접한 빈칸으로 숫자를 이동시키는 작업을 반복하여 주어진 숫자 배열을 목표 숫자 배열로 바꿀 수 있다. 이때, 숫자의 총 이동 횟수를 최소화하는 것이 목표이다. 이 문제는 A* 알고리즘으로 해결할 수 있다.

A* 알고리즘에서 ''f(n)'' = ''g(n)'' + ''h(n)''으로 계산된다. 여기서 ''g(n)''은 현재까지 움직인 횟수를 나타내고, ''h(n)''은 앞으로 예상되는 값으로, 이 문제에서는 제자리에 있지 않은 퍼즐의 수를 사용한다.

A* 알고리즘 작동 예시 (노드는 도로로 연결된 도시, h(x)는 목표 지점까지의 직선 거리) 녹색: 시작, 파란색: 목표, 주황색: 방문

A* 알고리즘이 워싱턴 D.C.와 로스앤젤레스 사이의 철도 경로를 찾습니다.

10. 부분 문제 분할 (AND/OR 탐색)

분할 정복과 같이 부분 문제로 분할한 후 전체 문제를 푸는 것이 더 효율적인 문제도 있다. A* 알고리즘과 유사하게, 일반적인 상태 전이는 어느 하나가 목표에 도달하면 되므로 OR이라고 부르고, 부분 문제로 분할하는 경우에는 모든 부분 문제를 해결해야 하므로 AND라고 부르면, 탐색 트리가 AND/OR 트리가 된다.^[44] AND로 상태를 분할할 때, 목표도 분할할 필요가 있다.

같은 상태가 두 번 나타나는 경우 하나의 노드로 묶으면 AND/OR 그래프가 된다. 사이클이 없는 AND/OR 그래프에 대한 A* 알고리즘에 대응하는 것이 1968년에 개발되었으며, 1980년에 '''AO* 알고리즘'''으로 명명되었다.^[45] 사이클이 있는 AND/OR 그래프에 대한 A* 알고리즘에 대응하는 '''A₀ 알고리즘'''은 1976년에 개발되었다.^[46] AND 노드의 비용을 "변의 비용 + 부분 문제의 비용의 최대값" 또는 "변의 비용 + 부분 문제의 비용의 총합" 등과 같은 단조 비감소 함수로 정의하면,^[47] 휴리스틱 함수가 허용적이라면, A*와 마찬가지로 최적해가 구해진다. 또한, 사이클이 없는 AND/OR 그래프는 문맥 자유 문법 (타입-2 문법)^[48], 사이클이 있는 AND/OR 그래프는 제한 없는 문법 (타입-0 문법)에 1대1로 대응한다는 것이 증명되었다.

참조

_[1] 서적 Artificial intelligence a modern approach Pearson 2018
_[2] 서적 Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation Springer
_[3] 논문 Finding shortest paths on real road networks: the case for A* https://zenodo.org/r[...]
_[4] 논문 A Formal Basis for the Heuristic Determination of Minimum Cost Paths
_[5] 논문 Experiments with the Graph Traverser program 1966-09-20
_[6] 서적 The Quest for Artificial Intelligence https://ai.stanford.[...] Cambridge University Press 2009-10-30
_[7] 서적 The Quest for Artificial Intelligence https://ai.stanford.[...] Cambridge University Press 2009-10-30
_[8] 논문 Cost-Algebraic Heuristic Search http://www.aaai.org/[...] 2005
_[9] 논문 Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths' https://www.ics.uci.[...] 1972-12-01
_[10] 논문 Bidirectional A* search on time-dependent road networks https://www.lix.poly[...]
_[11] 간행물 Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools https://books.google[...] Troubadour Publishing Ltd
_[12] 간행물 Python Algorithms: Mastering Basic Algorithms in the Python Language https://books.google[...] Apress
_[13] 논문 Generalized best-first search strategies and the optimality of A*
_[14] 논문 On the Complexity of Admissible Search Algorithms
_[15] 논문 Inconsistent heuristics in theory and practice
_[16] 간행물 Using Inconsistent Heuristics on A* Search https://www.aaai.org[...] 2009
_[17] 논문 First results on the effect of error in heuristic search Edinburgh University Press
_[18] 간행물 The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving https://www.cs.auckl[...] 1973-08
_[19] 간행물 A new approach to dynamic weighting https://dl.acm.org/d[...] Wiley 1992-08
_[20] 논문 Studies in semi-admissible heuristics
_[21] 간행물 A_ε – an efficient near admissible heuristic search algorithm http://ijcai.org/Pas[...] 1983-08
_[22] 간행물 AlphA*: An ε-admissible heuristic search algorithm http://home1.stofane[...] Institute for Production Technology, University of Southern Denmark 2014-11-05
_[23] AIMA
_[24] 서적 Heuristics: Intelligent Search Strategies for Computer Problem Solving https://archive.org/[...] Addison-Wesley
_[25] AIMA
_[26] 간행물 A* parsing: fast exact Viterbi parse selection https://people.eecs.[...]
_[27] 논문 A Group-Testing Algorithm with Online Informational Learning http://www.eng.tau.a[...] 2016-02-12
_[28] 간행물 A Guide to Heuristic-based Path Planning https://www.cs.cmu.e[...]
_[29] 논문 General branch and bound, and its relation to A∗ and AO∗ https://www.cs.umd.e[...]
_[30] 웹사이트 Variants of A* http://theory.stanfo[...] 2023-06-09
_[31] 논문 Anytime Heuristic Search https://www.jair.org[...] 2007
_[32] 논문 Investigating Reduced Path Planning Strategy for Differential Wheeled Mobile Robot https://www.cambridg[...] 2019-05-14
_[33] 간행물 Yet another bidirectional algorithm for shortest paths https://repub.eur.nl[...] Econometric Institute, Erasmus University Rotterdam
_[34] 웹사이트 Efficient Point-to-Point Shortest Path Algorithms http://www.cs.prince[...] Princeton University
_[35] 서적 "Heuristics intelligent search strategies for computer problem solving" Addison-Wesley
_[36] 논문 The FF planning system: Fast plan generation through heuristic search
_[37] 논문 Landmarks, critical paths and abstractions: what's the difference anyway?
_[38] 논문 How Good is Almost Perfect?
_[39] 학술지 A Formal Basis for the Heuristic Determination of Minimal Cost Paths http://ai.stanford.e[...]
_[40] 논문 Scalable, Parallel Best-First Search for Optimal Sequential Planning
_[41] 논문 Implementing fast heuristic search code https://www.aaai.org[...] 2012-07
_[42] 서적 Artificial intelligence: a modern approach
_[43] 문서 Common Misconceptions Concerning Heuristic Search
_[44] 학술지 Searching problem-solving and game-playing trees for minimal cost solutions Amsterdam : North-Holland
_[45] 서적 人工知能の原理日本コンピュータ協会 1983-01-15
_[46] 학술지 Generalized and/or graphs http://www.sciencedi[...]
_[47] 학술지 A General Paradigm for AND/OR Graph and Game Tree Search http://www.cs.utexas[...]
_[48] 학술지 Equivalence between AND/OR graphs and context-free grammars http://dl.acm.org/ci[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com