휴리스틱

import heapq
from typing import Callable, Optional
import random
import math

# 1. A* 알고리즘 - 휴리스틱 함수를 사용한 최단 경로
def a_star_search(
    start: tuple,
    goal: tuple,
    heuristic: Callable[[tuple, tuple], float],
    get_neighbors: Callable[[tuple], list],
    cost: Callable[[tuple, tuple], float] = lambda a, b: 1
):
    """A* 탐색 알고리즘 - h(n) 휴리스틱으로 탐색 효율화"""
    open_set = [(0, start)]  # (f_score, node)
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

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

        if current == goal:
            # 경로 복원
            path = [current]
            while current in came_from:
                current = came_from[current]
                path.append(current)
            return path[::-1]

        for neighbor in get_neighbors(current):
            tentative_g = g_score[current] + cost(current, neighbor)

            if neighbor not in g_score or tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None  # 경로 없음

# 일반적인 휴리스틱 함수들
def manhattan_distance(a: tuple, b: tuple) -> float:
    """맨해튼 거리 휴리스틱 (그리드용)"""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def euclidean_distance(a: tuple, b: tuple) -> float:
    """유클리드 거리 휴리스틱"""
    return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

# 2. 탐욕 알고리즘 - 작업 스케줄링 휴리스틱
def greedy_job_scheduling(jobs: list[tuple[int, int, int]]) -> list[int]:
    """
    작업 스케줄링: (시작시간, 종료시간, 가치)
    휴리스틱: 가장 빨리 끝나는 작업 먼저 (EDF)
    """
    # 종료 시간 기준 정렬 (EDF 휴리스틱)
    sorted_jobs = sorted(enumerate(jobs), key=lambda x: x[1][1])

    selected = []
    last_end = 0

    for idx, (start, end, value) in sorted_jobs:
        if start >= last_end:
            selected.append(idx)
            last_end = end

    return selected

# 3. 시뮬레이티드 어닐링 - 메타휴리스틱
def simulated_annealing(
    initial_state,
    objective: Callable,
    neighbor: Callable,
    initial_temp: float = 1000,
    cooling_rate: float = 0.995,
    min_temp: float = 1
):
    """
    시뮬레이티드 어닐링 - 지역 최적해 탈출 휴리스틱
    """
    current = initial_state
    current_score = objective(current)
    best = current
    best_score = current_score
    temperature = initial_temp

    while temperature > min_temp:
        # 이웃 해 생성
        candidate = neighbor(current)
        candidate_score = objective(candidate)

        # 수락 확률 계산 (휴리스틱)
        delta = candidate_score - current_score

        if delta < 0 or random.random() < math.exp(-delta / temperature):
            current = candidate
            current_score = candidate_score

            if current_score < best_score:
                best = current
                best_score = current_score

        temperature *= cooling_rate

    return best, best_score

# 4. 빔 서치 - LLM 디코딩 휴리스틱
def beam_search_decode(
    model_predict: Callable,  # 다음 토큰 확률 예측 함수
    start_token: int,
    end_token: int,
    beam_width: int = 5,  # 휴리스틱: 탐색 너비
    max_length: int = 50
) -> list[int]:
    """빔 서치 - 확률 기반 탐색 휴리스틱"""
    # (누적 log 확률, 시퀀스)
    beams = [(0.0, [start_token])]

    for _ in range(max_length):
        candidates = []

        for score, sequence in beams:
            if sequence[-1] == end_token:
                candidates.append((score, sequence))
                continue

            # 다음 토큰 확률 예측 (실제로는 모델 호출)
            next_probs = model_predict(sequence)

            # 상위 k개만 고려 (휴리스틱)
            top_k = sorted(enumerate(next_probs), key=lambda x: -x[1])[:beam_width]

            for token, prob in top_k:
                new_score = score + math.log(prob + 1e-10)
                candidates.append((new_score, sequence + [token]))

        # 상위 빔만 유지 (휴리스틱)
        beams = sorted(candidates, key=lambda x: -x[0])[:beam_width]

        if all(seq[-1] == end_token for _, seq in beams):
            break

    return beams[0][1]  # 최고 점수 시퀀스

# 5. 규칙 기반 휴리스틱 - 이상 탐지
class AnomalyDetectionHeuristics:
    """통계 기반 이상 탐지 휴리스틱"""

    @staticmethod
    def three_sigma_rule(data: list[float], value: float) -> bool:
        """3-시그마 규칙: 평균에서 3 표준편차 이상이면 이상"""
        mean = sum(data) / len(data)
        std = (sum((x - mean)**2 for x in data) / len(data)) ** 0.5
        return abs(value - mean) > 3 * std

    @staticmethod
    def iqr_rule(data: list[float], value: float) -> bool:
        """IQR 규칙: Q1 - 1.5*IQR 미만 또는 Q3 + 1.5*IQR 초과면 이상"""
        sorted_data = sorted(data)
        n = len(sorted_data)
        q1 = sorted_data[n // 4]
        q3 = sorted_data[3 * n // 4]
        iqr = q3 - q1
        return value < q1 - 1.5 * iqr or value > q3 + 1.5 * iqr

    @staticmethod
    def sudden_change(current: float, previous: float, threshold: float = 0.5) -> bool:
        """급격한 변화 감지: 이전 값 대비 threshold% 이상 변화"""
        if previous == 0:
            return abs(current) > threshold
        return abs((current - previous) / previous) > threshold

# 사용 예시
if __name__ == "__main__":
    # A* 경로 탐색
    print("=== A* 경로 탐색 ===")
    def get_grid_neighbors(pos):
        x, y = pos
        return [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]

    path = a_star_search(
        start=(0, 0),
        goal=(5, 5),
        heuristic=manhattan_distance,
        get_neighbors=get_grid_neighbors
    )
    print(f"최단 경로: {path}")

    # 작업 스케줄링
    print("\n=== 탐욕 작업 스케줄링 ===")
    jobs = [(0, 3, 10), (2, 5, 15), (4, 7, 12), (6, 9, 20)]
    selected = greedy_job_scheduling(jobs)
    print(f"선택된 작업 인덱스: {selected}")

    # 이상 탐지
    print("\n=== 이상 탐지 휴리스틱 ===")
    data = [10, 12, 11, 13, 10, 12, 11, 100]  # 100이 이상치
    detector = AnomalyDetectionHeuristics()
    print(f"3-시그마 이상치: {detector.three_sigma_rule(data[:-1], 100)}")
    print(f"IQR 이상치: {detector.iqr_rule(data[:-1], 100)}")