NP-Complete Problem Solver with AI/ML/LLM

AI 기반 접근법을 사용하여 NP-complete 문제를 해결하는 연구 프로젝트입니다.

📋 프로젝트 개요

이 프로젝트는 전통적으로 해결하기 어려운 NP-complete 문제들을 현대 AI 기술로 다루는 방법을 탐구합니다:

• 머신러닝: 강화학습(DQN, PPO), 그래프 신경망(GNN), 지도학습
• LLM: Few-shot 프롬프팅, Chain-of-Thought 추론, LLM 기반 탐색
• 전통적 방법: 탐욕 알고리즘, 유전 알고리즘, 담금질 기법

🎯 지원하는 NP-Complete 문제

1. TSP (Traveling Salesman Problem) - 외판원 문제
2. SAT (Boolean Satisfiability) - 충족 가능성 문제
3. Graph Coloring - 그래프 색칠 문제
4. Knapsack Problem - 배낭 문제
5. Vertex Cover - 정점 덮개 문제

🏗️ 프로젝트 구조

np-complete-program-solver/
├── src/
│   ├── problems/          # NP-complete 문제 정의
│   ├── solvers/           # 다양한 솔버 구현
│   │   ├── traditional/   # 전통적 알고리즘
│   │   ├── ml/            # 머신러닝 기반
│   │   └── llm/           # LLM 기반
│   ├── models/            # ML 모델 정의
│   ├── evaluation/        # 평가 프레임워크
│   └── utils/             # 유틸리티 함수
├── notebooks/             # Jupyter 노트북 예제
├── tests/                 # 단위 테스트
├── docs/                  # 문서
├── examples/              # 사용 예제
├── benchmarks/            # 벤치마크 데이터셋
└── results/               # 실험 결과

🚀 빠른 시작

설치

# 저장소 클론
git clone https://github.com/yourusername/np-complete-program-solver.git
cd np-complete-program-solver

# 가상환경 생성
python -m venv venv
source venv/bin/activate  # Windows: venv\Scripts\activate

# 의존성 설치
pip install -r requirements.txt

기본 사용법

from src.problems.tsp import TSPProblem
from src.solvers.ml.dqn_solver import DQNSolver

# TSP 문제 생성
problem = TSPProblem(num_cities=20)

# DQN 솔버로 해결
solver = DQNSolver()
solution = solver.solve(problem)

print(f"최적 경로: {solution.path}")
print(f"총 거리: {solution.cost}")

📊 접근 방법 비교

1. 전통적 알고리즘

• ✅ 빠른 실행
• ✅ 이해하기 쉬움
• ❌ 최적해 보장 어려움

2. 머신러닝

• ✅ 패턴 학습 가능
• ✅ 대규모 문제에 확장 가능
• ❌ 학습 시간 필요

3. LLM 기반

• ✅ 제로샷/퓨샷 학습
• ✅ 추론 과정 해석 가능
• ❌ API 비용
• ❌ 대규모 문제에 제한

🔬 실험 실행

# TSP 문제에 대한 모든 솔버 비교
python -m src.evaluation.benchmark --problem tsp --size 50

# 특정 솔버로 실험
python -m src.solvers.ml.train_dqn --problem tsp --episodes 1000

# LLM 기반 솔버 테스트
python -m src.solvers.llm.llm_solver --problem sat --model gpt-4

📚 문서

• 아키텍처 설계
• 알고리즘 상세
• API 레퍼런스
• 벤치마크 결과
• 연구 노트

🧪 Jupyter 노트북

• TSP 튜토리얼
• RL 학습 과정
• LLM 프롬프팅
• 결과 시각화

🤝 기여

기여를 환영합니다! Pull Request를 보내주세요.

📄 라이선스

이 프로젝트는 MIT 라이선스 하에 배포됩니다.

📧 연락처

질문이나 제안사항이 있으시면 이슈를 등록해주세요.

🎓 참고문헌

1. Reinforcement Learning for Combinatorial Optimization (Bello et al., 2016)
2. Attention, Learn to Solve Routing Problems! (Kool et al., 2019)
3. Learning to Solve NP-Complete Problems (Nowak et al., 2017)
4. Large Language Models as Optimizers (Yang et al., 2023)