검색 알고리즘

컴퓨터 과학에서 검색 알고리즘(search algorithm)은 검색 문제를 해결하도록 설계된 알고리즘이다. 검색 알고리즘은 특정 자료 구조 내에 저장되거나 문제 영역의 탐색 공간에서 이산 또는 연속 값으로 계산된 정보를 검색하는 역할을 한다.

검색 엔진은 검색 알고리즘을 사용하지만, 이는 정보 검색 연구에 속하며 알고리즘학에는 속하지 않는다.

사용할 적절한 검색 알고리즘은 검색되는 자료 구조에 따라 달라지는 경우가 많으며, 데이터에 대한 사전 지식을 포함할 수도 있다. 검색 알고리즘은 탐색 트리, 연관 배열, 데이터베이스 인덱스와 같이 특별히 구성된 데이터베이스 구조를 통해 더 빠르거나 효율적으로 만들 수 있다.^[1]^[2]

검색 알고리즘은 검색 메커니즘에 따라 선형, 이진, 해싱의 세 가지 유형으로 분류할 수 있다. 선형 검색 알고리즘은 선형 방식으로 모든 레코드에서 대상 키와 관련된 레코드를 확인한다.^[3] 이진 검색 또는 절반 구간 검색은 검색 구조의 중심을 반복적으로 대상으로 삼아 검색 공간을 절반으로 나눈다. 비교 검색 알고리즘은 키를 비교하여 대상 레코드를 찾을 때까지 레코드를 연속적으로 제거하여 선형 검색을 개선하며, 정의된 순서가 있는 자료 구조에 적용할 수 있다.^[4] 디지털 검색 알고리즘은 숫자 키를 사용하여 자료 구조의 숫자 속성을 기반으로 작동한다.^[5] 마지막으로 해싱은 해시 함수를 기반으로 키를 레코드에 직접 매핑한다.^[6]

알고리즘은 종종 계산 복잡도 또는 최대 이론적 실행 시간으로 평가된다. 예를 들어, 이진 검색 함수는 최대 O(log n) 또는 로그 시간의 복잡도를 갖는다. 간단히 말해, 검색 대상을 찾는 데 필요한 최대 연산 횟수는 검색 공간 크기의 로그 함수이다.

가상 검색 공간

가상 공간을 검색하는 알고리즘은 제약 충족 문제에 사용되며, 목표는 특정 수학적 방정식 및 부등식/등식을 충족할 특정 변수에 대한 값 할당 집합을 찾는 것이다. 또한 목표가 해당 변수의 특정 함수를 최대화 또는 최소화할 변수 할당을 찾는 경우에도 사용된다. 이러한 문제에 대한 알고리즘에는 기본적인 무차별 대입 검색 (또는 "순진한" 또는 "정보 없는" 검색)과 선형 완화, 제약 생성 및 제약 전파와 같이 이 공간의 구조에 대한 부분적인 지식을 활용하려는 다양한 휴리스틱이 포함된다.

중요한 하위 클래스는 지역 탐색 방법으로, 검색 공간의 요소를 그래프의 정점으로 보고, 해당 경우에 적용할 수 있는 휴리스틱 집합으로 정의된 가장자리로 이동하여 공간을 스캔한다. 예를 들어, 가장 가파른 하강 또는 최상 우선 기준에 따라 또는 확률적 검색에서 가장자리를 따라 항목 간에 이동한다. 이 범주에는 담금질 기법, 타부 탐색법, A-팀즈,^[7] 유전 프로그래밍과 같이 임의의 휴리스틱을 특정 방식으로 결합하는 다양한 일반 메타휴리스틱 방법이 포함된다. 지역 검색의 반대는 전역 검색 방법이다. 이 방법은 검색 공간이 제한되지 않고 주어진 네트워크의 모든 측면이 검색 알고리즘을 실행하는 엔티티에 사용할 수 있을 때 적용할 수 있다.^[8]

이 클래스에는 또한 요소를 트리의 정점으로 보고 특정 순서로 해당 트리를 탐색하는 다양한 트리 검색 알고리즘이 포함된다. 후자의 예로는 깊이 우선 탐색 및 너비 우선 탐색과 같은 철저한 방법과 퇴각검색 및 분기 한정법과 같은 다양한 휴리스틱 기반 탐색 트리 가지치기 방법이 있다. 최선을 다해서만 확률적으로 작동하는 일반적인 메타휴리스틱과 달리, 이러한 많은 트리 검색 방법은 충분한 시간이 주어지면 정확하거나 최적의 해를 찾는 것이 보장된다. 이를 "완전성"이라고 한다.

또 다른 중요한 하위 클래스는 체스 또는 백개먼과 같은 여러 플레이어 게임의 게임 트리를 탐색하는 알고리즘으로 구성되며, 노드는 현재 상황에서 발생할 수 있는 모든 가능한 게임 상황으로 구성된다. 이러한 문제의 목표는 상대방의 모든 가능한 움직임을 고려하여 승리할 최상의 기회를 제공하는 움직임을 찾는 것이다. 이와 유사한 문제는 로봇 안내 또는 마케팅, 금융, 군사 전략 계획과 같이 인간 또는 기계가 결과가 완전히 통제할 수 없는 연속적인 결정을 내려야 할 때 발생한다. 이러한 종류의 문제인 조합 검색은 인공지능의 맥락에서 광범위하게 연구되어 왔다. 이 클래스의 알고리즘 예로는 최소극대화 알고리즘, 알파-베타 가지치기, A* 알고리즘 및 그 변형이 있다.

주어진 구조의 하위 구조

중요하고 광범위하게 연구된 하위 클래스는 주어진 그래프에서 특정 하위 구조(예: 하위 그래프, 경로, 회로 등)를 찾는 그래프 알고리즘, 특히 그래프 순회 알고리즘이다. 예로는 데이크스트라 알고리즘, 크러스컬 알고리즘, 최근접 이웃 알고리즘, 프림 알고리즘이 있다.

이 범주의 또 다른 중요한 하위 클래스는 문자열 검색 알고리즘으로, 문자열 내에서 패턴을 검색한다. 두 가지 유명한 예는 보이어-무어 및 커누스-모리스-프랫 알고리즘과 접미사 트리 자료 구조를 기반으로 하는 여러 알고리즘이다.

함수의 최댓값 검색

1953년, 미국 통계학자 잭 키퍼는 단봉 함수의 최댓값을 찾는 데 사용할 수 있으며 컴퓨터 과학에서 많은 다른 응용 분야를 가진 피보나치 탐색을 고안했다.

양자 컴퓨터

양자 컴퓨터용으로 설계된 검색 방법도 있다. 예를 들어 그로버 알고리즘은 자료 구조나 휴리스틱의 도움 없이도 선형 또는 무차별 대입 검색보다 이론적으로 빠르다. 양자 컴퓨터의 아이디어와 응용은 아직 완전히 이론적이지만, 그로버의 알고리즘과 같은 알고리즘을 사용하여 양자 컴퓨팅 시스템의 가상 물리적 버전을 정확하게 복제하는 연구가 진행되었다.^[9]

검색 알고리즘