1. 알고리즘 용어
ㅇ 상태 공간 트리 (State Space Tree)
- 문제 해결 과정 중 각각의 상태를 하나의 노드로써 나타낸 트리
. 문제의 해를 만들어 가는 공간을 트리 형태로 나타내거나,
. 해들을 나타낸 트리 공간에서 적절한 해를 탐색하게됨
- 상태로써 노드의 표현
. 루트 노드 : 출발점
. 내부 노드 : 부분 후보 해
.. 문제 풀이 과정 중의 진행 상태
. 리프 노드 : 후보 해
.. 결국, 가능한 모든 후보 해들을 리프 노드로써 갖게됨
. 루트 노드 ~ 리프 노드 경로 : 하나의 후보 해를 만들어가는 과정
- 해들의 공간에서, 적절한 해를 탐색하는 알고리즘 例)
. 백트래킹, 한정분기법, A* 알고리즘 등
ㅇ 외판원 문제 (Traveling Salesman Problem, TSP)
- 모든 도시들을, 단 한 번씩 만 방문하고, 원래 시작점으로 돌아오는, 최소 비용의 이동 순서
- 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예
- NP 문제에 속함
- 종류 : 대칭 TSP (양방향 동일 길이를 갖는 간선), 비대칭 TSP
ㅇ 해밀토니안 사이클, 해밀턴 사이클 (Hamiltonian Cycle)
- 그래프에서, 모든 정점을 순회하고 돌아올 수 있는 사이클
. 출발점(도착점) 만 제외하고, 나머지 모든 정점들을 1번씩 만 방문하는 사이클
- 例) 완전 그래프(모든 정점끼리 연결된 그래프)에서,
. 해밀토니안 사이클이 무수히 많이 존재하나,
. TSP 문제는, 그 중 가장 짧은 것을 찾는 것임