언덕 오르기 탐색 (Hill Climbing Search)

# Hill Climbing Search & Random-Restart Implementation in Python

import random

def hill_climbing(problem):
    """
    표준 가파른 언덕 오르기 (Steepest-Ascent Hill Climbing)
    현재 상태의 이웃 중 목적 함수 값이 가장 높은 노드로 계속 이동
    """
    current = problem.initial_state()
    
    while True:
        neighbors = problem.get_neighbors(current)
        if not neighbors:
            break
            
        # 이웃 중 가장 높은 평가 값을 가진 최선 노드 선택
        best_neighbor = max(neighbors, key=lambda s: problem.value(s))
        
        # 최선의 이웃도 현재보다 고도가 높지 않으면 지역 최대치(Local Max) 도달로 종료
        if problem.value(best_neighbor) <= problem.value(current):
            break
            
        current = best_neighbor  # 더 높은 곳으로 한 걸음 전진
        
    return current

def random_restart_hill_climbing(problem, max_restarts=100):
    """
    무작위 재시작 언덕 오르기: 여러 임의의 시작점에서 시도하여 최고 결과 선택
    """
    best_overall = None
    best_val = -float('inf')
    
    for _ in range(max_restarts):
        candidate = hill_climbing(problem)
        cand_val = problem.value(candidate)
        
        if cand_val > best_val:
            best_val = cand_val
            best_overall = candidate
            
        # 완벽한 전역 최적해를 달성했으면 조기 탈출
        if problem.is_optimal(candidate):
            break
            
    return best_overall