Steiner Tree

Steiner Tree — 슈타이너 트리

정의

주어진 노드들을 최소 비용으로 연결하는 부분 트리를 찾는 그래프 이론의 고전 알고리즘. G-Retriever에서 거대한 정보 그래프에서 가장 가치있는 핵심 정보만 효율적으로 추출하는 핵심 기술.

개념 이해

피자 배달 비유

상황:

• 최고의 피자를 만들어야 함
• 여러 재료 가게가 도시 곳곳에 산재

해결법:

1. 최고 재료를 파는 가게들만 선택
2. 신선한 재료를 파는 가게들만 방문
3. 최단 경로로 쏙쏙 골라서 방문
4. 쓸데없는 가게는 무시

G-Retriever에서의 적용

정보 검색 과정

거대한 텍스트 그래프
     ↓
Steiner Tree 알고리즘 적용
     ↓
가장 가치있는 정보만 추출
+ 최단 경로 연결
     ↓
효율적이고 정확한 사실 선택
     ↓
이를 기반으로만 답변 생성

핵심 특징

효율성

• 전체가 아닌 핵심만
• 최단 경로 연결
• 계산 비용 최소화

정확성

• 가장 관련 있는 정보 선택
• 쓸데없는 정보 제외
• 환각 방지

실제 효과

측면	효과
성능	기존 방법 압도
확장성	대규모 그래프 처리
신뢰성	환각 현상 차단

---

출처: AI인터시스브랜드 Video 19 수학: 그래프 이론의 최적화 알고리즘