20220217 APS 응용 백트래킹, 그래프

백트래킹(Back tracking)

• 퇴각검색
• 모든 조합을 시도해서 문제의 해를 찾는다
• 해를 얻을 떄까지 모든 가능성을 시도
• 여러 가지 선택지들이 존재하는 상황에서 하나의 가지를 선택
• 선택이 이루어지면 새로운 선택지들의 집합이 생덤됨
• 이런 선택을 반복하며 최종 상태에 도달
• 보통 재귀 함수로 구현됨
• 상태 공간 트리(State space tree)로 재귀의 깊이를 예측 해야 함

백트래킹 기법

• 어떤 노드의 가능성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 간다
• 유망(promising)
  • 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 있는 경우
• 가지치기(pruning)
  • 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않음
• 백트래킹을 이용한 알고리즘
  1. 상태 공간 트리의 깊이 우선 검색(DFS)을 실시한다.
  2. 각 노드가 유망한지를 점검
  3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가 다른 노드로의 검색을 함

백트래킹과 완전탐색(DFS)과의 차이

• 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 그 경로를 탈출함으로 시도의 획수를 줄임 (Pruning : 가지치기)
• 완전 탐색(DFS)이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단

그래프

• 그래프는 아이템들과 이들 사이의 연결 관계를 표현
• 정점(Vertex) : 그래프의 구성요소로 하나의 연결점
• 간선(Edge) : 두 정점을 연결하는 선
• 차수(Degree) : 정점에 연결된 간선의 수
• 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성
  • V : 정점의 개수, E : 그래프에 포함된 간선의 개수

그래프 유형

• 무향 그래프(Undirected Graph)
• 유향 그래프(Directed Graph)
• 가중치 그래프(Weighted Graph)
• 사이클 없는 방향 그래프(DAG : Directed Acyclic Graph)
• 완전 그래프
  • 정점들에 대해 가능한 모든 간선들을 가진 그래프
• 부분 그래프
  • 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
• 인접(Adjacency)
  • 두 개의 정점에 간선이 존재하면 서로 인접
  • 완전 그래프에 속한 임의의 두 정점들은 서로 인접함

그래프 경로

• 경로 : 어떤 정점 A에서 시작하여 다른 정점 B로 끝나느 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것
• 단순 경로 : 시작정점과 끝 정점을 제외하고 중복된 정점이 없는 경로
• 싸이클(Cycle) : 경로의 시작 정점과 끝 정점이 같음

그래프 표현

• 간선의 정보를 저장하는 방식
• 인접 행렬(Adjacent matrix) : V*V 크기의 2차원 배열을 이용해서 간선 정보를 저장
• 인접 리스트(Adjacent List) : 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장
• 간선 리스트(Edge List) : 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장

인접 행렬

• 두 정점을 연견하는 간선의 유무를 행렬로 표현
• 행 번호와 열 번호는 그래프의 점정에 대응
• 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현 (1대신 가중치를 넣을 수 도 있음)
• 무향 그래프
  • i번째의 행의 합 = i번째 열의 합 = Vi의 차수
• 유향 그래프
  • 행 i의 합 = Vi의 진출 차수
  • 열 i의 합 = Vi의 진입 차수

인접 리스트

• 각 정점에 대한 인접 정점들을 순차적으로 표현
• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장

간선 리스트

• 두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장
• 간선을 표현하는 두 정점의 정보를 나타냄(시작 정점, 끝 정점)