🔍 인공지능 탐색 알고리즘 정리

🔍 탐색(Search)이란? 🤖

탐색(Search)이란, 주어진 문제의 해답을 찾기 위해 가능한 경로를 조사하는 과정을 의미합니다.
탐색 알고리즘은 길 찾기, 게임 AI, 네비게이션, 데이터 구조 활용 등에 필수적으로 사용됩니다.

✅ 탐색 알고리즘의 주요 활용 사례

네비게이션 시스템 (Google Maps, Waze) → 최적 경로 찾기
게임 AI (체스, 스타크래프트, RPG 게임) → 최적의 움직임 결정
로봇공학 (자율주행, 로봇 경로 설정) → 장애물을 피해 이동
웹 크롤링 (Google 검색 엔진) → 링크를 따라가며 정보를 탐색

📌 1. 맹목적 탐색(Blind Search)

✅ 맹목적 탐색이란?

맹목적 탐색(Blind Search)은 문제 해결을 위한 사전 정보 없이 가능한 모든 경로를 탐색하는 방식입니다.
이 방식은 휴리스틱(heuristic, 경험적 정보)을 사용하지 않으며, 목표 상태에 도달할 때까지 탐색을 계속합니다.

🔍 맹목적 탐색 알고리즘 종류

		탐색 기법설명특징
깊이 우선 탐색(DFS)	한 경로를 끝까지 탐색한 후, 되돌아가 다른 경로 탐색	스택(Stack) 또는 재귀(Recursion) 사용
너비 우선 탐색(BFS)	루트에서 가까운 노드부터 탐색	큐(Queue) 사용, 최단 경로 보장
깊이 제한 탐색(Depth-Limited Search, DLS)	DFS에 최대 탐색 깊이를 설정하여 무한 루프 방지	메모리 절약 가능
반복적 깊이 심화 탐색(Iterative Deepening DFS, IDDFS)	DLS를 반복적으로 수행하여 최적의 해를 찾음	DFS와 BFS의 장점 결합

💡 맹목적 탐색은 문제 해결의 보편적인 방법이지만, 비효율적일 수 있음!

📌 2. 정보 이용 탐색(Heuristic Search)

✅ 정보 이용 탐색이란?

정보 이용 탐색(Heuristic Search)은 문제 해결을 위해 휴리스틱(heuristic, 경험적 정보)을 활용하는 탐색 방식입니다.
즉, 최적의 경로를 빠르게 찾기 위해 예상 비용을 계산하여 탐색을 진행합니다.

🔍 주요 알고리즘

		탐색 기법설명특징
휴리스틱 탐색(Heuristic Search)	비용이 낮을 것으로 예상되는 경로를 먼저 탐색	최적 해를 보장하지 않음
*A 알고리즘(A-Star Algorithm)**	DFS와 BFS의 장점을 결합하여 최적 경로 탐색	`f(n) = g(n) + h(n)` 공식 활용
그리디 탐색(Greedy Best-First Search)	목표에 가장 가까워 보이는 노드를 먼저 탐색	효율적이지만 최적 경로 보장 X

💡 정보 이용 탐색은 맹목적 탐색보다 효율적이지만, 휴리스틱이 부정확하면 성능이 떨어질 수 있음!

📌 3. 게임에서의 탐색(Game Search)

게임 인공지능(AI)은 상대와의 경쟁을 고려하여 최적의 움직임을 선택하는 알고리즘을 사용합니다.
게임 탐색 알고리즘은 체스, 바둑, 오목, 스타크래프트 AI 등에서 활용됩니다.

🔍 게임 탐색 알고리즘 종류

		탐색 기법설명특징
미니맥스 알고리즘(Mini-Max Algorithm)	상대가 최선의 수를 두는 것을 가정하고, 가장 유리한 수를 선택	체스, 바둑, 틱택토 등에 사용
알파-베타 가지치기(α-β Pruning)	미니맥스 알고리즘에서 불필요한 경로를 제거하여 속도를 향상	탐색 공간 절약, 계산량 감소
몬테카를로 시뮬레이션(Monte Carlo Simulation)	무작위 시뮬레이션을 실행하여 승률이 높은 전략을 선택	바둑 AI(AlphaGo), 강화학습에 활용

💡 게임 탐색 알고리즘은 상대방의 수를 예측해야 하므로, 전략적인 계산이 필요!

📌 4. 제약 조건 만족 문제(Constraint Satisfaction Problem, CSP)

✅ 제약 조건 만족 문제란?

제약 조건 만족 문제(CSP, Constraint Satisfaction Problem)는 주어진 제약 조건을 만족하는 해를 찾는 문제입니다.
즉, 문제의 정답을 만족하는 값을 찾되, 주어진 조건을 충족해야 합니다.

🔍 제약 조건 만족 문제 예시

		문제 유형예시특징
스도쿠(Sudoku)	9x9 그리드에서 숫자 중복 없이 배치	백트래킹(Backtracking) 사용
N-퀸 문제(N-Queens Problem)	체스판에 N개의 퀸이 서로 공격하지 않도록 배치	DFS 및 백트래킹 활용
수업 시간표 배정(Scheduling Problem)	학생과 강의실을 배정하는 최적의 스케줄 생성	최적화 알고리즘 적용

💡 CSP 문제는 AI가 복잡한 문제를 해결하는 데 중요한 개념이며, 다양한 분야에서 활용됨!

📌 5. 탐색 알고리즘 비교

				알고리즘방식활용 분야장점단점
DFS	깊이 우선 탐색	그래프 탐색, 퍼즐 해결	메모리 효율적	최단 경로 보장 X
BFS	너비 우선 탐색	최단 거리 찾기	최단 경로 보장	메모리 사용량 큼
A*	최적 경로 탐색	네비게이션, 게임 AI	효율적, 최적 경로 보장	계산량 많음
미니맥스	게임 탐색	체스, 바둑, 스타크래프트	전략적 계산 가능	계산량 많음
몬테카를로	무작위 시뮬레이션	강화학습, 바둑 AI	유연한 전략	계산량이 많음
CSP	제약 조건 해결	스도쿠, 일정 관리	최적화 가능	문제 복잡도 증가

🎯 마무리: 탐색 알고리즘은 어디에 활용될까?

📌 맹목적 탐색(Blind Search) → 퍼즐 게임, 경로 탐색, 트리 구조 분석
📌 정보 이용 탐색(Heuristic Search) → 네비게이션, 자율주행, AI 추천 시스템
📌 게임 탐색(Game Search) → 체스 AI, 바둑 AI, 스타크래프트 AI
📌 제약 조건 만족 문제(CSP) → 스도쿠, 시간표 최적화, 로봇 제어