지난번 그래프 정리 글에서 그래프에 관련한 기본적인 이론과 활용 예시 들을 간단하게 살펴보았고,
ref : throwexception.tistory.com/1185
이번에는 그래프의 역사적인 배경과 다양한 문제들, 그래프 탐색 등에 대해 알아보자.
1. 그래프 이론의 시작 : 쾨니흐스베르크의 다리
- 오일러가 1736년에 쓴 쾨니히스베르크의 다리 문제에 대한 논문에서부터 시작됨
- 질문 : 프로이센 쾨니히스베르크에는 다리가 7개가 있는데, 모든 다리를 한 번씩만 건너서 모두 지나갈수 있을까?
- 아래의 그림은 쾨니히스베르크의 지도
2. 오일러 경로 Eulerian Path
- 오일러는 강으로 나눠지는 육지들을 A ~ D라고 이름을 주고, 각 다리마다 a ~ g라는 이름으로
- 여기서 A ~ D는 노드/정점이며, a ~ g 에지/간선이 된다.
- 아래의 그림은 오일러가 1736년 발표한 논문에서의 다리 스캐치
- 아래의 그림은 쾨니히스베르크의 다리를 그래프로 나타낸 결과물
- 오일러는 정점/노드가 짝수개의 차수를 갖는다면 모든 다리를 한번씩 건너는게 가능하다고 정리
* 오일러 경로 : 유한 그래프 Finite Graph의 모든 에지/간선를 한번씩 통과하는 경로(한붓 그리기)
=> 쾨니히스베르크의 다리는 정점 갯수가 짝수 개의 차수가 아니므로 오일러 경로가 아니다/한붓 그리기가 안된다.
3. 해밀턴 경로 Hamilton path
3.1 해밀턴 경로 개요
- 그래프이론에서 오일러 경로와 비슷한 경로로 해밀턴 경로가 있다.
- 해밀턴 경로 : 모든 정점을 한번씩 방문하는 그래프 경로
* 오일러 경로는 모든 에지를 한번씩 방문한다면, 해밀턴 경로는 모든 정점을 한번씩 방문해야함.
- 해밀턴 경로 찾기 -> 최적 알고리즘이 없는 NP-완전/NP-complete 문제
ref : ko.wikipedia.org/wiki/%ED%95%B4%EB%B0%80%ED%84%B4_%EA%B2%BD%EB%A1%9C
* 오일러경로와 해밀턴 경로의 비교
* 입체 도형의 해밀턴 경로들
3.2 해밀턴 순환
- 해밀턴 순환 출발점으로 돌아오는 해밀턴 경로
3.3 외판원 문제 Travelling Salesman Problem : TSP
- 각 도시를 방문하고 최단 경로를 찾는 문제
- NP-난해에 속하는 문제로, 계산 복잡도 이론에서 최적의 해를 구하기 힘든 문제의 대표적인 예시가 된다.
* 다항식 시간 내 풀수 있는 알고리즘이 없으므로 모의 담금질이나 유전 알고리즘으로 근사해를 구한다!
ref : ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C
- Question : 도시가 20개인 경우, 최적의 경로를 찾으러면 얼마나 많은 경로를 다녀야 할까?
=> Answer : 20! = 2,432,902,008,176,640,000 이 중에서 가장 짧은 경로를 찾기는 힘들다.
4. 복잡도와 문제들
4.1 NP 복잡도
- 비결정론적 튜링 기계 Non Deterministic Turing Machine : NTM으로 다항 시간안에 풀수 있는 판별 문제의 집합
- NP는 Non deterministic Polynomial time의 약어
- NP에 속하는 문제들은 결정론적 튜링 기계로 다항 시간에 검증이 가능하다.
ref : ko.wikipedia.org/wiki/NP_(%EB%B3%B5%EC%9E%A1%EB%8F%84)
4.2 계산 복잡도 이론 Computational Complexity theory
- 컴퓨터 과학의 계산 이론의 한 분야로 알고리즘을 복잡도에 따라 분류한 문제의 모임을 구성하는 방법을 다룸
- 알고리즘 수행을 (실제 컴퓨터로도 가능하나) 튜링 기계를 이용한 방법을 사용
- 복잡도의 기준 : 시간 복잡도(알고리즘 소요 시간)와 공간 복잡도(메모리 등 자원 사용량)
=> 복잡도에는 어떤게 있을까?
4.3 복잡도 종류
- 계산 복잡도에 따라 문제를 분류한 것
- 일반적인 정의 : 추상 기계 abstract machine이 O(f(n)) 만큼의 자원 R을 이용하여 풀수 있는 문제의 종류
- 복잡도 종류의 예시
example 1) NP : 확률적 튜링기계가 다항 시간에 풀 수 있는 판정 문제의 집합
example 2) PSPACE : 결정론적 튜링 기계가 다항 공간에서 풀 수 있는 판정 문제의 집합
ref : ko.wikipedia.org/wiki/%EB%B3%B5%EC%9E%A1%EB%8F%84_%EC%A2%85%EB%A5%98
=> 추상 기계, 튜링 기계, 판정 문제, 다항 시간, 다항 공간란 무엇일까?
4.4 추상 기계 abstract machine
- 컴퓨터 하드웨어나 소프트웨어의 이상적인 모형, 추상컴퓨터라고도 부름
- 계산 이론에서 추상 기계를 사고 실험에서 사용해, 계산 가능성이나 알고리즘 복잡도 추정
- 추상 기계를 통해 실제 컴퓨터를 만들지 않더라도 실행 시간이나 메모리 등 자원이 얼마나 필요한지 예측 가능
* 사고실험 though experiment : 가상 시나리오가 어떻게 동작하는지 생각하는 방법. 경험적 방법(관찰, 실험)과 반대됨
ref : ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EA%B8%B0%EA%B3%84
- 아래는 사고 실험의 예시. 이발사는 누구를 면도해야 할까?
4.5 튜링 기계 Turing Machine
- 수학/이론 전산학에서의 튜링 머신 :계산을 할수 있는 기계를 대표하는 가상의 장치, 수학적 모형
- 1936년 튜링은 automatic의 a자를 따서 a-기계라는 이름을 붙였으나 창시자의 엘런 튜링의 이름을따 튜링 기계가 됨.
- 튜링 기계의 구성 : 무한한 길이의 테이프(저장공간)과 테이프에 정보를 쓰고 읽을 수 있는 기계, 그리고 어떻게 값을 줄지 기록하는 상태, 행동표로 구성
* 실제 컴퓨터는 CPU, GPU로 정보를 처리하고, 주/보조 기억장치로 정보를 저장
=> 튜링 머신은 실제 컴퓨터를 대신하여 사고 실험에 사용하기 위한 가상의 수학적 모형/장치
- 튜링이 말하는 튜링 머신의 정의
"무한한 저장공간은 무한한 길이의 테이프로 나타나는데 이 테이프는 하나의 기호를 인쇄할 수 있는 크기의 정사각형들로 쪼개져있다. 언제든지 기계속에는 하나의 기호가 들어가있고 이를 "읽힌 기호"라고 한다. 이 기계는 "읽힌 기호"를 바꿀 수 있는데 그 기계의 행동은 오직 읽힌 기호만이 결정한다. 테이프는 앞뒤로 움직일 수 있어서 모든 기호들은 적어도 한번씩은 기계에게 읽힐 것이다"
ref : ko.wikipedia.org/wiki/%ED%8A%9C%EB%A7%81_%EA%B8%B0%EA%B3%84
- 아래는 세 정수를 다루는 어셈블리 코드
1. EAX 레지스터(위치)에 10000h를 쓰기
2. EAX 레지스터(위치)의 값과 40000h를 더하고 쓰기
3. EAX 레지스터(위치)의 값과 20000h를 빼고 쓰기
4. 모든 레지스터를 호출
4.6 결정 문제/판정 문제 Decision Problem
- 계산이론에서의 판정 문제 : 형식 체계에서 예-아니오로 답이 있는 질문
- example 1 : 두 수 x, y가 있을때 y는 x로 나누어 떨어지는가?
- 결정 문제와 알고리즘 : 판별 문제를 푸는데 사용되는 방법이 알고리즘.
- 결정 문제를 풀 수 있는 알고리즘이 존재한다. -> 결정 가능
- 결정 문제를 풀 수 있는 알고리즘이 존재하지 않는다. -> 결정 불가능
* 결정가능성 decidability : 해답을 내놓는 기계적인 절차/알고리즘이 존재하는 성질
ref : ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95_%EB%AC%B8%EC%A0%9C
ps. 판정 문제는 예 혹은 아니오라는 답이 존재하는 질문인데, 외판원 문제의 경우 경로같은 정답이 나온다. 복잡도 종류에서 말하는 판정 가능이란 예/아니오라는 범위를 넘어서 해답이 존재하는 문제를 말하는것 같다.
* 계산 이론에서 결정 Decision과 결정론적 deterministic이란 단어는 한글로 동일하게 결정이라 부르나 구분을 해야되는것으로 보인다.
4.7 결정론적 알고리즘 deterministic algorithm
- 예측한 그대로, 생각한 그대로 동작하는 알고리즘
- 대표적인 예시로 수학에서 사용하는 함수
- 한계 : 결정론적 알고리즘을 찾기 힘든 문제가 존재한다
-> 예시 : NP-완전(실생활에 중요한 많은 문제들이 NP-완전. ex : TSP)
=> 비결정론적 알고리즘이 필요하다!
4.8 비결정론적 알고리즘 non deterministic algorithm 만들기
- 입력 이외의 외부 상태를 알고리즘에 적용
- 알고리즘이 시간에 민감하게 영향을 받도록 동작.
- 하드웨어의 오류를 반영하여 알고리즘 진행을 예상할 수 없게 한다.
=> 예상한 대로 정확하게 동작하지 않는 알고리즘
- 비결정론적 알고리즘의 한계 : 비결정론적 튜링 기계를 이용하면 쉽게 풀수 있으나, 실제 구현하지 못함.
=> NP-완전 문제들의 근사해 approxminate solution이나 특이해를 구하는게 한계
ref : ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95%EB%A1%A0%EC%A0%81_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
4,9 비결정론적 튜링 기계 Non deterministic Turing Machine(NTM)
- 튜링 머신에서 움직일수 있는 상태의 개수가 하나였던과 달리 움직일 수 있는 상태 갯수가 하나로 정히지지 않은 머신
- 이동 가능한 상태가 여러개 되거나 아예 없을 수 있음.
=> 기존의 컴퓨터는 쓰레드나 멀티프로세싱 등 병렬 처리 기법이 존재하지만, 모든 CPU의 연산들은 기계어까지 내려가서보면 병렬로 동작하는게 아니라 순차적으로 연산되니. 아예 병렬 연산이 가능한 기계를 말하는 것으로 보임.
4.9 다항 시간 polynomial time과 복잡도 클래스
- 다항 시간 : T(n) = O(n^k)와 같이 다항 표현의 상한을 가지고 수행되는 알고리즘은 다항 시간을 가진다.
- P: 다항 시간동안 결정적 튜링 머신에서 해결할 수 있는 결정 문제의 복잡도 클래스
- NP: 다항 시간동안 비결정적 튜링 머신에서 해결할 수 있는 결정 문제의 복잡도 클래스
- ZPP: 다항 시간동안 확률적 튜링 머신에서 0의 에러확률로 해결할 수 있는 결정 문제의 복잡도 클래스
- RP: 다항 시간동안 확률적 튜링 머신에서 단방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
- BPP: 다항 시간동안 확률적 튜링 머신에서 양방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
- BQP: 다항 시간 동안 양자 튜링 머신에서 양방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
ref : ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
=> P 문제 : 다항 시간동안 결정론적 튜링 머신으로 풀 수 있는 문제. (일반적인 알고리즘 테스트 문제들)
=> NP 문제 : 다항 시간동안 비결정론적 튜링 머신으로 푸는게 가능한 문제(P 문제를 포함함)
4.10 지금까지 본 내용들
- 계산복잡도 이론 : 알고리즘을 복잡도에 따라 어떻게 분류할지 연구하는 이론
- 판정 문제 decision problem : 실제로 해답을 찾을 수 있는 문제(해답이 존재하는 문제)
- 사고 실험 : 실제 하드웨어나 소프트웨어 없이 가상의 시나리오로 어떤 결과가 나오는지 다루는 실험.
- 튜링 머신 : 사고 실험에 사용하기 위한 가상의 장치. 실제 컴퓨터로 구현됨.
- 비결정론적 튜링 머신 NTM : 여러 상태를 동시에 처리 가능한 튜링 머신, 병렬 처리 가능한 가상 기계
- 결정론적 알고리즘 : 예측한 대로 동작하는 알고리즘. ex) 수학 함수
- 비결정론적 알고리즘 : 예측한대로 정확히 동작하지 않는 알고리즘. NTM으로 풀기가능 ex)NP-완전
- 다항 시간 알고리즘 : 시간 복잡도가 O(n^k)로 다항식 시간인 알고리즘.
=> 아래의 그림을 참고하여 대표적인 문제들을 살펴보자.
4.11 복잡도 정리
- EXPSPACE : 결정론적 튜링 기계가 O(2^{p(n)}) 공간으로 풀수 있는 판정 문제 집합. p(n)은 n에대한 다항함수
- EXPTIME : 결정론적 튜링 기계가 O(2^{p(n)}) 시간에 풀수 있는 모든 판정 문제 집합. p(n)엔 n에대한 다항함수
- PSPACE : 결정론/비결정론적 튜링기계가 시간에 상관없이, 다항 공간을 써서 풀수 있는 판정 문제 집합
- NP : 비결정론적 튜링기계 NTM으로 다항시간에 풀수 있는 판정 문제 집합.
- NP-HARD : 적어도 모든 NP 문제만큼 어려운 문제들의 집합
* NP는 NTM으로 다항식 시간에 풀수 있는 문제 집합, NP-hard는 NP만큼이나 어려운 문제 집합점에서 다름
* NP-Hard 중에서 NP에 속하지 않은 문제들이 존재.
- NP-Complete : NP-HARD이지만, NP로 바꿀수 있는 문제 집합
- P(PTIME) : 결정론적 튜링 기계로 다항 시간안에 풀수 있는 판정 문제 집합.
4.11. 해밀턴 경로와 외판원 문제를 계산 복집도 이론으로 보기
4.11.1 해밀턴 경로 문제와 외판원 문제의 관계
- 해밀턴 경로 : 한 번만 방문하는 경로
- 해밀턴 순환 : 한 번만 방문하여 출발지로 돌아오는 경로
- 외판원 문제 : 한 번만 방문하여 출발지로 돌아오는 경로 중가장 짧은 분류
=> 해밀턴 경로 > 해밀턴 순환 > 외판원 문제
4.11.2 문제 정의
문제 1. 해밀턴 경로가 존재하는가?
문제 2. 각 도시를 방문하고, 돌아오는 가장 짧은 경로 찾아라(최단거리 해밀턴 순환 찾기)
4.11.3 문제 1번 보기
- 질문 : 해밀턴 경로가 존재하는가?
- 예/아니오로 대답할 수 있는 결정 문제이며, 다항 시간에 검증이 가능한 NP 문제이며, NP-Hard -> NP-완전
4.11.4 문제 2번 보기
- 질문 : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾아라
- 예/아니오로 대답할 수 있는 결정 문제가 아니므로, NP 문제가 아닐 수 있다.
- 증명된 NP-난해 문제이나 NP 문제가 아닐수 있어 NP-완전 문제가아니며, NP-난해
5. 그래프 순회 Graph Traversals, 그래프 탐색 Graph Search
5.1 그래프 탐색 개요
- 그래프 순회/탐색은 그래프가 가지고 있는 정점들을 방문하는 것을 말함.
- 대표적인 그래프 탐색 방법으로 깊이 우선 탐색 Depth First Search DFS와 너비 우선 탐색 Breadth First Search BFS
* 위와 같은 기본적인 그래프 탐색 알고리즘에서 최적 탐색 방법과 경험적 탐색 방법을 활용하여 개선된 방법들이 존재
| 임의 경로 탐색 | 최적 경로 탐색 | |
| 맹목적 탐색 blind search | 깊이 우선 탐색 Depth First Search 너비 우선 탐색 Breadth First Search |
균일 비용 탐색 Uniform Cost Search |
| 경험적 탐색 heuristic search | 언덕 오르기 탐색 hill Climbing Search 최적 우선 탐색 |
다익스트라 알고리즘 Dijkstra algorithm A* 알고리즘 Astar Algorithm |
5.2 깊이 우선 탐색과 너비 우선 탐색
- DFS는 왼쪽 깊이 방향을 우선으로 탐색
- BFS는 너비 방향을 우선으로 탐색
5.3 백트래킹 BackTracking
- 탐색을 하다가 진행 할 수 없을때(후보 경로를 포기) 왔던 길을 되돌아서 탐색을 진행하는 것에서 유례
- DFS 같은 방식으로 탐색하는 모든 방법을 의미, 주로 재귀로 구현하며 기본적으로 DFS에 속함.
- 최적의 경우 적은 시행착오로 목표 도달하나 최악의 경우 모든 경우를 고려해야함
* 브루트 포스와 다른 점은 가능성이 없는 경우 후보를 즉시 포기해서 되돌아간다는 점에서 개선됨.(가지치기)
ref : en.wikipedia.org/wiki/Backtracking
5.4 백트래킹과 제약충족 문제 Constraint Satisfaction Problems(CSP)
- 제약 충족 문제 : 제약 조건 Constraints를 충족하는 상태 States를 찾아내는 수학 문제.
- CSP의 예시 : 스도쿠, 십자말풀이, 퍼즐 문제, 문자열 파싱 등
- 제약 충족 문제를 푸는데 (가지치기로 최적화) 백트래킹이 필수적임.
ref : en.wikipedia.org/wiki/Constraint_satisfaction_problem
'수학 > 알고리즘' 카테고리의 다른 글
| 슬라이딩 윈도우 (0) | 2021.04.28 |
|---|---|
| 퀵 정렬 quick sort (0) | 2021.04.07 |
| 그래프 정리 1 (0) | 2021.02.23 |
| [리트코드 문제 풀기] 연결 리스트 (0) | 2021.01.27 |
| [리트코드 문제 풀기] 배열 (0) | 2021.01.20 |