[상태공간 트리의 탐색 - 0] 목차

상태공간 트리의 탐색

> 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리이다.

!

> 상태공간 트리로 뭘 할수 있을까

• TSP (외판원 문제) 그래프
• 4-Queen 문제
• SumOfSubset(부분 집합 합 문제)
• GraphColoring(그래프 색칠)
• Knapsack 냅섹

> 뭐랑 관련되어있나?

• DFS(재귀 스택)
  • 트리나 그래프에서 한 루트로 탐색
  • 백트래킹과 관련
  • 재귀는 스텍오버플로 조심
• BFS(queue)
  • 트리나 그래프에서 한 루트로 탐색
  • 최선 우선 탐색도 있다
  • 분기한정과 관련
• 백트래킹(Backtracking)
• 분기 한정(Branch and Bound)

---

목차

1. 백트래킹
2. 몬테 카를로 알고리즘
3. 분기한정 (Branch and Bound)
4. Best FS