알고리즘 용어

1. 알고리즘 용어

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

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