SMAK 알고리즘

SMAWK algorithm

SMAKE 알고리즘은 암묵적으로 정의된 완전 모노톤 매트릭스의 각 행에서 최소값을 찾기 위한 알고리즘이다. 피터 쇼르, 슐로모 모란, 알록 아가왈, 로버트 윌버, 마리아 클라웨 등 다섯 발명가의 이니셜에서 따온 이름이다.[1]

입력

이 알고리즘의 목적상, 매트릭스는 각 행의 최소값이 이전 행의 최소값과 같거나 큰 열에서 발생하는 경우 단조로 정의된다. (주어진 행렬의 행과 열의 임의 부분 집합에 의해 정의되는) 모든 하위 행렬에 대해 동일한 속성이 참이면 완전히 단조롭다. 마찬가지로, 행렬이 오른쪽 위와 왼쪽 아래 모서리에 있는 2×2 하위 행렬이 없으면 행렬은 완전히 단조로워진다. 모든 몽에 배열이 완전히 단조롭지만, 반드시 그 반대는 아니다.

SMAKE 알고리즘의 경우 검색할 매트릭스를 함수로 정의해야 하며, 이 함수는 알고리즘의 입력(매트릭스의 치수와 함께)으로 주어진다. 그런 다음 알고리즘은 특정 매트릭스 셀의 값을 알아야 할 때마다 함수를 평가한다. 만약 이 평가에 O(1)가 걸린다면, r 행과 c 열이 있는 매트릭스의 경우, 기능 평가의 실행 시간과 횟수는 모두 O(1 + log(r/c)이다. 이는 모든 매트릭스 셀을 평가하는 순진한 알고리즘의 O(r c) 시간보다 훨씬 빠르다.

방법

알고리즘의 기본이념은 일정한 인자에 의해 크기가 작은 동일한 유형의 단일 재귀 하위 문제로 풀어나가는 제거와 검색 전략을 따르는 것이다. 이를 위해 알고리즘은 먼저 매트릭스를 사전 처리하여 Graham 스캔의 것과 유사한 스택 기반 알고리즘과 모든 가장 가까운 작은 값 알고리즘을 사용하여 행 최소값을 포함할 수 없는 열의 일부를 제거한다. 알고리즘의 이 단계 이후 나머지 열의 수는 최대 행 수와 동일하다. 다음으로 알고리즘은 매트릭스의 짝수 행의 행 미니마를 찾기 위해 스스로를 재귀적으로 호출한다. 마지막으로 연속 이븐 행 미니마의 위치 사이의 열을 검색하여 알고리즘이 홀수 행에 남아 있는 미니마를 채운다.

적용들

Aggarwal 외 연구진이 원본 논문에서 제시한 이 방법의 주요 적용 분야는 계산 기하학, 볼록한 다각형의 각 지점에서 가장 먼 지점 찾기, 최적의 둘러싸인 다각형 찾기였다. 후속 연구에서는 문단을 선,[2] RNA 2차 구조 예측,[3] DNA 및 단백질 시퀀스 정렬,[4][5] 접두사 코드 구성,[6][7] 이미지 임계값 설정 등에서 동일한 알고리즘의 적용을 발견했다.

참조

  1. ^ Aggarwal, Alok; Klawe, Maria M.; Moran, Shlomo; Shor, Peter; Wilber, Robert (1987), "Geometric applications of a matrix-searching algorithm", Algorithmica, 2 (2): 195–208, doi:10.1007/BF01840359, MR 0895444.
  2. ^ Wilber, Robert (1988), "The concave least-weight subsequence problem revisited", Journal of Algorithms, 9 (3): 418–425, doi:10.1016/0196-6774(88)90032-6, MR 0955150
  3. ^ Larmore, Lawrence L.; Schieber, Baruch (1991), "On-line dynamic programming with applications to the prediction of RNA secondary structure", Journal of Algorithms, 12 (3): 490–515, doi:10.1016/0196-6774(91)90016-R, MR 1114923.
  4. ^ Russo, Luís M. S. (2012), "Monge properties of sequence alignment", Theoretical Computer Science, 423: 30–49, doi:10.1016/j.tcs.2011.12.068, MR 2887979.
  5. ^ Crochemore, Maxime; Landau, Gad M.; Ziv-Ukelson, Michal (2003), "A subquadratic sequence alignment algorithm for unrestricted scoring matrices", SIAM Journal on Computing, 32 (6): 1654–1673 (electronic), CiteSeerX 10.1.1.57.8562, doi:10.1137/S0097539702402007, MR 2034254.
  6. ^ Bradford, Phil; Golin, Mordecai J.; Larmore, Lawrence L.; Rytter, Wojciech (2002), "Optimal prefix-free codes for unequal letter costs: dynamic programming with the Monge property", Journal of Algorithms, 42 (2): 277–303, CiteSeerX 10.1.1.45.5501, doi:10.1006/jagm.2002.1213, MR 1895977.
  7. ^ Luessi, M.; Eichmann, M.; Schuster, G.M.; Katsaggelos, A.K. (2006), "New results on efficient optimal multilevel image thresholding", IEEE International Conference on Image Processing, pp. 773–776, CiteSeerX 10.1.1.461.663, doi:10.1109/ICIP.2006.312426, ISBN 978-1-4244-0480-3.