[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다.외판원 문제는 다음과 같이 설명할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.
그림과 같이 각 도시의 위치가 표시된 미국 지도가 있다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까?만약 도시가 20개라고 할 때 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 [math(20!)]다. 이 값은 얼마나 될까? [math(20!=2,432,902,008,176,640,000)]이다. 그러니까 약 240경 번의 경로를 다녀봐야 가장 짧은 경로를 찾을 수 있다. 문제는 단순하고 인간의 눈으로 보이는 답도 존재하지만, 수학적으로 진짜 최소경로가 증명되는 정답을 찾는 과정은 실로 엄청나다. 이 경우의 수를 모두 조회하는 것은 브루트 포스 알고리즘인데 굉장히 비효율적이고, 동적 계획법등 별도의 최적화 알고리즘을 통해 문제를 풀어야 연산량과 풀이시간이 줄어든다.
2. 문제의 정의
외판원 순회 문제는 다음과 같이 그래프 이론의 용어로 엄밀하게 정의할 수 있다.주어진 완전 그래프 G=(V, E)가, 연결되어 있고(connected) 가중치가 있는(weighted) 완전한(complete) 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을 방문하고 원래의 출발 정점으로 되돌아오는 순환 경로들 중에서 가중치의 합이 최소가 되는 순환 경로를 찾아라.
3. 문제의 해결
외판원 순회 문제는 NP-완전 집합에 속하는 문제라는 것이 증명되었다. 다항 시간에 이 문제를 해결할 수 있는 알고리즘을 아무도 찾지 못했으며, 그렇다고 다항 시간에 문제를 해결하지 못한다는 것도 아무도 증명하지 못했다. 만약 이 문제를 다항 시간에 해결할 수 있는 알고리즘을 발견하거나, 다항 시간에 해결이 불가능함을 명확히 증명한다면 100만 달러의 상금을 받을 수 있다.3.1. 동적 계획법으로 풀기
외판원 순회 문제의 최적해는 동적 계획법으로 지수 시간에 풀 수 있다. 다음은 동적 계획으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.#!syntax python
def travel (W):
n = len(W) - 1
size = 2 ** (n - 1)
D = [[0] * size for _ in range(n + 1)]
P = [[0] * size for _ in range(n + 1)]
for i in range(2, n + 1):
D[i][0] = W[i][1]
for k in range(1, n - 1):
for A in range(1, size):
if (count(A, n) == k):
for i in range(2, n + 1):
if (not isIn(i, A)):
D[i][A], P[i][A] = minimum(W, D, i, A)
A = size - 1
D[1][A], P[1][A] = minimum(W, D, 1, A)
return D, P
def minimum (W, D, i, A):
minValue = INF
minJ = 1
n = len(W) - 1
for j in range(2, n + 1):
if (isIn(j, A)):
m = W[i][j] + D[j][diff(A, j)]
if (minValue > m):
minValue = m
minJ = j
return minValue, minJ
3.2. 분기 한정으로 풀기
외판원 순회 문제의 최적해는 분기 한정(Branch-and-Bound)으로 지수 시간에 풀 수 있다. 다음은 분기 한정으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.#!syntax python
def travel2 (W):
global minlength, opttour
n = len(W) - 1
PQ = PriorityQueue()
v = SSTNode(0)
v.path = [1]
v.bound = bound(v, W)
minlength = INF
PQ.put((v.bound, v))
while (not PQ.empty()):
v = PQ.get()[1]
if (v.bound < minlength):
for i in range(2, n + 1):
if (v.contains(i)):
continue
u = SSTNode(v.level + 1)
u.path = v.path[:]
u.path.append(i)
if (u.level == n - 2):
for k in range(2, n + 1):
if (not u.contains(k)):
u.path.append(k)
u.path.append(1)
if (length(u.path, W) < minlength):
minlength = length(u.path, W)
opttour = u.path[:]
else:
u.bound = bound(u, W)
if (u.bound < minlength):
PQ.put((u.bound, u))
def bound(v, W):
n = len(W) - 1
total = length(v.path, W)
for i in range(1, n + 1):
if (hasOutgoing(i, v.path)):
continue
min = INF
for j in range(1, n + 1):
if (i == j): continue
if (hasIncoming(j, v.path)): continue
if (j == 1 and i == v.path[len(v.path) - 1]): continue
if (min > W[i][j]): min = W[i][j]
total += min
return total
4. 기타
만화 xkcd는 외판원이라는 설정을 집으며 물건을 eBay에 올리면 O(1)에 해결할 수 있다는 패기 넘치는 해법을 내놓았다. 옆에서 정공법으로 경로를 그리면서 닥치라고 쌍욕을 하는 세일즈맨이 킬포.수학 귀신에서 미해결 문제의 예시로 등장했다.