1. 그래프
    1. 개론
      1. 일반적으로 알고 있는 그래프와는 조금 다름
      2. 노드와 에지
        1. 노드 : 중간 지점
        2. 에지 : 노드끼리를 연결하는 길
      3. 광범위한 의미
        1. 하나의 네트워크의 기호적인 표현
          1. 전화
          2. www
          3. 전자 회로
          4. 인공 신경망
    2. 좀 더 형식적인 기술
      1. G = {N, E}
        1. N : 0 ~ (N-1)
        2. E : 3-5 / 19-7
          1. 가중치 존재
          2. 거리
          3. 길의 특성(오르막, 늪 등)
    3. 트리
      1. 비순환인 모든 그래프를 포함하는 그래프의 부분집합
    4. 그래프 밀도
      1. 밀집하거나
      2. 성기거나
    5. 다이그래프
      1. 에지의 방향 존재
      2. 16-6 : 16->6 ( ! 6->16 )
        1. 16 : 근원 노드(source node)
        2. 6 : 목적 노드(destination node)
      3. 무방향 그래프 == 쌍방향 다이그래프
    6. 게임 AI에서의 그래프
      1. 항해 그래프(navgraph)
        1. 게임 에이전트가 방문할 수 있는 게임 환경의 모든 장소와 그 지점들 사이의 모든 연결의 추상화
      2. 종속 그래프(dependency graph)
        1. 여러 빌딩, 물자, 유닛과 선우에 적용될 수 있는 기술들 사이의 종속성을 표현하기 위해 사용
      3. 상태 그래프(state graph)
        1. 시스템이 존재할 수 있는 모든 가능한 상태와 그 상태들 사이의 전환을 표현
        2. 루트 노드
        3. 부모 상태 - 자식 상태
        4. 분기율(branching factor)
          1. 각 부모 노드에서 퍼져 나가는 자식 노드의 평균 개수
        5. 대부분 분기율이 높기 때문에 목표 상태 쪽으로 탐색을 지시해 한 번에 몇 개의 노드만 생성되고 탐색
  2. 그래프 클래스 구현하기
    1. 개론
      1. 표현 자료구조
        1. 인접 행렬(adjacency matrix)
          1. 직관적
          2. 용량 비효율
          3. N의 제곱
        2. 인접 리스트(adjacency list)
          1. 성긴 그래프에 효율적
          2. 공간 낭비 x
          3. N+E
    2. GraphNode Class
      1. 노드가 필요로 하는 최소 정보를 캡슐화
      2. template< class extra_info = void* > class NavGraphNode : public GraphNode
    3. GraphEdge Class
      1. 두 개의 노드 사이의 연결을 나타내기 위해 필요한 기본 정보를 캡슐화
      2. 가중치
        1. 가중치가 동일하다면 그 필드를 생략함으로써 메모리 절약
        2. 가중치가 두 노드 사이의 거리라면 Distance 함수 사용
    4. SparseGraph Class
      1. 노드와 에지에 접근할 수 있게끔
        1. 인텍스 사용
      2. 컨테이너
        1. vector<node_type> NodeVector
        2. list<edge_type> EdgeList
        3. vector<EdgeList> EdgeListVector
  3. 그래프 탐색 알고리즘
    1. 개론
      1. 탐색 알고리즘이 하는 일
        1. 그래프의 모든 노드 방문
        2. 두 노드 사이의 어떠한 경로를 찾음
        3. 두 노드 사이의 최적 경로를 찾음
    2. 무정보 그래프 탐색
      1. 에지 비용에 대한 언급 없이 그래프 탐색
      2. 깊이 우선 탐색
        1. 모든 노드와 에지가 방문될 것임을 보장
        2. 알고리즘 구현
          1. 멤버
          2. m_Visited : unvisited
          3. 방문된 모든 노드들의 인덱스 기록
          4. m_Route : no_parent_assigned
          5. 목표까지의 경로 보유
          6. std::Stack 사용
          7. 순서
          8. 생성자 -> Search()
          9. std::stack<const Edge*> stack;
          10. Edge Dummy();
          11. stack.push(&Dummy);
          12. while(!stack.empty())
          13. const Edge* Next = stack.top()
          14. stack.pop()
          15. m_Route[Next->To] = Next->From()
          16. m_Visited[Next->To()] = visited
          17. if(Next->To() == m_iTarget) return true;
          18. for( ConstEdgeItr )
          19. if(m_Visited[pE->To()] == unvisited) stack.push(pE);
          20. GetPathToTarget() 에서 목표까지의 경로 반환
      3. 너비 우선 탐색
        1. 가장 적은 에지를 방문하는 경로를 보장
        2. 멤버
          1. m_Visited : unvisited
          2. 방문된 모든 노드들의 인덱스 기록
          3. m_Route : no_parent_assigned
          4. 목표까지의 경로 보유
          5. std::queue 사용
        3. 알고리즘 구현
          1. std::queue<const Edge*> Q
          2. const Edge Dummy()
          3. Q.push(&Dummy)
          4. m_Visited[m_iSource] = visited;
          5. while(!Q.empty())
          6. const Edge* Next = Q.front();
          7. Q.pop();
          8. m_Route[Next->To()] = Next->From();
          9. if(Next->To() == m_iTarget) return true;
          10. for(ConstEdgeItr)
          11. if(m_Visited[pE->To()] = visited)
          12. Q.push(pE);
          13. m_Visited[pE->To()] = visited;
    3. 비용 기반 그래프 탐색
      1. 에지 완화(Edge relaxation)
        1. 지금까지 발견된 가장 좋은 경로(BDSF)에 대한 정보 수집
      2. 최단 경로 트리(Shortest Path Tree, SPT)
        1. 어떤 노드에서 근원 노드까지 최단 경로를 나타내는 그래프의 부트리(sub-tree)
      3. Dijkstra Algorithm
        1. 인덱스 우선순위 큐(indexed Priority Queue, iPQ) 사용
          1. 양방향 힙 사용
        2. PQ의 앞에 있는 노드는 근원 노드에 가장 가까운 SPT에 아직 없는 노드라는 것을 보장
        3. 알고리즘 구현
          1. IndexedPriorityQLow<double> pq
          2. pq.Insert(m_iSource)
          3. while(!Q.empty())
          4. int NextClosestNode = pq.Pop()
          5. .....
        4. BFS처럼, Dijkstra 알고리즘은 너무 많은 에지를 검사
      4. A* Algorithm
        1. 특별한 Dijkstra
        2. 휴리스틱(heuristic)
          1. 각 노드에서 목표까지의 비용을 추정해 탐색 속도 개선 가능
          2. 유클리디언(Euclidean) 거리 사용
          3. 노드들 사이의 직선 거리
        3. Dijkstra와의 차이점
          1. 탐색 변경(우선순위 큐)의 노드들의 비용 계산
          2. F = G + H
          3. G : 노드에 이르는 누적 비용
          4. H : 목표까지 거리의 휴리스틱 추정
        4. 구현하기
          1. 휴리스틱을 템플릿 매개변수로 설정
          2. 자체 제작 휴리스틱을 사용하기 쉽게 하기 위해
          3. 에지 완화 땐 Gcsot, PQ엔 Fcost 사용
        5. 맨하탄 거리 휴리스틱
          1. 가로와 세로 방향의 변이의 합
          2. 제곱근이 필요없으므로 유클리디언 휴리스틱보다 빠름