그래서 수학이 뭐에 쓰이는 건데? 1

미로 찾기 A* 알고리즘과 그 제자들의 활용법

항상 사람들이 이야기하는 건 그래서 수학이 뭐에 쓰이는 건데? 실생활에서는 계산만 잘하면 되는 거 아냐?라고 합니다. 그런데 잘 생각해 보면 수학은 의외로 많은 실생활에 쓰이고 있습니다. 1/n 술자리, 데이트 앱에서도 심리학에서도 말이죠~ 다만 그렇게 생각하느냐 그냥 넘어가느냐에 따라 이 세상이 달리 보입니다.

A_ 알고리즘과 실생활 활용.wav

그래서 수학이 뭐에 쓰이는 건데 이제 아주 간단한 이야기부터 해볼 생각입니다. 현실에서 장난감도 세탁기도 청소기도 모두 디지탈화가 되면서 어떻게 움직이 그 원리는 무엇인지 그리고 그 생각의 끝에는 수학의 원리가 들어있다는 것을 찾아가는 과정을 수학식이 아닌 그냥 간단한 유틸리티나 퍼즐로 만들어볼 생각입니다. 

A* 알고리즘(A* algorithm 에이 스타 알고리즘[*])은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 탐색 알고리즘 중 하나입니다.

그래서 만들어본 게 한눈에 모서리에 누가 빨리 도달하는지를 찾는 간단한 퍼즐을 만들어봤습니다. 가운데서 탈출하는 것인데 가장 짧은 거리에서 탈출은 누가 할 것인지 같은 미로 찾기라기보다 판단력게임입니다. 최상단으로 탈출하려면 더 많은 길을 가야겠죠?

농담입니다. 출판사 창고에 있는 책을 빨리 찾아서 다음 창고로 가져다줘야 하는데 그걸 잘 모르는 로봇이 한 번에 많이 책을 수거해서 가져다준다면? 당연히 최단 경로에서 다 모은 다음에 집하하는 게 더 낫겠죠 한대면 모르겠지만 협력이 가능하다면 그런 걸 생각하고 있습니다. 창고선진화 하려면 퍼즐을 잘해야?

� 게임 캐릭터 길 찾기 (Pathfinding): 이게 아마 A* 알고리즘이 가장 유명하게 쓰이는 곳일 거예요!

게임 캐릭터(NPC)가 맵 안에서 이동하거나, 플레이어를 추격하거나, 특정 목표 지점까지 알아서 찾아갈 때, A*가 가장 효율적인 경로를 계산해 줍니다.

스타크래프트 같은 전략 시뮬레이션 게임에서 유닛들이 장애물을 피해 이동하거나, RPG 게임에서 몬스터가 플레이어를 따라올 때 등등! 게임에서 캐릭터가 똑똑하게 움직이는 뒤에는 A* 또는 그 변형 알고리즘이 있는 경우가 많아요. 복잡한 지형에서도 길을 잘 찾게 해 줍니다.

� 로봇/자율 주행 내비게이션:

공장이나 창고를 돌아다니는 로봇, 자율 주행 자동차 등이 주변 장애물을 피해 목표 지점까지 안전하고 빠르게 이동해야 할 때 A* 알고리즘이 활용됩니다.

청소 로봇이 집 안 구조를 파악하고 구석구석 청소 경로를 짤 때도 비슷한 원리가 사용될 수 있습니다.

�️ 지도 앱 / 내비게이션 시스템:

우리가 스마트폰 지도 앱이나 차량 내비게이션에서 ‘최단 경로’, ‘추천 경로’ 등을 검색하잖아요? A* 알고리즘 자체 또는 A의 아이디어를 바탕으로 발전된 알고리즘들이 출발지부터 목적지까지의 도로망에서 가장 효율적인 경로를 계산해 주는 데 사용됩니다. A의 ‘미래 예측(휴리스틱)’ 개념이 여기서 빛을 발하죠!

� 물류 배송 최적화:

택배 회사나 배달 서비스에서 여러 배송지를 거쳐 최종 목적지까지 가는 가장 효율적인 순서와 경로를 결정할 때 응용될 수 있습니다. (이건 ‘외판원 문제’와도 관련 있지만, A*는 여러 지점을 효율적으로 지나는 경로 탐색의 기초가 됩니다.)

� 인공지능 및 문제 해결:

로봇 팔이 여러 단계를 거쳐 조립 작업을 수행하거나, 특정 복잡한 퍼즐 게임(예: 15-퍼즐, 루빅스 큐브 상태 탐색 등)에서 목표 상태까지 가는 최소한의 단계를 찾을 때 A* 알고리즘이 상태 공간 탐색에 활용되기도 합니다.

요약하자면, A* 알고리즘은 “어떤 목표까지 가장 빠르거나 효율적인 길을 찾아야 하는” 거의 모든 분야에서 직간접적으로 사용될 수 있는, 아주 실용적이고 강력한 알고리즘이라고 할 수 있습니다! �

A* 알고리즘의 “과거 비용 + 미래 추정”이라는 핵심 아이디어가 워낙 강력하고 유용하다 보니, 다양한 상황과 요구사항에 맞춰 A*를 개선하거나 변형한 알고리즘들이 많이 파생되었습니다.

몇 가지 대표적인 파생 또는 관련 알고리즘들은 다음과 같습니다.

IDA* (Iterative Deepening A*):

문제점 해결: 오리지널 A*는 탐색 공간이 넓으면 메모리 사용량이 폭발적으로 늘어나는 문제가 있습니다.

해결 방식: IDA*는 정해진 비용 한계(threshold) 내에서만 깊이 우선 탐색(DFS)을 수행하고, 목표를 찾지 못하면 한계를 점차 늘려가며 탐색을 반복합니다. A*처럼 f(x)=g(x)+h(x) 값을 활용하지만, 메모리를 훨씬 적게 사용합니다. 메모리가 매우 제한적인 환경에서 유용합니다.

D* (Dynamic A*) 및 LPA* (Lifelong Planning A*):

문제점 해결: A*는 탐색 환경(예: 지도상의 장애물, 길의 비용)이 고정되어 있을 때 최적이지만, 환경이 실시간으로 변하거나 새로운 정보가 계속 들어올 때는 비효율적입니다. 환경이 변할 때마다 처음부터 다시 계산해야 하니까요.

해결 방식: D*나 LPA* 같은 알고리즘들은 환경이 변했을 때 변경된 부분만 효율적으로 업데이트하여 새로운 최적 경로를 빠르게 찾아냅니다. 로봇 내비게이션처럼 동적으로 변하는 환경에서 경로 계획에 많이 사용됩니다. D*는 초기 버전이고, LPA*가 이를 개선한 형태입니다.

Weighted A*:

목표 변경: 때로는 ‘가장 짧은’ 최적 경로보다 ‘빨리 계산되는’ 경로가 더 중요할 때가 있습니다.

해결 방식: Weighted A*는 f(x)=g(x)+w⋅h(x)와 같이 휴리스틱 h(x)에 가중치(w>1)를 줍니다. 이렇게 하면 미래 추정을 더 중요하게 여기게 되어 탐색하는 노드의 수가 줄어들어 계산 속도는 빨라지지만, 찾은 경로가 최적 경로가 아닐 수도 있습니다 (완벽하게 가장 짧은 길은 포기할 수 있습니다).

Bidirectional A*:

해결 방식: 출발지에서 목표지로 가는 탐색과 목표지에서 출발지로 거슬러오는 탐색을 동시에 진행해서, 중간에서 만나는 지점을 찾는 방식입니다. 탐색 공간을 줄여 탐색 속도를 높이는 데 효과적일 수 있습니다.

A*와 관련 깊은 다른 알고리즘들 (파생은 아니지만 비교 대상):

다익스트라 알고리즘 (Dijkstra’s Algorithm): A*의 휴리스틱(h(x))이 없는 경우(h(x)=0)와 같습니다. ‘과거 비용'(g(x))만 보고 탐색하며, 항상 최적 경로를 찾지만 A*처럼 ‘목표 방향’에 대한 정보가 없어 비효율적일 수 있습니다.

욕심쟁이 최우선 탐색 (Greedy Best-First Search): A*의 ‘과거 비용'(g(x))이 없는 경우(g(x)=0 또는 무시)와 같습니다. 오직 ‘미래 추정'(h(x))만 보고 가장 좋아 보이는 곳으로만 가는 탐색입니다. 계산은 빠를 수 있지만, 최적 경로를 보장하지 못하며 잘못된 길로 빠질 위험도 있습니다.

이처럼 A* 알고리즘은 기본적인 강력함 위에 다양한 문제 상황에 대처하기 위한 여러 변형 알고리즘들을 낳았고, 덕분에 게임, 로봇, 내비게이션 등 여러 분야에서 더욱 폭넓게 활용될 수 있게 되었답니다! �

https://product.kyobobook.co.kr/detail/S000212754141

제가 스도쿠, 매직아이, 다양한 퍼즐 개발자로 유명하지만 그래도 수학책은 써본적이 있긴합니다 3==3=333