3강

경험적 탐색 (Heuristic Search)

---

1. 경험적 탐색이란?

• 목표 상태를 더 빠르게 찾기 위해 경험적 규칙(heuristic)을 사용하는 탐색 방법
• 단순히 무작정 탐색하는 대신, "어느 방향이 더 좋아 보이는지"를 평가함수로 판단해서 우선순위를 줌

용어 정리

• 평가함수 f(n): 상태 n이 얼마나 "좋은 상태"인지 수치로 나타냄
• 경험적 함수 h(n): 상태 n에서 목표 상태까지 남은 비용을 예측
• 실제 비용 g(n): 출발점에서 상태 n까지 도달하는 데 든 실제 비용
• 전체 평가값 f(n) = g(n) + h(n) (A* 알고리즘에서 사용)

---

2. 언덕오르기 탐색 (Hill Climbing)

개요

• 현재 상태에서 가장 좋은 방향으로 한 걸음씩 올라감
• g(n)은 고려하지 않고, h(n)만으로 판단함
  → 목표까지 남은 예측 비용이 가장 작은 후계 노드를 선택

특징

• DFS와 유사하게 작동 (하지만 깊이 제한 없이 최적 방향만 고려)
• 지역 최적값에 빠지기 쉬움

단점 (계수 최적화의 한계)

• 지역 최대값 문제: 더 높은 값이 있지만, 현재보다 높은 곳이 없어서 멈춤
• 고원 문제: 주변 값들이 동일해 어디로 가야 할지 판단 불가능
• 능선 문제: 좁고 긴 오르막을 올라가지 못하고 옆으로 빠짐

---

3. 모의 담금질 (Simulated Annealing)

개요

• 언덕오르기처럼 좋은 방향으로 이동하지만, 가끔 나쁜 방향으로도 이동함
• 이렇게 함으로써 지역 최적값에 빠지지 않고 전역 최적값을 찾을 확률을 높임

알고리즘 요약

1. 초기 상태와 초기 온도 설정
2. 현재 상태에서 임의의 후계 상태 선택
3. ΔE = h(새 상태) - h(현재 상태) 계산
4. ΔE < 0 → 이동 (더 좋음)
5. ΔE ≥ 0 → 확률적으로 이동 (확률 = e^(-ΔE/T))
6. T를 점점 줄이며 반복 → "서서히 식히는" 개념

핵심 아이디어

• 온도가 높을 땐 아무 방향으로든 잘 움직임 (탐색 범위 넓음)
• 온도가 낮아지면 더 좋은 방향만 선택함 (수렴 단계)

---

4. A* 알고리즘

개요

• 경험적 탐색 + 실제 비용을 모두 고려한 탐색
• f(n) = g(n) + h(n) 으로 계산된 평가값이 가장 작은 노드를 우선 탐색
• 균일비용 탐색(UCS)과 비슷하지만, h(n)이라는 예측치를 추가로 사용

조건

• h(n)은 실제 남은 비용을 과대평가하지 않아야 함
  • 즉, 항상 h(n) ≤ 실제 h*(n)이 되어야 함 → 이걸 Admissible Heuristic이라고 함

알고리즘 요약

1. 시작 노드를 OPEN 리스트에 추가 (f(start) = g + h)
2. f(n)이 가장 작은 노드를 꺼냄
3. 목표 노드이면 종료
4. 후계 노드들 생성하고 g, h, f 계산
5. 중복 검사 및 갱신
6. OPEN 리스트에 넣고 정렬
7. 반복

장점

• h(n)을 잘 설계하면 최적해 보장 + 빠른 탐색 속도

---

5. 요약

탐색 방법	핵심 아이디어	평가 기준	장점	단점
언덕오르기	가장 좋은 방향으로만 이동	h(n)	간단함	지역 최적값에 빠질 수 있음
모의 담금질	확률적으로 나쁜 방향도 허용	h(n) + 확률	전역 최적해 가능성	속도 느림, 파라미터 조절 필요
A*	경험 + 실제 비용 고려	g(n) + h(n)	최단 경로 보장	h(n)이 부정확하면 비효율적

---

코드

공통 목표 함수

# 최소값을 찾고 싶은 함수 (목표)
def objective_function(x):
    return (x - 3)**2

언덕오르기 탐색 (Hill Climbing)

import random

def hill_climbing(objective_function, start_x, step_size=0.1, max_iterations=100):
    current_x = start_x
    current_value = objective_function(current_x)

    for i in range(max_iterations):
        # 현재 위치 주변의 두 점을 확인
        neighbors = [current_x + step_size, current_x - step_size]

        # 이웃 중 더 나은(값이 더 작은) 점을 선택
        next_x = min(neighbors, key=objective_function)
        next_value = objective_function(next_x)

        print(f"Iteration {i}: x = {current_x:.5f}, f(x) = {current_value:.5f}")

        # 더 이상 개선이 없으면 멈춤
        if next_value >= current_value:
            break

        current_x, current_value = next_x, next_value

    print(f"최적해 추정: x = {current_x}, 최소값 = {current_value}")
    return current_x

# 실행
hill_climbing(objective_function, start_x=random.uniform(-10, 10))

설명

• 현재 위치에서 출발해서, 이웃 중 더 나은 방향으로만 이동
• f(x)가 작아지는 방향(오르막)을 선택하고, 나빠지면 중단
• 단점: 지역 최솟값에 빠질 수 있음

모의 담금질 (Simulated Annealing)

import math

def simulated_annealing(objective_function, start_x, initial_temp=100.0, cooling_rate=0.95, max_iterations=1000):
    current_x = start_x
    current_value = objective_function(current_x)
    temperature = initial_temp

    for i in range(max_iterations):
        # 온도가 너무 낮아지면 중단
        if temperature < 1e-6:
            break

        # 근처의 랜덤한 이웃 선택
        new_x = current_x + random.uniform(-1, 1)
        new_value = objective_function(new_x)

        # 차이 계산
        delta = new_value - current_value

        # 개선되었거나, 확률적으로 허용하는 경우 이동
        if delta < 0 or random.random() < math.exp(-delta / temperature):
            current_x = new_x
            current_value = new_value

        print(f"Iteration {i}: x = {current_x:.5f}, f(x) = {current_value:.5f}, T = {temperature:.5f}")

        # 온도 감소
        temperature *= cooling_rate

    print(f"최적해 추정: x = {current_x}, 최소값 = {current_value}")
    return current_x

# 실행
simulated_annealing(objective_function, start_x=random.uniform(-10, 10))

설명

• 언덕오르기와 달리, 나쁜 방향으로도 확률적으로 이동함
• 시간이 지나면서 확률이 줄어들어 전역 최솟값에 수렴하는 방식
• e^(-delta/T) 확률로 나쁜 해도 수용

A* 알고리즘 (A-Star Search)

import heapq

# A*에서 사용할 노드 정의 (단순화된 x값만 있음)
class Node:
    def __init__(self, x, g):
        self.x = x          # 현재 상태 (x값)
        self.g = g          # 시작점에서 현재까지의 비용 (실제 비용)
        self.h = (x - 3)**2 # 목표까지의 예측 비용
        self.f = self.g + self.h  # 평가함수 f(x) = g(x) + h(x)

    def __lt__(self, other):
        return self.f < other.f  # 우선순위 비교

def astar_search(start_x, goal_range=0.01):
    open_list = []
    heapq.heappush(open_list, Node(start_x, g=0))
    visited = set()

    while open_list:
        current = heapq.heappop(open_list)

        print(f"x = {current.x:.5f}, f(x) = {current.f:.5f}, g = {current.g:.5f}, h = {current.h:.5f}")

        # 목표에 도달했는지 검사
        if abs(current.x - 3) <= goal_range:
            print(f"최적해 도달: x = {current.x}, 최소값 = {objective_function(current.x)}")
            return current.x

        visited.add(round(current.x, 5))

        # 이웃 생성 (양옆으로 조금씩 이동)
        for dx in [-0.1, 0.1]:
            neighbor_x = current.x + dx
            if round(neighbor_x, 5) in visited:
                continue
            heapq.heappush(open_list, Node(neighbor_x, g=current.g + abs(dx)))

    print("해를 찾지 못함")
    return None

# 실행
astar_search(start_x=random.uniform(-10, 10))

설명

• f(n) = g(n) + h(n) 으로 평가함수 구성
  - g(n): 현재까지 이동한 거리
  - h(n): 목표까지 얼마나 남았는지 예측
• f(n)이 가장 작은 노드를 먼저 선택해서 탐색
• h(n)이 정확할수록 탐색 성능이 좋아짐