동적 프로그래밍
개념
- 주어진 문제에 대해 최적해를 제공하는 재귀 관계식(점화 관계식)을 도출
최적성의 원리: 주어진 문제의 최적해가 분할된 부분 문제에 대한 최적해로 구성 - 가장 작은 부분 문제부터 점화식의 해를 구한뒤 이를 테이블에 저장한다
- 이 해를 이용하여 점차적으로 입력 크기가 큰 상위 문제의 해를 구하는 상향식(bottom-up) 접근법
연쇄 행렬 곱셈
- n개의 행렬을 곱하는 최적의(최소의 곱셈 횟수를 가진) 곱셈 순서를 구하는 것
- 수행시간 O(n3)
스트링 편집 거리 (edit distance)
-
두 개의 문자열 사이의 편집거리는 문자열 X를 문자열 Y로 변환하는데 필요한 전체 편집연산(삽입, 삭제, 변경)에 대한 최소비용을 의미한다
-
일반적으로 편집 거리가 클수록 두 스트링의 유사도는 낮아진다
-
과정:
- 최적해와 부분 문제들의 관계 분석 (최적 부분 구조 분석)
- 점화식 세우기
- 최적해의 값 구하기
- 수행시간 O(mn)
NP 완전 문제
1. 클래스 NP
1) (결정론적) 튜링 기계: 읽고 쓸 수 있는 무한한 길이의 테이프를 가지며, 유한한 개수의 입력 기호와 테이프의 현재 위치에 쓰인 기호에 따라 (한 가지의 상태로만) 테이프의 위치를 바꾼다거나 쓰인 기호를 바꿀 수 있는 기계
2) 비결정론적 튜링 기계: 테이프의 위치를 바꾸거나 쓰인 기호를 바꿀 때 하나 이상의 상태로 바뀔 수 있거나 혹은 없을 수 있다
3) 다항시간 알고리즘: 수행시간이 입력의 크기에 대한 다항식으로 표현되는 알고리즘
- 다루기 쉬운(tractable) 문제: 튜링 기계를 이용한 다항시간 알고리즘이 존재하는 문제
- 다루기 어려운(untractable) 문제: 튜링 기계를 이용한 다항시간 알고리즘이 존재하는지 알 수 없는 문제
4) 판정 문제: 예 혹은 아니오 중 하나를 답으로 요구하는 문제
5) 클래스 P: (결정론적) 튜링 기계를 이용한 다항시간 해결할 수 있는 모든 판정 문제 튜링이다
6) 클래스 NP: 비결정론적 튜링 기계를 이용하여 다항시간에 해결할 수 있는 모든 판정 문제 튜링이 아니다
7) 변환(reduction): 문제 A의 입력과 출력을 문제 B의 입력과 출력 형태로 바꿀 수 있고, 여기에 문제 B를 해결하는 알고리즘을 적용함으로써 궁극적으로 문제 A를 풀 수 있다는 것
8) 근사 알고리즘: 최적화 문제에 대해 최적의 해에 가까운(근사한) 해를 구하는 알고리즘
- 최적의 해를 구하는 것보다 짧은 수행시간에 해를 구할 수 있다
- 최소 신장 트리를 이용한다
- 최소 신장트리 < 최적해 < 근사해
NP-완전(NP-complete) 문제
- 클래스 NP에 속하는 모든 문제가 주어진 어떤 문제로 다항식 시간에 변환되고 그 문제가 클래스 NP에 속하는 경우
- 헤밀토니언 사이클 문제
- 클리크 판정 문제
- 파티션 문제
- 버텍스 커버 문제
- CNF 만족성 문제
- 외판원 문제(TSP, traveling salesman problem): 주어진 비용보다 적은 비용으로 모든 도시를 한 번씩만 방문하고 돌아오는 방법이 존재하는가?
- 궤 채우기 문제
- 3-CNF 만족성 문제
9 0 / 1 배낭 문제
병렬 알고리즘
개념
- 여러 프로세스를 이용하여 동시에 명령을 수행할 수 있는 알고리즘
- 쿼드코어 시스템, 분산처리 시스템
병렬계산 모델
- PRAM, PMH, BSP, LogP
1. PRAM(Parallel Random Access Machine) 모델
- p개의 프로세서가 동시에 독립적인 명령어를 수행할 수 있고 공유메모리를 사용하는 병렬계산 모델
2. 작업량
- 순차 알고리즘: 짧은 시간과 적은 공간을 차지할수록 좋은 알고리즘
- 병렬 알고리즘: 짧은 시간과 적은 프로세서 개수를 사용할수록 좋은 알고리즘
- 작업량: 수행시간(T)과 프로세서 개수(p)의 곱 = P(n)*p, 작업량이 많을수록 비효율적
- 시간효율성: (S(n) /p) / P(n)
유전 알고리즘 (Generic Algorithm, GA)
1. 개념
- 1970년 존 홀랜드(John Holland)
- 자연계의 진화를 통해 관찰된 메커니즘을 모방하여 최적화 문제(탐색공간에서 더 좋은 해를 찾는 것)를 해결하기 위한 탐색 방법
2. 유전 알고리즘의 전형적인 처리과정
1) 특징
-
찰스 다윈의 자연계의 진화 시스템의 원칙에 따름: 자연선택(selection, 적자생존) -> 교차(crosscover,짝짓기) -> 변이(mutation)
-
연속적인 세대를 거치면서 개체 사이의 적자생존을 모방
-
각 개체는 하나의 가능한 해법을 함축하고 있는 염색체로 표현
-
염색체 정보의 결합을 통해 더 나은 자손을 생성하기 위해 각각 적합도 점수가 부여된 해를 선택적으로 키워 나가는 방법을 이용
-
인공지능 방법들보다 사소한 변화나 잡음에 강하고, 상태 공간의 탐색에 있어서 전형적인 최적화 탐색 방법보다 의미있는 결과를 제공
2) 기본 처리과정
-
초기화: 난수를 사용해 n개의 염색체로 이루어진 개체군을 생성
-
적합도: 각 염색체에 대해 적합도 점수를 계산
-
새 개체군: 선택, 교차, 변이, 저장의 과정을 반복
-
대체: 새 개체군으로 대체
-
종료검사
-
반복
3. 유전 알고리즘의 연산자
4. 유전 알고리즘의 매개변수
-
교차 확률
-
변이 확률
-
개체군의 크기
- 유전 알고리즘의 응요
-
병렬성에 유리
-
구현이 용이
-
많은 계산시간이 소요
