21강 A* 알고리즘 기초
1. A* 알고리즘 개념
1) Grid Map(격자지도)상에서 8방향의 방향성에 대해 장애물을 고려하여 Cost를 계산하고, 이 Cost 비용 최소화를 통해 최적의 길을 찾아내는 알고리즘, 주어진 목표 꼭짓점까지 가는 최단경로임을 판단할 수 있는 테스트를 통과하는 그래프/트리 탐색 알고리즘
2. A* 알고리즘 Grid
1) Grid의 크기를 어떻게 설정하는가 즉, 현실세계를 어떠한 크기의 격자로 작게 혹은 크게 쪼갤 것인가에 따라서 A* 알고리즘이 결과값으로 제시할 수 있는 경로의 섬세함과 계산량이 달라짐
- 주어진 환경 정보와 자차의 크기에 따라 Grid의 크기를 적합하게 설정하는 것이 중요
퀴즈)
1. A* 알고리즘에서 cost를 계산할 때 몇가지 방향? 답 1
1. 8
2. 9
3. 10
4. 12
2. 격자 개념에서 가로 5m/세로 5m의 방을 0.1m 크기의 격자로 나누면 몇 개의 격자가 생성되는가? 답 3
1. 25개
2. 250개
3. 2500개
4. 25000개
22강 A* 알고리즘 이해
1. 시작 단계 설정
1) A* 알고리즘은 시작부터 도착까지 8방향에 대한 cost를 계속적으로 확장하여 계산하고 최종적으로 최소의 cost를 보장하는 최단 경로를 선택하게 해주는 알고리즘
2. 탐색 시작 단계와 경로 채점
1) F = G + H
- F : 현재까지 이동하는데 걸린 비용과 예상비용을 합친 총 비용
- G : 시작점으로부터 현재 사각형까지의 경로를 따라 이동하는 데 소요되는 비용
- H : 현재 사각형에서 목적지까지의 예상 이동 비용(시작점과 목적지 사이의 장애물 무시)
- 맨해튼 방법 : 대각선 이동은 생각하지 않고 가로 또는 세로로 이동하는 비용만 계산
2) 탐색 범위 안에 목적지가 들어올 때까지 계속적으로 탐색 -> 목표지점에서 거꾸로 시작점으로 부모 노드를 찾아 최종경로 선택
퀴즈)
1. A* 알고리즘의 설명에서 F=G+H 인데, 여기서 F는 무엇인가? 답 4
1. 시작점부터 현재 사각형까지의 이동 소요 비용
2. 현재 사각형에서 목적지까지의 예상 이동 비용
3. 부분 비용
4. 총 비용
2. F=G+H에서 H 비용을 구할 때, 대각선 이동을 생각하지 않고, 가로 또는 세로로 이동하는 비용만 계산하는 방식은 무엇인가? 답 1
1. 맨하탄 방법
2. A* 방법
3. 생략 방법
4. 최단거리 방법
댓글