최적화 관련 상식

• 물품을 무게순으로 미리 정렬한 뒤 FF 알고리즘을 적용하는 방법을 FFD 알고리즘(first-first decreasing algorithm)이라 한다.
• 절제 평면법은 완화 문제의 최적 설루션에서 시작해서 실행 가능 설루션을 남기면서 완화 문제의 최적 설루션을 소거하는 제약조건을 조직적으로 추가하는 절차를 반복 적용하는 알고리즘이다. 정수 계획 문제에 대한 절제 평면법을 1958년에 고모리가 제안했다.
• 여러 초기 솔루션에서 국소 탐색 알고리즘을 실행해서 얻어진 국소 최적 설루션 중에서 가장 좋은 것을 출력하는 기법이 다중 시작 국소 탐색 알고리즘(multi-start local search, MSL)이다.
• 최적화에 대한 근사 성능이 보증되지 않은 실행 가능 설루션을 하나 출력하는 알고리즘을 휴리스틱이라 한다.
• 주 쌍대법(primal-dual method)는 선형 계획 완화 문제의 쌍대 문제를 이용해 원래 문제에 대해 실행 가능 설루션을 구하는 방법이다.
• 모듈러리티(modularity)란 커뮤니티 검출의 우수함을 나타내는 평가 함수의 하나다.
• 동적 계획법(dynamic programming, DP)은 문제를 작은 부분 문제로 분할해서 푼 뒤, 부분 문제의 최적 설루션을 결합해서 원래 문제의 최적 설루션을 구하는 분할 정복법과 유사한 기법이다. 동적 계획법은 '원래 문제의 최적 설루션이 어떤 부분 문제의 최적 설루션을 포함한다'라는 부분 구조 최적성을 갖는 문제를 대상으로 한다
• NP 난해한 조합 최적화 문제를 푸는 알고리즘은 완전 알고리즘, 근사 알고리즘, 휴리스틱으로 분류할 수 있다. 임의의 문제 사례에 대해 최적 설루션을 하나 출력하는 알고리즘을 완전 알고리즘이라 한다.
• 계산 도중 경과를 일시적으로 유지하기 위해 필요한 기억 영역의 크기를 공간 복잡도(space complexity)라 한다. 시간 복잡도와 공간 복잡도를 합쳐 계산 복잡도라 한다.
• 근방은 국소 탐색 알고리즘의 설계에서 가장 중요한 요소 중 하나다. 근방 안에 개선 설루션이 포함된 가능성이 높아지도록, 그러면서도 근방이 너무 커지지 않도록 설계해야 한다.
• 조합 최적화 문제의 실행 가능 솔루션을 단계적으로 구축할 때 각 단계에서 국소적인 평갓값이 가장 높은 요소를 선택하는 기법을 탐욕 알고리즘(greedy method)이라 한다.
• 과거의 탐색에서 얻은 좋은 설루션에 무작위로 변형을 추가하는 것을 초기 설루션으로 하여 국소 탐색 알고리즘을 적용하는 절차를 반복하는 기법이 반복 국소 탐색 알고리즘(iterated local search, ILS)이다.
• 알고리즘의 성능은 계산 종료까지 실행된 기본 연산(사칙 연산, 비교 연산, 입력 데이터 로딩, 출력 데이터 쓰기 등)의 회수를 이용해 평가되는 경우가 많고, 이를 계산 시간 또는 시간 복잡도(time complexity)라 한다.
• 정수 계획 문제를 포함한 NP 난해한 조합 최적화 문제에서는 분기 한정법과 절제 평면법이 대표적인 완전 알고리즘으로 알려져 있다. 분기 한정법은 잠정 설루션에서 얻을 수 있는 최적값의 하한과 완화 문제를 풀어 얻을 수 있는 최적 설루션의 상한을 이용해 한정 조작을 구현한다.
• 조합 최적화 문제는 최적 설루션을 포함하는 설루션의 집합이 조합적인 구조를 갖는 최적화 문제이며 설루션이 집합, 순서, 할당, 그래프, 논릿값, 정수 등으로 나타나는 경우가 많다. 정수 변수는 이산적인 값을 갖는 사상을 나타내는 것뿐만 아니라 제약조건이나 상태를 전환하는 스위치로 이용할 수 있어, 원리적으로 모든 조합 최적화 문제는 정수 계획 문제로 정식화할 수 있다.
• 국소 탐색 알고리즘은 많은 조합 최적화 문제에 대해 관측되는 '좋은 설루션끼리는 비슷한 구조를 갖는다'라는 근접 최적성(proximity optimality principle, POP)이라 불리는 특징을 바탕으로 설계되어 있다. 근접 최적성이 성립한다면 좋은 설루션과 비슷한 설루션 안에서 개선 설루션을 발견할 가능성이 높다.
• 알고리즘의 실행에 필요한 계산 복잡도를 평가할 때, 알고리즘의 세부 영향을 제외하기 위해 상수 배의 차이를 무시한 오더 표기법을 자주 이용한다. 란다우의 O-표기법이라고도 한다.
• 주어진 계산 시간 안에 최적 설루션을 구하지 못하더라도, 높은 품질의 실행 가능 설루션을 구할 수 있다면 충분히 만족할 수 있는 사례도 많다. 임의의 문제 사례에 대해 근사 성능을 보증할 수 있는 실행 가능 설루션을 하나 출력하는 알고리즘을 근사 알고리즘이라 한다.
• 보통 선형 계획 문제에서 모든 변수는 연속적인 실숫값을 갖는데, 모든 변수가 이산적인 정숫값만 갖는 선형 계획 문제를 정수(선형) 계획 문제(Integer programming problem, IP)라 한다. 여기서 실숫값을 갖는 변수를 실수 변수, 정숫값만 갖는 변수를 정수 변수라 한다.
• 두 개 이상의 변을 포함하며, 시작점과 종료점이 같은 경로를 닫힌 경로(cycle)라 한다.