A* 알고리즘 및 Heuristics 기반 탐색 공간 최적화로 연산 복잡도 획기적 감소

Context

BFS, DFS와 같은 Blind Search 방식은 탐색 공간 확장에 따라 지수함수적 비용이 발생하는 한계 존재. 단순 탐색만으로는 대규모 상태 공간(State Space)에서 실시간 의사결정 및 최적 경로 탐색이 불가능한 구조적 병목 발생.

Technical Solution

• Heuristics 도입을 통한 Informed Search 구현으로 불필요한 경로를 사전에 제거하여 탐색 효율성 증대
• g(n)(실제 비용)과 h(n)(추정 비용)을 결합한 f(n) = g(n) + h(n) 함수 기반의 A* 알고리즘 설계
• Admissibility 조건을 만족하는 Heuristic 설계를 통해 최적해 보장 및 오버헤드 최소화
• 단순 일치 여부만 판단하는 Misplaced Tiles 방식에서 거리 기반의 Manhattan Distance로 Heuristic 정밀도 개선
• Symbolic AI의 논리적 투명성과 Generative AI의 유연성을 결합한 Hybrid Architecture 지향
• Constraint Satisfaction Problems(CSP) 접근법을 통한 제약 조건 기반의 효율적 값 할당 구조 적용