알고리즘 용어

1. 알고리즘 용어

  ㅇ 상태 공간 트리 (State Space Tree)
     - 문제 해결 과정 중 각각의 상태를 하나의 노드로써 나타낸 트리
        . 문제의 해를 만들어 가는 공간을 트리 형태로 나타내거나,
        . 해들을 나타낸 트리 공간에서 적절한 해를 탐색하게됨
     - 상태로써 노드의 표현
        . 루트 노드 : 출발점
        . 내부 노드 : 부분 후보 해
           .. 문제 풀이 과정 중의 진행 상태
        . 리프 노드 : 후보 해
           .. 결국, 가능한 모든 후보 해들을 리프 노드로써 갖게됨
        . 루트 노드 ~ 리프 노드 경로 : 하나의 후보 해를 만들어가는 과정
     - 해들의 공간에서, 적절한 해를 탐색하는 알고리즘 例)
        . 백트래킹, 한정분기법, A* 알고리즘 등

  ㅇ 외판원 문제 (Traveling Salesman Problem, TSP)
     - 모든 도시들을, 단 한 번씩 만 방문하고, 원래 시작점으로 돌아오는, 최소 비용의 이동 순서
     - 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예
     - NP 문제에 속함
     - 종류 : 대칭 TSP (양방향 동일 길이를 갖는 간선), 비대칭 TSP

  ㅇ 해밀토니안 사이클, 해밀턴 사이클 (Hamiltonian Cycle)
     - 그래프에서, 모든 정점을 순회하고 돌아올 수 있는 사이클
        . 출발점(도착점) 만 제외하고, 나머지 모든 정점들을 1번씩 만 방문하는 사이클 
     - 例) 완전 그래프(모든 정점끼리 연결된 그래프)에서, 
        . 해밀토니안 사이클이 무수히 많이 존재하나,
        . TSP 문제는, 그 중 가장 짧은 것을 찾는 것임