A* 알고리즘 (Dijkstra algorithm)

A* 알고리즘: 효율적인 경로 탐색을 위한 휴리스틱 기법

---

 

A* 알고리즘은 그래프에서 출발점부터 목표점까지의 최단 경로를 찾는 데 사용되는 휴리스틱 탐색 알고리즘이다.

이 알고리즘은 Edsger W. Dijkstra의 최단 경로 알고리즘과 Best-First Search(최선 우선 탐색) 알고리즘의 아이디어를 결합하여 탐색 효율성을 높혀준다.

A* 알고리즘의 기본 개념

---

A* 알고리즘은 두 가지 주요 함수를 사용해 각 노드를 평가한다

1. g(n): 출발점부터 현재 노드 n까지의 실제 비용 ->출발지에서 그 노드까지 비용
2. h(n): 현재 노드 n부터 목표점까지의 예상 비용 (휴리스틱) ->그 노드에서 도착지 까지 비용 (예상)

이 두 함수를 합한 f(n) = g(n) + h(n)이 각 노드의 평가 함수가 되며, A* 알고리즘은 f(n) 값이 가장 작은 노드부터 우선적으로 탐색을 진행한다

 

다익스트라 알고리즘과의 비교

---

Dijkstra's Algorithm 은 그래프를 아래와 같이 한 인접한 노드씩 탐색하며

initial노드에서부터 모든 노드까지의 최단 거리를 구하는 알고리즘이다

즉 A*알고리즘에서 h(n) 휴리스틱 함수 값이 0인 알고리즘이 

Dijkstra's Algorithm 이다

A* 알고리즘의 동작 과정

---

1. Open List 와 Closed List를 초기화합니다. 오픈 리스트에는 탐색할 노드들이 저장되고, 클로즈드 리스트에는 이미 탐색한 노드들이 저장된다.
2. 출발점을 오픈 리스트에 넣고 f(n), g(n), h(n) 값을 계산.
3. 오픈 리스트에서 f(n) 값이 가장 작은 노드를 선택하여 현재 노드로 설정. Best First Search!
4. 현재 노드가 목표점이라면 탐색을 종료하고 경로를 반환합니다. break
5. 현재 노드를 오픈 리스트에서 제거하고 클로즈드 리스트에 추가.
6. 현재 노드의 인접 노드들을 탐색:
   • 인접 노드가 클로즈드 리스트에 있다면 무시.
   • 인접 노드가 오픈 리스트에 없다면 오픈 리스트에 추가하고 f(n), g(n), h(n) 값을 계산.
   • 인접 노드가 오픈 리스트에 이미 있다면, 현재 경로를 통해 도달했을 때의 g(n) 값이 더 작은지 확인합니다. 만약 그렇다면 해당 노드의 부모를 현재 노드로 변경하고 f(n), g(n) 값을 갱신.
7. 오픈 리스트가 비어있을 때까지 3-6 단계를 반복합니다.

Ex)

S→C→A→E→F→G

because f(D)=18 and f(A)=16

A* 알고리즘의 휴리스틱 함수 Heuristic Function

---

A* 알고리즘의 성능은 휴리스틱 함수 h(n)의 품질에 크게 좌우된다.

휴리스틱 함수는 admissible(허용 가능)해야 하며, 이는 h(n)이 실제 비용을 과대 평가하지 않아야 함을 의미한다.

대표적인 휴리스틱 함수로는 맨해튼 거리, 유클리드 거리, 대각선 거리 등이 있다.

8 Puzzle with A*

---

1, 2, 3

4,   , 5

6, 7, 8

이 정답인 9칸짜리 공간에 8조각이 있는 퍼즐을 맞춰보자

 

여기에 A*알고리즘을 적용하면 

g(n)함수는 움직인 횟수

h(n)함수는 위 정답과 다른 횟수의 갯수로

설정하면 아래와 같이 접근해 퍼즐을 풀 수 있다

A* 알고리즘의 응용 분야

---

A* 알고리즘은 다양한 분야에서 활용된다:

1. 경로 탐색: 로봇 공학, 자율 주행 차량, 게임 AI 등에서 최적 경로를 찾기
2. 그래프 탐색: 네트워크 라우팅, 최단 경로 문제 등을 해결.
3. 스케줄링: 작업 스케줄링, 자원 할당 문제 등에 적용
4. 문자열 탐색: 패턴 매칭, 시퀀스 정렬 등의 문제를 해결하는 데 사용

결론

---

A* 알고리즘은 휴리스틱을 사용하여 탐색 효율성을 높이는 강력한 알고리즘이다.

적절한 휴리스틱 함수를 선택함으로써 다양한 도메인에서 최적 경로를 찾는 문제를 효과적으로 해결할 수 있으며.

알고리즘의 작동 원리를 이해하고 문제에 맞는 휴리스틱 함수를 설계하는 것이 A* 알고리즘을 성공적으로 활용하는 핵심이라고 할 수 있다

 

https://tonnykang.tistory.com/226

Branch and Bound 분기 한정 알고리즘