🔍 인공지능 탐색 알고리즘 - 정보 이용 탐색

📌 1. 정보 이용 탐색(Heuristic Search)란?

✅ 정보 이용 탐색이란?

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

📌 정보 이용 탐색의 특징
✔ 맹목적 탐색(DFS, BFS)보다 빠르고 효율적
✔ 문제 해결을 위한 추가적인 정보(휴리스틱 함수)를 사용
✔ 최적의 해를 보장하지 않을 수도 있음 (휴리스틱이 부정확할 경우 성능 저하 가능)

📌 정보 이용 탐색이 사용되는 분야

• 네비게이션 시스템 (Google Maps, Waze) → 최적 경로 찾기

• 게임 AI (체스, 스타크래프트, RPG 게임) → 최적의 움직임 결정

• 로봇공학 (자율주행, 로봇 경로 설정) → 장애물을 피해 이동

• 자연어 처리(NLP) → 문장 의미 분석 및 검색 최적화

📌 2. 휴리스틱 탐색(Heuristic Search)

✅ 휴리스틱 탐색이란?

휴리스틱 탐색은 추가적인 경험적 정보를 이용하여 탐색 속도를 높이는 기법입니다.
즉, 가장 가능성이 높은 경로를 우선적으로 탐색하여 최적의 해결책을 찾는 방식입니다.

📌 휴리스틱 탐색의 핵심 개념
✔ 문제 해결을 위한 직관적 판단 사용
✔ 완전한 탐색을 수행하지 않고, 가장 유망한 방향을 선택하여 탐색
✔ 정확한 해답을 보장하지 않지만, 빠른 해결 가능

🔍 휴리스틱 탐색의 주요 알고리즘

💡 휴리스틱 탐색은 문제 해결을 빠르게 하지만, 휴리스틱 함수의 품질에 따라 성능이 달라질 수 있음!

📌 3. A* 알고리즘 (A-Star Algorithm)

✅ A* 알고리즘이란?

A* 알고리즘은 DFS와 BFS의 장점을 결합하여 최적 경로를 찾는 탐색 알고리즘입니다.
이 알고리즘은 휴리스틱(Heuristic) 함수를 사용하여 더 나은 방향으로 탐색할 수 있도록 설계되었습니다.

📌 A* 알고리즘의 공식

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

• g(n): 시작점에서 현재 노드까지의 실제 비용

• h(n): 현재 노드에서 목표까지의 예상 비용 (휴리스틱)

🔍 A* 알고리즘의 동작 과정

1. 시작 노드를 오픈 리스트에 추가하고, g(n) = 0으로 설정

2. 오픈 리스트에서 f(n)이 가장 작은 노드를 선택하여 현재 노드로 설정

3. 현재 노드가 목표 노드이면 탐색 종료

4. 현재 노드의 인접 노드에 대해 다음을 수행:

   • 인접 노드가 폐쇄 리스트에 있으면 무시

   • 인접 노드가 오픈 리스트에 없으면 추가하고 g(n)과 f(n)을 계산

   • 인접 노드가 오픈 리스트에 이미 있으면, 더 작은 g(n)이 발견된 경우 업데이트

5. 현재 노드를 폐쇄 리스트에 추가하고, 2번 과정 반복

✅ A* 알고리즘의 특징

✔ 휴리스틱 함수를 활용하여 효율적인 탐색 가능
✔ 최적 경로를 보장
✔ 네비게이션, 게임 AI, 로봇 경로 탐색 등에 활용

✅ A* 알고리즘 코드 구현 (Python)

import heapq

def a_star(graph, start, goal, h):
    open_list = []
    heapq.heappush(open_list, (0 + h[start], start))
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0

    while open_list:
        _, current = heapq.heappop(open_list)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]

        for neighbor, cost in graph[current]:
            tentative_g_score = g_score[current] + cost
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score = tentative_g_score + h[neighbor]
                heapq.heappush(open_list, (f_score, neighbor))

    return None

# 예제 그래프
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': [('E', 3)],
    'E': []
}

# 휴리스틱 값 (예제)
heuristic = {'A': 6, 'B': 4, 'C': 2, 'D': 1, 'E': 0}

# 실행
path = a_star(graph, 'A', 'E', heuristic)
print("A* 알고리즘 탐색 결과:", path)

📌 A 알고리즘 실행 결과 예시

A* 알고리즘 탐색 결과: ['A', 'B', 'C', 'D', 'E']